기초과학연구원 이산수학그룹
This program consists of a short intensive workshop, where mathematicians from across the globe will come together to work on open problems in structural graph theory. We will consider the following research themes: graph minors, graph colouring, Hadwiger’s Conjecture, bounded expansion classes, graph product structure theory, generalised colouring numbers, VC dimension, induced subgraphs, Erdős-Hajnal conjecture, …
The Ramsey number $R(F,H)$ is the minimum number $N$ such that any $N$-vertex graph either contains a copy of $F$ or its complement contains $H$. Burr in 1981 proved a pleasingly general result that for any graph $H$, provided $n$ is sufficiently large, a natural lower bound construction gives the correct Ramsey number involving cycles: …
Suppose that $E$ is a subset of $\mathbb{F}_q^n$, so that each point is contained in $E$ with probability $\theta$, independently of all other points. Then, what is the probability that there is an $m$-dimensional affine subspace that contains at least $\ell$ points of $E$? What is the probability that $E$ intersects all $m$-dimensional affine subspaces? …
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 …
To celebrate the opening of the IBS ECOPRO (Extremal Combinatorics and Probability) Group, we will organize a 3-day online conference from April 4 to April 6. Official Website: https://www.ibs.re.kr/ecopro/event/opening/ Invited Speakers Noga Alon Princeton University József Balogh University of Illinois at Urbana-Champaign Jeff Kahn Rutgers University Mihyun Kang Graz University of Technology Jeong Han Kim …
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 …
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 …
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 …
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 …
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 …