기초과학연구원 이산수학그룹
This talk follows on from the recent talk of Pascal Gollin in this seminar series, but will aim to be accessible for newcomers. Erdős and Pósa proved in 1965 that …
We examine algorithmic extensions of two classic results of extremal combinatorics. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree d>1, …
It is known that the rank- and tree-width of the random graph $G(n,p)$ undergo a phase transition at $p = 1/n$; whilst for subcritical $p$, the rank- and tree-width are bounded above …
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 …
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 …
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 …
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 …
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 …
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 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 …