## March 2022

### Jean-Florent Raymond, Long induced paths in minor-closed graph classes and beyond

Zoom ID: 869 4632 6610 (ibsdimag)

In 1982 Galvin, Rival, and Sands proved that in $K_{t,t}$-subgraph free graphs (t being fixed), the existence of a path of order n guarantees the existence of an induced path of order f(n), for some (slowly) increasing function f. The problem of obtaining good lower-bounds for f for specific graph classes was investigated decades later

## April 2022

### Younjin Kim (김연진), On the extremal problems related to Szemerédi’s theorem

Room B232 IBS (기초과학연구원)

In 1975, Szemerédi proved that for every real number $\delta > 0$ and every positive integer $k$, there exists a positive integer $N$ such that every subset $A$ of the set $\{1, 2, \cdots, N \}$ with $|A| \geq \delta N$ contains an arithmetic progression of length $k$. There has been a plethora of

### Jakub Gajarský, Model Checking on Interpretations of Classes of Bounded Local Clique-Width

Zoom ID: 869 4632 6610 (ibsdimag)

The first-order model checking problem for finite graphs asks, given a graph G and a first-order sentence $\phi$ as input, to decide whether $\phi$ holds on G. Showing the existence of an efficient algorithm for this problem implies the existence of efficient parameterized algorithms for various commonly studied problems, such as independent set, distance-r dominating

### Boram Park (박보람), Odd coloring of sparse graphs

Room B232 IBS (기초과학연구원)

We introduce an odd coloring of a graph, which was introduced very recently, motivated by parity type colorings of graphs. A proper vertex coloring of graph $G$ is said to be odd if for each non-isolated vertex $x \in V (G)$ there exists a color $c$ such that $c$ is used an odd number of

### Michael Savery, Induced subgraphs of induced subgraphs of large chromatic number

Zoom ID: 869 4632 6610 (ibsdimag)

We prove that for every graph F with at least one edge there are graphs H of arbitrarily large chromatic number and the same clique number as F such that every F-free induced subgraph of H has chromatic number at most c=c(F). (Here a graph is F-free if it does not contain an induced copy

## May 2022

### Cheolwon Heo (허철원), The complexity of the matroid-homomorphism problems

Room B332 IBS (기초과학연구원)

In this talk, we introduce homomorphisms between binary matroids that generalize graph homomorphisms. For a binary matroid $N$, we prove a complexity dichotomy for the problem $\rm{Hom}_\mathbb{M}(N)$ of deciding if a binary matroid $M$ admits a homomorphism to $N$. The problem is polynomial-time solvable if $N$ has a loop or has no circuits of odd

### Kyeongsik Nam (남경식), Large deviations for subgraph counts in random graphs

Room B332 IBS (기초과학연구원)

The upper tail problem for subgraph counts in the Erdos-Renyi graph, introduced by Janson-Ruciński, has attracted a lot of attention. There is a class of Gibbs measures associated with subgraph counts, called exponential random graph model (ERGM). Despite its importance, lots of fundamental questions have remained unanswered owing to the lack of exact solvability. In

### Andreas Holmsen, A colorful version of the Goodman-Pollack-Wenger transversal theorem

Room B332 IBS (기초과학연구원)

Hadwiger's transversal theorem gives necessary and sufficient conditions for the existence of a line transversal to a family of pairwise disjoint convex sets in the plane. These conditions were subsequently generalized to hyperplane transversals in $\mathbb{R}^d$ by Goodman, Pollack, and Wenger. Here we establish a colorful extension of their theorem, which proves a conjecture of

### Jan Kurkofka, Canonical Graph Decompositions via Coverings

Zoom ID: 869 4632 6610 (ibsdimag)

We present a canonical way to decompose finite graphs into highly connected local parts. The decomposition depends only on an integer parameter whose choice sets the intended degree of locality. The global structure of the graph, as determined by the relative position of these parts, is described by a coarser model. This is a simpler

### Gil Kalai, The Cascade Conjecture and other Helly-type Problems

Zoom ID: 868 7549 9085

For a set $X$ of points $x(1)$, $x(2)$, $\ldots$, $x(n)$ in some real vector space $V$ we denote by $T(X,r)$ the set of points in $X$ that belong to the convex hulls of r pairwise disjoint subsets of $X$. We let $t(X,r)=1+\dim(T(X,r))$. Radon's theorem asserts that If $t(X,1)< |X|$, then $t(X, 2) >0$. The first

기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209