Tag: CaseyTompkins

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.

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.

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.

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.

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.