More Like this

1. Ramsey numbers of hypergraphs with a given size

   https://doi.org/10.1017/S0305004124000409  

   BRADAČ, DOMAGOJ; FOX, JACOB; SUDAKOV, BENNY (January 2025, Mathematical Proceedings of the Cambridge Philosophical Society)

   Abstract Theq-colour Ramsey number of ak-uniform hypergraphHis the minimum integerNsuch that anyq-colouring of the completek-uniform hypergraph onNvertices contains a monochromatic copy ofH. The study of these numbers is one of the central topics in Combinatorics. In 1973, Erdős and Graham asked to maximise the Ramsey number of a graph as a function of the number of its edges. Motivated by this problem, we study the analogous question for hypergaphs. For fixed$$k \ge 3$$and$$q \ge 2$$we prove that the largest possibleq-colour Ramsey number of ak-uniform hypergraph withmedges is at most$$\mathrm{tw}_k(O(\sqrt{m})),$$where tw denotes the tower function. We also present a construction showing that this bound is tight for$$q \ge 4$$. This resolves a problem by Conlon, Fox and Sudakov. They previously proved the upper bound for$$k \geq 4$$and the lower bound for$$k=3$$. Although in the graph case the tightness follows simply by considering a clique of appropriate size, for higher uniformities the construction is rather involved and is obtained by using paths in expander graphs. 

   more » « less
2. The Edge-Statistics Conjecture for Hypergraphs

   https://doi.org/10.1093/imrn/rnaf273  

   Jain, Vishesh; Kwan, Matthew; Mubayi, Dhruv; Tran, Tuan (September 2025, International Mathematics Research Notices)

   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}$$. 

   more » « less
3. On Off-Diagonal Hypergraph Ramsey Numbers

   https://doi.org/10.1093/imrn/rnaf122  

   Conlon, David; Fox, Jacob; Gunby, Benjamin; He, Xiaoyu; Mubayi, Dhruv; Suk, Andrew; Verstraëte, Jacques (June 2025, International Mathematics Research Notices)

   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. 

   more » « less
4. Supersaturation of even linear cycles in linear hypergraphs

   https://doi.org/10.1017/S0963548320000206  

   Jiang, Tao; Yepremyan, Liana (September 2020, Combinatorics, Probability and Computing)

   Abstract A classical result of Erdős and, independently, of Bondy and Simonovits [3] says that the maximum number of edges in ann-vertex graph not containingC_2k, the cycle of length 2k, isO(n^1+1/k). Simonovits established a corresponding supersaturation result forC_2k’s, showing that there exist positive constantsC,cdepending only onksuch that everyn-vertex graphGwithe(G)⩾Cn^1+1/kcontains at leastc(e(G)/v(G))^2kcopies ofC_2k, this number of copies tightly achieved by the random graph (up to a multiplicative constant). In this paper we extend Simonovits' result to a supersaturation result ofr-uniform linear cycles of even length inr-uniform linear hypergraphs. Our proof is self-contained and includes ther= 2 case. As an auxiliary tool, we develop a reduction lemma from general host graphs to almost-regular host graphs that can be used for other supersaturation problems, and may therefore be of independent interest. 

   more » « less
5. Off‐Diagonal Ramsey Numbers for Slowly Growing Hypergraphs

   https://doi.org/10.1002/rsa.21284  

   Mattheus, Sam; Mubayi, Dhruv; Nie, Jiaxi; Verstraëte, Jacques (January 2025, Random Structures & Algorithms)

   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. 

   more » « less