기초과학연구원 이산수학그룹
On April 14, 2020, Casey Tompkins from IBS discrete mathematics group gave a talk on the saturation version of the problems related to the Erdős-Szekeres theorem on convex k-gons, sequences, and posets. The title of his talk is “Saturation problems in the Ramsey theory of graphs, posets and point sets“.
In 1964, Erdős, Hajnal and Moon introduced a saturation version of Turán’s classical theorem in extremal graph theory. In particular, they determined the minimum number of edges in a $K_r$-free, $n$-vertex graph with the property that the addition of any further edge yields a copy of $K_r$. We consider analogues of this problem in other settings. We prove a saturation version of the Erdős-Szekeres theorem about monotone subsequences and saturation versions of some Ramsey-type theorems on graphs and Dilworth-type theorems on posets.
We also consider semisaturation problems, wherein we allow the family to have the forbidden configuration, but insist that any addition to the family yields a new copy of the forbidden configuration. In this setting, we prove a semisaturation version of the Erdős-Szekeres theorem on convex $k$-gons, as well as multiple semisaturation theorems for sequences and posets.
This project was joint work with Gábor Damásdi, Balázs Keszegh, David Malec, Zhiyu Wang and Oscar Zamora.
On October 1, 2019, Casey Tompkins at IBS discrete mathematics group presented a seminar talk on an extension of Turán’s theorem to hypergraphs. The title of his talk was “Extremal problems for Berge hypergraphs“.
Given a graph $G$, there are several natural hypergraph families one can define. Among the least restrictive is the family $BG$ of so-called Berge copies of the graph $G$. In this talk, we discuss Turán problems for families $BG$ in $r$-uniform hypergraphs for various graphs $G$. In particular, we are interested in general results in two settings: the case when $r$ is large and $G$ is any graph where this Turán number is shown to be eventually subquadratic, as well as the case when $G$ is a tree where several exact results can be obtained. The results in the first part are joint with Grósz and Methuku, and the second part with Győri, Salia and Zamora.
The IBS discrete mathematics group welcomes Dr. Casey Tompkins, a new research fellow at the IBS discrete mathematics group from September 1, 2019.
He received his Ph.D. from the Department of Mathematics at the Central European University in Budapest, Hungary in 2015 under the supervision of Prof. Gyula O. H. Katona.