Search

Building on recent work of Mattheus and Verstraëte, we establish a general connection between Ramsey numbers of the form r(F,t)$r(F,t)$ for F$F$ a fixed graph and a variant of the Zarankiewicz problem asking for the maximum number of 1s in an m$m$ by n$n$0/1$0/1$‐matrix that does not have any matrix from a fixed finite family L(F)$\mathcal {L}(F)$ derived from F$F$ as a submatrix. As an application, we give new lower bounds for the Ramsey numbers r(C5,t)$r(C_5,t)$ and r(C7,t)$r(C_7,t)$, namely, r(C5,t)=Ω∼(t107)$r(C_5,t) = \tilde{\Omega }(t^{\frac{10}{7}})$ and r(C7,t)=Ω∼(t54)$r(C_7,t) = \tilde{\Omega }(t^{\frac{5}{4}})$. We also show how the truth of a plausible conjecture about Zarankiewicz numbers would allow an approximate determination of r(C2ℓ+1,t)$r(C_{2\ell +1}, t)$ for any fixed integer ℓ⩾2$\ell \geqslant 2$. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Let Km(3)$$ {K}_m^{(3)} $$ denote the complete 3‐uniform hypergraph on m$$ m $$ vertices and Sn(3)$$ {S}_n^{(3)} $$ the 3‐uniform hypergraph on n+1$$ n+1 $$ vertices consisting of all n2$$ \left(\genfrac{}{}{0ex}{}{n}{2}\right) $$ 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 r(K4(3),Sn(3))$$ r\left({K}_4^{(3)},{S}_n^{(3)}\right) $$ exhibits an unusual intermediate growth rate, namely, 2clog2n≤r(K4(3),Sn(3))≤2c′n2/3logn,$$ {2}^{c\log^2n}\le r\left({K}_4^{(3)},{S}_n^{(3)}\right)\le {2}^{c^{\prime }{n}^{2/3}\log n}, $$for some positive constants c$$ c $$ and c′$$ {c}^{\prime } $$. The proof of these bounds brings in a novel Ramsey problem on grid graphs which may be of independent interest: what is the minimum N$$ N $$ such that any 2‐edge‐coloring of the Cartesian product KN□KN$$ {K}_N\square {K}_N $$ contains either a red rectangle or a blue Kn$$ {K}_n $$? [ABSTRACT FROM AUTHOR]

A k‐uniform hypergraph with n vertices is an (n,k,ℓ)$$ \left(n,k,\ell \right) $$‐omitting system if it has no two edges with intersection size ℓ$$ \ell $$. If in addition it has no two edges with intersection size greater than ℓ$$ \ell $$, then it is an (n,k,ℓ)$$ \left(n,k,\ell \right) $$‐system. Rödl and Šiňajová proved a sharp lower bound for the independence number of (n,k,ℓ)$$ \left(n,k,\ell \right) $$‐systems. We consider the same question for (n,k,ℓ)$$ \left(n,k,\ell \right) $$‐omitting systems. Our proofs use adaptations of the random greedy independent set algorithm, and pseudorandom graphs. We also prove related results where we forbid more than two edges with a prescribed common intersection size leading to some applications in Ramsey theory. For example, we obtain good bounds for the Ramsey number rk(F,t)$$ {r}_k\left(F,t\right) $$, where F is the k‐uniform Fan. The behavior is quite different than the case k=2$$ k=2 $$ which is the classical Ramsey number r(3,t)$$ r\left(3,t\right) $$. [ABSTRACT FROM AUTHOR]

The triangle covering number of a graph is the minimum number of vertices that hit all triangles. Given positive integers s,t and an n‐vertex graph G with ⌊n2∕4⌋+t edges and triangle covering number s, we determine (for large n) sharp bounds on the minimum number of triangles in G and also describe the extremal constructions. Similar results are proved for cliques of larger size and color critical graphs. This extends classical work of Rademacher, Erdős, and Lovász–Simonovits whose results apply only to s≤t. Our results also address two conjectures of Xiao and Katona. We prove one of them and give a counterexample and prove a modified version of the other conjecture. [ABSTRACT FROM AUTHOR]

Given s⩾k⩾3, let h(k)(s) be the minimum t such that there exist arbitrarily large k‐uniform hypergraphs H whose independence number is at most polylogarithmic in the number of vertices and in which every s vertices span at most t edges. Erdős and Hajnal conjectured (1972) that h(k)(s) can be calculated precisely using a recursive formula and Erdős offered $500 for a proof of this. For k=3, this has been settled for many values of s including powers of three but it was not known for any k⩾4 and s⩾k+2. Here we settle the conjecture for all s⩾k⩾4. We also answer a question of Bhat and Rödl by constructing, for each k⩾4, a quasirandom sequence of k‐uniform hypergraphs with positive density and upper density at most k!/(kk−k). This result is sharp. [ABSTRACT FROM AUTHOR]

Motivated by the Erdős–Szekeres convex polytope conjecture in Rd, we initiate the study of the following induced Ramsey problem for hypergraphs. Given integers n>k⩾5, what is the minimum integer gk(n) such that any k ‐uniform hypergraph on gk(n) vertices with the property that any set of k+1 vertices induces 0, 2, or 4 edges, contains an independent set of size n. Our main result shows that gk(n)>2cnk−4, where c=c(k). [ABSTRACT FROM AUTHOR]

Abstract: We provide several constructions for problems in Ramsey theory. First, we prove a superexponential lower bound for the classical 4‐uniform Ramsey number r 4 ( 5 , n ), and the same for the iterated ( k − 4 )‐fold logarithm of the k‐uniform version r k ( k + 1 , n ). This is the first improvement of the original exponential lower bound for r 4 ( 5 , n ) implicit in work of Erdős and Hajnal from 1972 and also improves the current best known bounds for larger k due to the authors. Second, we prove an upper bound for the hypergraph Erdős–Rogers function f k + 1 , k + 2 k ( N ) that is an iterated ( k − 13 )‐fold logarithm in N. This improves the previous upper bounds that were only logarithmic and addresses a question of Dudek and the first author that was reiterated by Conlon, Fox and Sudakov. Third, we generalize the results of Erdős and Hajnal about the 3‐uniform Ramsey number of K 4 minus an edge versus a clique to k‐uniform hypergraphs. [ABSTRACT FROM AUTHOR]

Abstract: The Ramsey number r k ( s , n ) is the minimum N such that for every red–blue coloring of the k‐tuples of { 1 , … , N }, there are s integers such that every k‐tuple among them is red, or n integers such that every k‐tuple among them is blue. We prove the following new lower bounds for 4‐uniform hypergraph Ramsey numbers: r 4 ( 5 , n ) > 2 n c log n and r 4 ( 6 , n ) > 2 2 c n 1 / 5, where c is an absolute positive constant. This substantially improves the previous best bounds of 2 n c log log n and 2 n c log n, respectively. Using previously known upper bounds, our result implies that the growth rate of r 4 ( 6 , n ) is double exponential in a power of n. As a consequence, we obtain similar bounds for the k‐uniform Ramsey numbers r k ( k + 1 , n ) and r k ( k + 2 , n ), where the exponent is replaced by an appropriate tower function. This almost solves the question of determining the tower growth rate for all classical off‐diagonal hypergraph Ramsey numbers, a question first posed by Erdős and Hajnal in 1972. The only problem that remains is to prove that r 4 ( 5 , n ) is double exponential in a power of n. [ABSTRACT FROM AUTHOR]

The size-Ramsey number of a graph G is the minimum number of edges in a graph H such that every 2-edge-coloring of H yields a monochromatic copy of G. Size-Ramsey numbers of graphs have been studied for almost 40 years with particular focus on the case of trees and bounded degree graphs. We initiate the study of size-Ramsey numbers for k-uniform hypergraphs. Analogous to the graph case, we consider the size-Ramsey number of cliques, paths, trees, and bounded degree hypergraphs. Our results suggest that size-Ramsey numbers for hypergraphs are extremely difficult to determine, and many open problems remain. [ABSTRACT FROM AUTHOR]

We show that, for a natural notion of quasirandomness in k-uniform hypergraphs, any quasirandom k-uniform hypergraph on n vertices with constant edge density and minimum vertex degree Ω( n k-1) contains a loose Hamilton cycle. We also give a construction to show that a k-uniform hypergraph satisfying these conditions need not contain a Hamilton ℓ-cycle if k- ℓ divides k. The remaining values of ℓ form an interesting open question. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 363-378, 2016 [ABSTRACT FROM AUTHOR]

We produce an edge-coloring of the complete 3-uniform hypergraph on n vertices with [ABSTRACT FROM AUTHOR]

For s ⩾ 4, the 3-uniform tight cycle C3s has vertex set corresponding to s distinct points on a circle and edge set given by the s cyclic intervals of three consecutive points. For fixed s ⩾ 4 and s ≢ 0 (mod 3), we prove that there are positive constants a and b with 2at < r(C3s,K3t ) < 2bt2 log t. The lower bound is obtained via a probabilistic construction. The upper bound for s > 5 is proved by using supersaturation and the known upper bound for r(K34,K3t ), while for s = 5 it follows from a new upper bound for r(K3-5 ,K3t ) that we develop. [ABSTRACT FROM AUTHOR]

A triangle in a hypergraph is a collection of distinct vertices u, v, w and distinct edges e, f, g with [ABSTRACT FROM AUTHOR]

Chung and Graham began the systematic study of k-uniform hypergraph quasirandom properties soon after the foundational results of Thomason and Chung-Graham-Wilson on quasirandom graphs. One feature that became apparent in the early work on k-uniform hypergraph quasirandomness is that properties that are equivalent for graphs are not equivalent for hypergraphs, and thus hypergraphs enjoy a variety of inequivalent quasirandom properties. In the past two decades, there has been an intensive study of these disparate notions of quasirandomness for hypergraphs, and an open problem that has emerged is to determine the relationship between them. Our main result is to determine the poset of implications between these quasirandom properties. This answers a recent question of Chung and continues a project begun by Chung and Graham in their first paper on hypergraph quasirandomness in the early 1990's. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46,762-800, 2015 [ABSTRACT FROM AUTHOR]

Let [ABSTRACT FROM AUTHOR]

The well-known Ramsey number [ABSTRACT FROM AUTHOR]

The independence number [ABSTRACT FROM AUTHOR]