Search for: All records

For positive integers 𝑛, 𝑟, 𝑠 with 𝑟 > 𝑠, the set-coloring Ramsey number 𝑅(𝑛; 𝑟, 𝑠) is the minimum 𝑁 such that if every edge of the complete graph 𝐾_𝑁 receives a set of 𝑠 colors from a palette of 𝑟 colors, then there is guaranteed to be a monochromatic clique on 𝑛 vertices, that is, a subset of 𝑛 vertices where all of the edges between them receive a common color. In particular, the case 𝑠 = 1 corresponds to the classical multicolor Ramsey number. We prove general upper and lower bounds on 𝑅(𝑛; 𝑟, 𝑠) which imply that 𝑅(𝑛; 𝑟, 𝑠) = 2^Θ(𝑛𝑟) if 𝑠/𝑟 is bounded away from 0 and 1. The upper bound extends an old result of Erdős and Szemerédi, who treated the case 𝑠 = 𝑟 − 1, while the lower bound exploits a connection to error-correcting codes. We also study the analogous problem for hypergraphs. 

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 ?

 

We consider the maximum chromatic number of hypergraphs consisting of cliques that have pairwise small intersections. Designs of the appropriate parameters produce optimal constructions, but these are generally known to exist only when the number of cliques is exponential in the clique size (Glock, Kühn, Lo, and Osthus,Mem. Amer. Math. Soc.284(2023) v+131 pp; Keevash, Preprint; Rödl,Eur. J. Combin. 6 (1985) 69–78). We construct near designs where the number of cliques is polynomial in the clique size, and show that they have large chromatic number. The case when the cliques have pairwise intersections of size at most one seems particularly challenging. Here, we give lower bounds by analyzing a random greedy hypergraph process. We also consider the related question of determining the maximum number of caps in a finite projective/affine plane and obtain nontrivial upper and lower bounds.

 

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 .

 

We show that there is an absolute constant c > 0 c>0 such that the following holds. For every n > 1 n > 1 , there is a 5-uniform hypergraph on at least 2 2 c n 1 / 4 2^{2^{cn^{1/4}}} vertices with independence number at most n n , where every set of 6 vertices induces at most 3 edges. The double exponential growth rate for the number of vertices is sharp. By applying a stepping-up lemma established by the first two authors, analogous sharp results are proved for k k -uniform hypergraphs. This answers the penultimate open case of a conjecture in Ramsey theory posed by Erdős and Hajnal in 1972.