Abstract. We study the extremal number for paths in [Formula: see text]-uniform hypergraphs where two consecutive edges of the path intersect alternately in sets of sizes [Formula: see text] and [Formula: see text] with [Formula: see text] 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 [Formula: see text]-paths that have an odd number of edges or that have an even number of edges and [Formula: see text]. This generalizes the Erdős–Gallai theorem for graphs, which is the case of [Formula: see text]. 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 [Formula: see text]-path of length 4 using the different [Formula: see text]-systems method.

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 $e_1,e_2,\dots,e_k$ such that $e_1 \cap e_2, e_2 \cap e_3,\dots,e_k \cap e_1$ has a system of distinct representatives and $e_1 \cap e_2 \cap \dots \cap e_k = \emptyset$. In the case that all the sets $e_i$ have size three, let $\mathcal{B}_k$ denote the family of all nontrivial Berge $k$-cycles. The Ramsey numbers $R(t,\mathcal{B}_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, \mathcal{B}_{2k}) \leq t^{1 + \frac{1}{2k-1} + \frac{2}{\sqrt{\log t}}}$, and moreover, we show that if a conjecture of Erdös and Simonovits [ Combinatorica, 2 (1982), pp. 275--288] on girth in graphs is true, then this is tight up to a factor $t^{o(1)}$ as $t \rightarrow \infty$.

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.

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$ edges and $G$ is an $n$-vertex $r$-uniform hypergraph containing no copy of $T$, then $G$ has at most $\frac{t-1}{r}\binom{n}{r-1}$ 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\ge 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 Ser. 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.

The expansion $G^+$ of a graph $G$ is the 3-uniform hypergraph obtained from $G$ by enlarging each edge of $G$ with a new vertex disjoint from $V(G)$ such that distinct edges are enlarged by distinct vertices. Let ${ex}_3(n,F)$ denote the maximum number of edges in a 3-uniform hypergraph with $n$ vertices not containing any copy of a 3-uniform hypergraph $F$. The study of ${ex}_3(n,G^+)$ includes some well-researched problems, including the case that $F$ consists of $k$ disjoint edges, $G$ is a triangle, $G$ is a path or cycle, and $G$ is a tree. In this paper we initiate a broader study of the behavior of ${ex}_3(n,G^+)$. Specifically, we show $ {ex}_3(n,K_{s,t}^+) = \Theta(n^{3 - 3/s})$ whenever $t > (s - 1)!$ and $s \geq 3$. One of the main open problems is to determine for which graphs $G$ the quantity ${ex}_3(n,G^+)$ is quadratic in $n$. We show that this occurs when $G$ is any bipartite graph with Turán number $o(n^{\varphi})$ where $\varphi = \frac{1 + \sqrt{5}}{2}$, and in particular this shows ${ex}_3(n,G^+) = O(n^2)$ when $G$ is the three-dimensional cube graph.

We investigate the natural situation of the dissemination of information on various graph classes starting with a random set of informed vertices called active. Initially active vertices are chosen independently with probability p, and at any stage in the process, a vertex becomes active if the majority of its neighbours are active, and thereafter never changes its state. This process is a particular case of bootstrap percolation. We show that in any cubic graph, with high probability, the information will not spread to all vertices in the graph if $p<\frac{1}{2}$ . We give families of graphs in which information spreads to all vertices with high probability for relatively small values of p.

The cycle packing number ν e ( G ) of a graph G is the maximum number of pairwise edge-disjoint cycles in G . Computing ν e ( G ) is an NP-hard problem. We present approximation algorithms for computing ν e ( G ) in both undirected and directed graphs. In the undirected case we analyze a variant of the modified greedy algorithm suggested by Caprara et al. [2003] and show that it has approximation ratio Θ(√log n ), where n = | V ( G )|. This improves upon the previous O (log n ) upper bound for the approximation ratio of this algorithm. In the directed case we present a √ n -approximation algorithm. Finally, we give an O ( n 2/3 )-approximation algorithm for the problem of finding a maximum number of edge-disjoint cycles that intersect a specified subset S of vertices. We also study generalizations of these problems. Our approximation ratios are the currently best-known ones and, in addition, provide upper bounds on the integrality gap of standard LP-relaxations of these problems. In addition, we give lower bounds for the integrality gap and approximability of ν e ( G ) in directed graphs. Specifically, we prove a lower bound of Ω(log n /loglog n ) for the integrality gap of edge-disjoint cycle packing. We also show that it is quasi-NP-hard to approximate ν e ( G ) within a factor of O (log 1 − ε n ) for any constant ε > 0. This improves upon the previously known APX-hardness result for this problem.

Let NF;(n, k, r) denote the maximum number of columns in an n-row matrix with entries in a finite field F in which each column has at most r nonzero entries and every k columns are linearly independent over F. Such sparse parity check matrices are fundamental tools in coding theory, derandomization and complexity theory. We obtain near-optimal theoretical upper bounds for NF(n, k, r) in the important case k > r, i.e. when the number of correctible errors is greater than the weight. Namely, we show that NF(n, k, r) = O(n(r/2)+(4r/3k)). The best known (probabilistic) lower bound is NF(n, k, r) = Omega(n(r/2)+(r/(2k-2))), while the best known upper bound in the case k > r was for k a power of 2, in which case NF(n, k, r) = Omega(n(r/2)+(1/2)). Our method is based on a novel reduction of the problem to the extremal problem for cycles in graphs, and yields a fast algorithm for finding short linear dependences in large sets of sparse vectors. In the full version of this paper we present additional applications of this method to problems in combinatorial number theory