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.

Abstract. The celebrated dependent random choice lemma states that in a bipartite graph, an average vertex (weighted by its degree) has the property that almost all small subsets [Formula: see text] in its neighborhood have a common neighborhood almost as large as in the random graph of the same edge-density. There are two well-known applications of this lemma. The first is a theorem of Füredi [ Combinatorica, 11 (1991), pp. 75–79] and Alon, Krivelevich, and Sudakov [ Combin. Probab. Comput., 12 (2003), pp. 477–494] showing that the maximum number of edges in an [Formula: see text]-vertex graph not containing a fixed bipartite graph with maximum degree at most [Formula: see text] on one side is [Formula: see text]. This was recently extended by Grzesik, Janzer, and Nagy [ J. Combin. Theory Ser. B, 156 (2022), pp. 299–309] to the family of so-called [Formula: see text]-blowups of a tree. A second application is a theorem of Conlon, Fox, and Sudakov [ Geom. Funct. Anal., 20 (2010), pp. 1354–1366], confirming a special case of a conjecture of Erdős and Simonovits and of Sidorenko, showing that if [Formula: see text] is a bipartite graph that contains a vertex that is completely joined to the other part and [Formula: see text] is a graph, then the probability that the uniform random mapping from [Formula: see text] to [Formula: see text] is a homomorphism is at least [Formula: see text]. In this paper, we introduce a nested variant of the dependent random choice lemma, which might be of independent interest. We then apply it to obtain a common extension of the theorem of Conlon, Fox, and Sudakov and the theorem of Grzesik, Janzer, and Nagy regarding Turán and Sidorenko properties of so-called tree-degenerate graphs.

Given a graph $H$, the Turán number $\mathrm{ex}(n,H)$ is the largest number of edges in an $H$-free graph on $n$ vertices. We make progress on a recent conjecture of Conlon, Janzer, and Lee [ More on the Extremal Number of Subdivisions, arXiv:1903.10631v1, 2019] on the Turán numbers of bipartite graphs, which in turn yields further progress on a conjecture of Erdös and Simonovits [ Combinatorica, 1 (1981), pp. 25--42]. Let $s,t,k\geq 2$ be integers. Let $K_{s,t}^k$ denote the graph obtained from the complete bipartite graph $K_{s,t}$ by replacing each edge $uv$ in it with a path of length $k$ between $u$ and $v$ such that the $st$ replacing paths are internally disjoint. It follows from a general theorem of Bukh and Conlon [J. Eur. Math. Soc. (JEMS), 20 (2018), pp. 1747--1757] that $\mathrm{ex}(n,K_{s,t}^k)=\Omega(n^{1+\frac{1}{k}-\frac{1}{sk}})$. Conlon, Janzer, and Lee recently conjectured that for any integers $s,t,k\geq 2$, $\mathrm{ex}(n,K_{s,t}^k)=O(n^{1+\frac{1}{k}-\frac{1}{sk}})$. Among many other things, they settled the $k=2$ case of their conjecture. As the main result of this paper, we prove their conjecture for $k=3,4$. Our main results also yield infinitely many new so-called Turán exponents: rationals $r\in (1,2)$ for which there exists a bipartite graph $H$ with $\mathrm{ex}(n, H)=\Theta(n^r)$, adding to the lists recently obtained by Jiang, Ma, and Yepremyan [ On Turán Exponents of Bipartite Graphs, arXiv:1806.02838, 2018], by Kang, Kim, and Liu [ On the Rational Turán Exponent Conjecture, arXiv:1811.06916, 2018], and by Conlon, Janzer, and Lee. Our method builds on an extension of the Conlon--Janzer--Lee method. We also note that the extended method also gives a weaker version of the Conlon--Janzer--Lee conjecture for all $k\geq 2$.

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.

Given a positive integer $n$ and a graph $F$, the Turán number $ex(n,F)$ is the maximum number of edges in an $n$-vertex simple graph that does not contain $F$ as a subgraph. Let $H$ be a graph and $p$ a positive even integer. Let $H^{(p)}$ denote the graph obtained from $H$ by subdividing each of its edges $p-1$ times. We prove that $ex(n,H^{(p)})=O(n^{1+(16/p)})$. This follows from a more general result that we establish, where different edges of $H$ are allowed to be subdivided different numbers of times. Our result is closely related to the results of Jiang [J. Graph Theory, 67 (2011), pp. 139--152] and of Kostochka and Pyber [Combinatorica, 8 (1988), pp. 83--86] on topological minors.

Given a set S of vertices in a connected graph G, the classic Steiner tree problem asks for the minimum number of edges of a connected subgraph of G that contains S. We study this problem in the hypercube. Given a set S of vertices in the n-dimensional hypercube $Q_n$, the Steiner cost of S, denoted by $cost(S)$, is the minimum number of edges among all connected subgraphs of $Q_n$ that contain S. We obtain the following results on $cost(S)$. Let $\epsilon$ be any given small, positive constant, and set $k=|S|$. (1) [upper bound] For every set S we have $cost(S) < (\frac{1}{3}k + 1 + \frac{1}{2}\ln k)n.$ In particular, there is a constant $c_1$ depending only on $\epsilon$ such that if $k > c_1$, then $cost(S) < (\frac{1}{3} + \epsilon)kn.$ (2) We develop a randomized algorithm of running time $O(kn)$ that produces a connected subgraph H of $Q_n$ containing S such that with probability approaching 1 as $k,n\to\infty$ we have $|E(H)| < (\frac{1}{3} + \epsilon)kn$. (3) [lower bound] There are constants $c_2$ and b (with $1 (\frac{1}{3} - \epsilon)kn$. Thus for k in this range with $k\to \infty$, the upper bound (1) is asymptotically tight. We also show that for fixed k, as $n\to \infty$, almost always a random family of k vertices in $Q_n$ satisfies $[\frac{k}{3}+\frac{2}{9}(-1+(-\frac{1}{2})^k)] n - \sqrt{n\ln n}\leq cost (S)\leq [\frac{k}{3}+\frac{2}{9}(-1+(-\frac{1}{2})^k)] n + \sqrt{n\ln n}.$

A d-simplex is a collection of $d+1$ sets such that every d of them have nonempty intersection and the intersection of all of them is empty. A strong d-simplex is a collection of $d+2$ sets $A,A_1,\dots,A_{d+1}$ such that $\{A_1,\dots,A_{d+1}\}$ is a d-simplex, while A contains an element of $\cap_{j\neq i}A_j$ for each i, $1\leq i\leq d+1$. Mubayi and Ramadurai [Combin. Probab. Comput., 18 (2009), pp. 441–454] conjectured that if $k\geq d+1\geq3$, $n>k(d+1)/d$, and $\mathcal{F}$ is a family of k-element subsets of an n-element set that contains no strong d-simplex, then $|\mathcal{F}|\leq{n-1\choose k-1}$ with equality only when $\mathcal{F}$ is a star. We prove their conjecture when $k\geq d+2$ and n is large. The case $k=d+1$ was solved in [M. Feng and X. J. Liu, Discrete Math., 310 (2010), pp. 1645–1647] and [Z. Füredi, private communication, St. Paul, MN, 2010]. Our result also yields a new proof of a result of Frankl and Füredi [J. Combin. Theory Ser. A, 45 (1987), pp. 226–262] when $k\geq d+2$ and n is large.

The edge-bandwidth $B'(G)$ of a graph G is the bandwidth of the line graph of G. More specifically, for any bijection $f: E(G)\to \{1,2,\ldots, |E(G)|\}$, let $B'(f,G)=\max\{|f(e_1)- f(e_2)|: \mbox{$e1$ and $e2$ are incident edges of G}\}$, and let $B'(G)=\min_f B'(f,G)$. We determine asymptotically the edge-bandwidth of d-dimensional grids $P_n^d$ and of the Hamming graph $K_n^d$, the d-fold Cartesian product of $K_n$. Our results are as follows. (i) For fixed d and $n\to \infty$, $B'(P_n^d)=c(d)d n^{d-1}+O(n^{d-{3\over2}})$, where $c(d)$ is a constant depending on d, which we determine explicitly. (ii) For fixed even n and $d\to \infty$, $B'(K_n^d)=(1+o(1))\sqrt{d\over {2\pi}}\, n^d (n-1)$. Our results extend recent results by Balogh, Mubayi, and Pluhár [Theoret. Comput. Sci., 359 (2006), pp. 43–57], who determined $B'(P_n^2)$ asymptotically as a function of n and $B'(K_2^d)$ asymptotically as a function of d.

Given positive integers n and d, let A/sub 2/(n,d) denote the maximum size of a binary code of length n and minimum distance d. The well-known Gilbert-Varshamov bound asserts that A/sub 2/(n,d)/spl ges/2/sup n//V(n,d-l), where V(n,d) = /spl sigma//sub i=0//sup d/(/sub i//sup n/) is the volume of a Hamming sphere of radius d. We show that, in fact, there exists a positive constant c such that A/sub 2/(n, d)/spl ges/c2/sup n//V(n,d-1)log/sub 2/V(n, d-1) whenever d/n/spl les/0.499. The result follows by recasting the Gilbert-Varshamov bound into a graph-theoretic framework and using the fact that the corresponding graph is locally sparse. Generalizations and extensions of this result are briefly discussed.

Subsequent to the publication of this article in SIAM J. Discrete Math., 12 (1999), pp. 307--316, an error in one of the authors' affiliations was discovered. The correct affiliation follows: Tao Jiang, Department of Mathematics, University of Illinois, Urbana, IL 61801-2975 ([email protected]). Due to the serious nature of this mistake, a sticker containing the correct affiliation was printed and mailed to all print subscribers. This sticker should be placed over the footnotes on page 307 of volume 12 (1999), issue 3. A corrected version of the electronic file was posted to http://epubs.siam.org/sam-bin/dbq/article/33075 on December 13, 1999. SIAM sincerely regrets this error.

The edge-bandwidth of a graph is the minimum, over all labelings of the edges with distinct integers, of the maximum difference between labels of two incident edges. We prove that edge-bandwidth is at least as large as bandwidth for every graph, with equality for certain caterpillars. We obtain sharp or nearly sharp bounds on the change in edge-bandwidth under addition, subdivision, or contraction of edges. We compute edge-bandwidth for K n , K n,n , caterpillars, and some theta graphs.