Tag: CaseyTompkins

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 modk$ 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 $0mod4$.
This is joint work with Ervin Győri, Binlong Li, Nika Salia, Kitti Varga and Manran Zhu.

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)\le 2n+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 $\mathrm{\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.