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
Ramsey numbers and the Zarankiewicz problem
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 .
more »
« less
- PAR ID:
- 10498580
- Publisher / Repository:
- Oxford University Press (OUP)
- Date Published:
- Journal Name:
- Bulletin of the London Mathematical Society
- ISSN:
- 0024-6093
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
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 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
