Search for: All records

Abstract Let $$r,k,\ell $$ be integers such that $$0\le \ell \le \binom{k}{r}$$. Given a large $$r$$-uniform hypergraph $$G$$, we consider the fraction of $$k$$-vertex subsets that span exactly $$\ell $$ edges. If $$\ell $$ is $$0$$ or $$\binom{k}{r}$$, this fraction can be exactly $$1$$ (by taking $$G$$ to be empty or complete), but for all other values of $$\ell $$, one might suspect that this fraction is always significantly smaller than $$1$$. In this paper we prove an essentially optimal result along these lines: if $$\ell $$ is not $$0$$ or $$\binom{k}{r}$$, then this fraction is at most $$(1/e) + \varepsilon $$, assuming $$k$$ is sufficiently large in terms of $$r$$ and $$\varepsilon>0$$, and $$G$$ is sufficiently large in terms of $$k$$. Previously, this was only known for a very limited range of values of $$r,k,\ell $$ (due to Kwan–Sudakov–Tran, Fox–Sauermann, and Martinsson–Mousset–Noever–Trujić). Our result answers a question of Alon–Hefetz–Krivelevich–Tyomkyn, who suggested this as a hypergraph generalization of their edge-statistics conjecture. We also prove a much stronger bound when $$\ell $$ is far from 0 and $$\binom{k}{r}$$. 

A natural open problem in Ramsey theory is to determine those $3$-graphs $H$for which the off-diagonal Ramsey number $r(H,K_n^{\left(3\right)})$grows polynomially with $n$. We make substantial progress on this question by showing that if $H$is tightly connected or has at most two tight components, then $r(H,K_n^{\left(3\right)})$grows polynomially if and only if $H$is contained in an iterated blowup of an edge. 

Abstract For an integer , the Erdős–Rogers function is the maximum integer such that every ‐vertex ‐free graph has a ‐free induced subgraph with vertices. It is known that for all , as . In this paper, we show that for all , there exists a constant such thatThis improves previous bounds of order by Dudek, Retter and Rödl and answers a question of Warnke. 

Abstract A fundamental problem in Ramsey theory is to determine the growth rate in terms of $$n$$ of the Ramsey number $$r(H, K_{n}^{(3)})$$ of a fixed $$3$$-uniform hypergraph $$H$$ versus the complete $$3$$-uniform hypergraph with $$n$$ vertices. We study this problem, proving two main results. First, we show that for a broad class of $$H$$, including links of odd cycles and tight cycles of length not divisible by three, $$r(H, K_{n}^{(3)}) \ge 2^{\Omega _{H}(n \log n)}$$. This significantly generalizes and simplifies an earlier construction of Fox and He which handled the case of links of odd cycles and is sharp both in this case and for all but finitely many tight cycles of length not divisible by three. Second, disproving a folklore conjecture in the area, we show that there exists a linear hypergraph $$H$$ for which $$r(H, K_{n}^{(3)})$$ is superpolynomial in $$n$$. This provides the first example of a separation between $$r(H,K_{n}^{(3)})$$ and $$r(H,K_{n,n,n}^{(3)})$$, since the latter is known to be polynomial in $$n$$ when $$H$$ is linear. 

ABSTRACT For ak‐uniform hypergraph and a positive integer , the Ramsey number denotes the minimum such that every ‐vertex ‐free ‐uniform hypergraph contains an independent set of vertices. A hypergraph isslowly growingif there is an ordering of its edges such that for each . We prove that if is fixed and is any non‐k‐partite slowly growing ‐uniform hypergraph, then for ,In particular, we deduce that the off‐diagonal Ramsey number is of order , where is the triple system . This is the only 3‐uniform Berge triangle for which the polynomial power of its off‐diagonal Ramsey number was not previously known. Our constructions use pseudorandom graphs and hypergraph containers. 

Abstract Building on recent work of Mattheus and Verstraëte, we establish a general connection between Ramsey numbers of the form for a fixed graph and a variant of the Zarankiewicz problem asking for the maximum number of 1s in an by ‐matrix that does not have any matrix from a fixed finite family derived from as a submatrix. As an application, we give new lower bounds for the Ramsey numbers and , namely, and . We also show how the truth of a plausible conjecture about Zarankiewicz numbers would allow an approximate determination of for any fixed integer .