기초과학연구원 이산수학그룹
On April 2, 2024, Casey Tompkins from the Alfréd Rényi Institute of Mathematics gave a talk at the Discrete Math Seminar on the maximum number of edges in a graph without cycles of length 0 mod 4. The title of his talk was “On graphs without cycles of length 0 modulo 4“.
Bollobás proved that for every $k$ and $\ell$ such that $k\mathbb{Z}+\ell$ contains an even number, an $n$-vertex graph containing no cycle of length $\ell \bmod k$ can contain at most a linear number of edges. The precise (or asymptotic) value of the maximum number of edges in such a graph is known for very few pairs $\ell$ and $k$. We precisely determine the maximum number of edges in a graph containing no cycle of length $0 \bmod 4$.
This is joint work with Ervin Győri, Binlong Li, Nika Salia, Kitti Varga and Manran Zhu.
On November 23, 2021, Casey Tompkins from the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar on the poset Ramsey number for Boolean lattices. The title of his talk was “Ramsey numbers of Boolean lattices“.
The poset Ramsey number $R(Q_{m},Q_{n})$ is the smallest integer $N$ such that any blue-red coloring of the elements of the Boolean lattice $Q_{N}$ has a blue induced copy of $Q_{m}$ or a red induced copy of $Q_{n}$. Axenovich and Walzer showed that $n+2\le R(Q_{2},Q_{n})\le2n+2$. Recently, Lu and Thompson
improved the upper bound to $\frac{5}{3}n+2$. In this paper, we solve this problem asymptotically by showing that $R(Q_{2},Q_{n})=n+O(n/\log n)$.
Joint work with Dániel Grósz and Abhishek Methuku.
On March 30, 2021, Casey Tompkins from the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar on an upper bound for the maximum number of edges in a 3-uniform hypergraph having no Berge cycles of length 4. The title of his talk was “3-uniform hypergraphs avoiding a cycle of length four“.
We show that that the maximum number of of edges in a $3$-uniform hypergraph without a Berge-cycle of length four is at most $(1+o(1)) \frac{n^{3/2}}{\sqrt{10}}$. This improves earlier estimates by Győri and Lemons and by Füredi and Özkahya. Joint work with Ergemlidze, Győri, Methuku, Salia.
On November 10, 2020, Casey Tompkins from the IBS Discrete Mathematics Group presented a talk on the extremal problems on Boolean and linear lattices with forbidden posets at the Discrete Math Seminar. The title of his talk was “Extremal forbidden poset problems in Boolean and linear lattices“.
Extending the classical theorem of Sperner on the maximum size of an antichain in the Boolean lattice, Katona and Tarján introduced a general extremal function $La(n,P)$, defined to be the maximum size of a family of subsets of $[n]$ which does not contain a given poset $P$ among its containment relations. In this talk, I will discuss what is known about the behavior of $La(n,P)$ and its natural extension to the lattice of subspaces of a vector space over a finite field. In particular, I will highlight some recent joint work with Jimeng Xiao. Many open problems will also be discussed.
On July 14, 2020, Casey Tompkins from IBS Discrete Mathematics Group gave a talk on inverse Turán problems at the Discrete Math Seminar. The goal is for a fixed graph H and an integer k to find the minimum number of edges of a graph G such that that every subgraph of G with at least k edges has a subgraph isomorphic to H. The title of his talk is “Inverse Turán Problems“.
For given graphs $G$ and $F$, the Turán number $ex(G,F)$ is defined to be the maximum number of edges in an $F$-free subgraph of $G$. Briggs and Cox introduced a dual version of this problem wherein for a given number $k$, one maximizes the number of edges in a host graph $G$ for which $ex(G,H) < k$. We resolve a problem of Briggs and Cox in the negative by showing that the inverse Turán number of $C_4$ is $\Theta(k^{3/2})$. More generally, we determine the order of magnitude of the inverse Turán number of $K_{s,t}$ for all $s$ and $t$. Addressing another problem of Briggs and Cox, we determine the asymptotic value of the inverse Turán number of the paths of length $4$ and $5$ and provide an improved lower bound for all paths of even length. We also obtain improved bounds on the inverse Turán number of even cycles
Joint work with Ervin Győri, Nika Salia and Oscar Zamora.