An official website of the United States government
Abstract Let denote the complete 3‐uniform hypergraph on vertices and the 3‐uniform hypergraph on vertices consisting of all edges incident to a given vertex. Whereas many hypergraph Ramsey numbers grow either at most polynomially or at least exponentially, we show that the off‐diagonal Ramsey number exhibits an unusual intermediate growth rate, namely,for some positive constants and . The proof of these bounds brings in a novel Ramsey problem on grid graphs which may be of independent interest: what is the minimum such that any 2‐edge‐coloring of the Cartesian product contains either a red rectangle or a blue ?
more »
« less
Off‐Diagonal Ramsey Numbers for Slowly Growing Hypergraphs
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
- Award ID(s):
- 2347832
- PAR ID:
- 10597629
- Publisher / Repository:
- Wiley
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 66
- Issue:
- 1
- ISSN:
- 1042-9832
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
Abstract The list Ramsey number , recently introduced by Alon, Bucić, Kalvari, Kuperwasser, and Szabó, is a list‐coloring variant of the classical Ramsey number. They showed that if is a fixed ‐uniform hypergraph that is not ‐partite and the number of colors goes to infinity, . We prove that if and only if is not ‐partite.more » « less
-
Abstract Theq-color Ramsey number of ak-uniform hypergraphG, denotedr(G; q), is the minimum integerNsuch that any coloring of the edges of the completek-uniform hypergraph onNvertices contains a monochromatic copy ofG. The study of these numbers is one of the most central topics in combinatorics. One natural question, which for triangles goes back to the work of Schur in 1916, is to determine the behavior ofr(G; q) for fixedGandqtending to infinity. In this paper, we study this problem for 3-uniform hypergraphs and determine the tower height ofr(G; q) as a function ofq. More precisely, given a hypergraphG, we determine whenr(G; q) behaves polynomially, exponentially or double exponentially inq. This answers a question of Axenovich, Gyárfás, Liu and Mubayi.more » « less
-
Abstract The hedgehog H t is a 3-uniform hypergraph on vertices $$1, \ldots ,t + \left({\matrix{t \cr 2}}\right)$$ such that, for any pair ( i , j ) with 1 ≤ i < j ≤ t , there exists a unique vertex k > t such that { i , j , k } is an edge. Conlon, Fox and Rödl proved that the two-colour Ramsey number of the hedgehog grows polynomially in the number of its vertices, while the four-colour Ramsey number grows exponentially in the square root of the number of vertices. They asked whether the two-colour Ramsey number of the hedgehog H t is nearly linear in the number of its vertices. We answer this question affirmatively, proving that r ( H t ) = O ( t 2 ln t ).more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1002/rsa.21284
