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]

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

For fixed s≥3, we prove that if optimal Ks-free pseudorandom graphs exist, then the Ramsey number r(s,t) is t s−1+o(1) as t→∞. Our method also improves the best lower bounds for r(Cℓ ​,t) obtained by Bohman and Keevash from the random Cℓ-free process by polylogarithmic factors for all odd ℓ≥5 and ℓ∈{6,10}. For ℓ=4 it matches their lower bound from the C4-free process. We also prove, via a different approach, that r(C5,t)>(1+o(1))t 11/8 and r(C7 ​,t)>(1+o(1))t 11/9 . These improve the exponent of t in the previous best results and appear to be the first examples of graphs F with cycles for which such an improvement of the exponent for r(F,t) is shown over the bounds given by the random F-free process and random graphs. [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]

We study the extremal number for paths in r-uniform hypergraphs where two consecutive edges of the path intersect alternately in sets of sizes b and a with a+b = r and all other pairs of edges have empty intersection. Our main result, which is about hypergraphs that are blowups of trees, determines asymptotically the extremal number of these (a, b)-paths that have an odd number of edges or that have an even number of edges and a >b. This generalizes the Erd\H os--Gallai theorem for graphs, which is the case of a = b = 1. Our proof method involves a novel twist on Katona's permutation method, where we partition the underlying hypergraph into two parts, one of which is very small. We also find the asymptotics of the extremal number for the (1, 2)-path of length 4 using the different-systems method. [ABSTRACT FROM AUTHOR]

Morris and Saxton used the method of containers to bound the number of n‐vertex graphs with m edges containing no ℓ‐cycles, and hence graphs of girth more than ℓ. We consider a generalization to r‐uniform hypergraphs. The girth of a hypergraph H is the minimum ℓ≥2 such that there exist distinct vertices v1,...,vℓ and hyperedges e1,...,eℓ with vi,vi+1∈ei for all 1≤i≤ℓ. Letting Nmr(n,ℓ) denote the number of n‐vertex r‐uniform hypergraphs with m edges and girth larger than ℓ and defining λ=⌈(r−2)∕(ℓ−2)⌉, we show Nmr(n,ℓ)≤Nm2(n,ℓ)r−1+λ, which is tight when ℓ−2 divides r−2 up to a 1+o(1) term in the exponent. This result is used to address the extremal problem for subgraphs of girth more than ℓ in random r‐uniform hypergraphs. [ABSTRACT FROM AUTHOR]

In this paper, we consider an extension of cycle-complete graph Ramsey numbers to Berge cycles in hypergraphs: for k \geq 2, a nontrivial Berge k-cycle is a family of sets e1, e2, . . ., ek such that e1\cap e2, e2\cap e3, . . ., ek\cap e1 has a system of distinct representatives and e1\cap e2\cap \cdot \cdot \cdot \cap ek = \emptyset. In the case that all the sets ei have size three, let \scrB k denote the family of all nontrivial Berge k-cycles. The Ramsey numbers R(t, \scrB k) denote the minimum n such that every n-vertex 3-uniform hypergraph contains either a nontrivial Berge k-cycle or an independent set of size t. We prove R(t, \scrB 2k) \leq t 1+ 1 2k 1+\surd 2 log t, and moreover, we show that if a conjecture of Erd\H os and Simonovits [Combinatorica, 2 (1982), pp. 275--288] on girth in graphs is true, then this is tight up to a factor to(1) as t \rightarrow \infty. [ABSTRACT FROM AUTHOR]

In this paper, we consider a randomized greedy algorithm for independent sets in r‐uniform d‐regular hypergraphs G on n vertices with girth g. By analyzing the expected size of the independent sets generated by this algorithm, we show that α(G)≥(f(d,r)−ϵ(g,d,r))n, where ϵ(g,d,r) converges to 0 as g → ∞ for fixed d and r, and f(d, r) is determined by a differential equation. This extends earlier results of Garmarnik and Goldberg for graphs [8]. We also prove that when applying this algorithm to uniform linear hypergraphs with bounded degree, the size of the independent sets generated by this algorithm concentrate around the mean asymptotically almost surely. [ABSTRACT FROM AUTHOR]

For two graphs $F$ and $H$, the relative Turán number ${ex}(H,F)$ is the maximum number of edges in an $F$-free subgraph of $H$. Foucaud, Krivelevich, and Perarnau [SIAM J. Discrete Math., 29 (2015), pp. 65--78] and Perarnau and Reed [Combin. Probab. Comput., 26 (2017), pp. 448--467] studied these quantities as a function of the maximum degree of $H$. In this paper, we study a generalization for uniform hypergraphs. If $F$ is a complete $r$-partite $r$-uniform hypergraph with parts of sizes $s_1,s_2,\dots,s_r$ with each $s_{i + 1}$ sufficiently large relative to $s_i$, then with $1/\beta = \sum_{i = 2}^r \prod_{j = 1}^{i - 1} s_j$ we prove that for any $r$-uniform hypergraph $H$ with maximum degree $\Delta$, ${ex}(H,F)\ge \Delta^{-\beta - o(1)} \cdot e(H).$ This is tight as $\Delta \rightarrow \infty$ up to the $o(1)$ term in the exponent, since we show there exists a $\Delta$-regular $r$-graph $H$ such that ${ex}(H,F)=O(\Delta^{-\beta}) \cdot e(H)$. Similar tight results are obtained when $H$ is the random $n$-vertex $r$-graph $H_{n,p}^r$ with edge-probability $p$, extending results of Balogh and Samotij [J. Lond. Math. Soc., 83 (2011), pp. 1091--1094] and Morris and Saxton [Adv. Math., 298 (2016), pp. 534--580]. General lower bounds for a wider class of $F$ are also obtained. [ABSTRACT FROM AUTHOR]

An r -uniform hypergraph is a tight r-tree if its edges can be ordered so that every edge e contains a vertex v that does not belong to any preceding edge and the set e - v lies in some preceding edge. A conjecture of Kalai personal communication published in Frankl and Füredi, J. Combin. Theory Ser. A, 45 (1987), pp. 226--262, generalizing the Erdõs-Sós conjecture for trees, asserts that if T is a tight r -tree with t edge\bigr)s and G is an n-vertex r-uniform hypergraph containing no copy of T, then G has at most t--1/r(n r-i) edges. A trunk T' of a tight r-tree T is a tight subtree such that every edge of T - T' has r - 1 vertices in some edge of T' and a vertex outside T'. For r ≥ 3, the only nontrivial family of tight r-trees for which this conjecture has been proved is the family of r-trees with trunk size one in J. Combin. Theory Se r. A, 45 (1987), pp. 226--262. Our main result is an asymptotic version of Kalai's conjecture for all tight trees T of bounded trunk size. This follows from our upper bound on the size of a T-free r-uniform hypergraph G in terms of the size of its shadow. We also give a short proof of Kalai's conjecture for tight r-trees with at most four edges. In particular, for 3-uniform hypergraphs, our result on the tight path of length 4 implies the intersection shadow theorem of Katona Acta Math. Acad. Sci. Hungar., 15 (1964), pp. 329--337. [ABSTRACT FROM AUTHOR]

Abstract: Let G = ( V , E ) be a graph of density p on n vertices. Following Erdős, Łuczak, and Spencer, an m‐vertex subgraph H of G is called full if H has minimum degree at least p ( m − 1 ). Let f ( G ) denote the order of a largest full subgraph of G. If p n 2 is a nonnegative integer, define f ( n , p ) = min { f ( G ) : | V ( G ) | = n , | E ( G ) | = p n 2 } .Erdős, Łuczak, and Spencer proved that for n ≥ 2, ( 2 n ) 1 2 − 2 ≤ f ( n , 1 2 ) ≤ 4 n 2 3 ( log n ) 1 3 .In this article, we prove the following lower bound: for n − 2 3 < p n < 1 − n − 1 7, f ( n , p ) ≥ 1 4 ( 1 − p ) 2 3 n 2 3 − 1 .Furthermore, we show that this is tight up to a multiplicative constant factor for infinitely many p near the elements of { 1 2 , 2 3 , 3 4 , ⋯ }. In contrast, we show that for any n‐vertex graph G, either G or G c contains a full subgraph on Ω ( n log n ) vertices. Finally, we discuss full subgraphs of random and pseudo‐random graphs, and several open problems. [ABSTRACT FROM AUTHOR]