Abstract. We consider three extremal problems about the number of copies of a fixed graph in another larger graph. First, we correct an error in a result of Reiher and Wagner [ Studia Sci. Math. Hungar., 55 (2018), pp. 238–259] and prove that the number of [Formula: see text]-edge stars in a graph with density [Formula: see text] is asymptotically maximized by a clique and isolated vertices or its complement. Next, among ordered [Formula: see text]-vertex graphs with [Formula: see text] edges, we determine the maximum and minimum number of copies of a [Formula: see text]-edge star whose nonleaf vertex is minimum among all vertices of the star. Finally, for [Formula: see text], we define a particular three-edge-colored complete graph [Formula: see text] on [Formula: see text] vertices with colors blue, green, and red and determine, for each [Formula: see text] with [Formula: see text] and [Formula: see text], the maximum density of [Formula: see text] in a large graph whose blue, green, and red edge sets have densities [Formula: see text], and [Formula: see text], respectively. These are the first nontrivial examples of colored graphs for which such complete results are proved.

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.

An $(n,s,q)$-graph is an $n$-vertex multigraph where every set of $s$ vertices spans at most $q$ edges. In this paper, we determine the maximum product of the edge multiplicities in $(n,s,q)$-graphs if the congruence class of $q$ modulo ${s\choose 2}$ is in a certain interval of length about $3s/2$. The smallest case that falls outside this range is $(s,q)=(4,15)$, and here the answer is $a^{n^2+o(n^2)}$, where $a$ is transcendental assuming Schanuel's conjecture. This could indicate the difficulty of solving the problem in full generality. Many of our results can be seen as extending work by Bondy and Tuza [ J. Graph Theory, 25 (1997), pp. 267--275] and Füredi and Kündgen [ J. Graph Theory, 40 (2002), pp. 195--225] about sums of edge multiplicities to the product setting. We also prove a variety of other extremal results for $(n,s,q)$-graphs, including product-stability theorems. These results are of additional interest because they can be used to enumerate $(n,s,q)$-graphs. Our work therefore extends many classical enumerative results in extremal graph theory beginning with the Erdös--Kleitman--Rothschild theorem [ Asymptotic enumeration of $K\sb{n}$-free graphs, in Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo II, Atti dei Convegni Lincei 17, Accad. Naz. Lincei, Rome, 1976, pp. 19--27] to multigraphs.

Abstract Fix an integer $r \ge 3$ . We consider metric spaces on n points such that the distance between any two points lies in $\left\{ {1, \ldots ,r} \right\}$ . Our main result describes their approximate structure for large n. As a consequence, we show that the number of these metric spaces is $\left\lceil {{{r + 1} \over 2}} \right\rceil ^{\left( {\matrix{ n \cr 2 \cr } } \right) + o\left( {n^2 } \right)} .$ Related results in the continuous setting have recently been proved by Kozma, Meyerovitch, Peled, and Samotij [34]. When r is even, our structural characterization is more precise and implies that almost all such metric spaces have all distances at least $r/2$ . As an easy consequence, when r is even, we improve the error term above from $o\left( {n^2 } \right)$ to $o\left( 1 \right)$ , and also show a labeled first-order 0-1 law in the language ${\cal L}_r $ , consisting of r binary relations, one for each element of $[r]$ . In particular, we show the almost sure theory T is the theory of the Fraïssé limit of the class of all finite simple complete edge-colored graphs with edge colors in $\left\{ {r/2, \ldots ,r} \right\}$ . Our work can be viewed as an extension of a long line of research in extremal combinatorics to the colored setting, as well as an addition to the collection of known structures that admit logical 0-1 laws.

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.

Fix $k \geq 3$, and let $G$ be a $k$-uniform hypergraph with maximum degree $\Delta$. Suppose that for each $l = 2, \dots, k-1$, every set of $l$ vertices of $G$ is in at most $\Delta^{\frac{k-l}{k-1}}/f$ edges. Then the chromatic number of $G$ is $O((\frac{\Delta}{\log f})^{\frac{1}{k-1}})$. This extends results of Frieze and the second author [J. Combin. Theory. Ser. B, 103 (2013), pp. 767--794] and Bennett and Bohman [arXiv:1308:3732, 2013]. A similar result is proved for 3-uniform hypergraphs where every vertex lies in few triangles. This generalizes a result of Alon, Krivelevich, and Sudakov [J. Combin. Theory Ser. B, 77 (1999), pp. 73--82], who proved the result for graphs. Our main new technical contribution is a deviation inequality for positive random variables with expectation less than $1$. This may be of independent interest and have further applications.

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.

In this paper we consider spectral extremal problems for hypergraphs. We give two general criteria under which such results may be deduced from “strong stability” forms of the corresponding (pure) extremal results. These results hold for the $\alpha$-spectral radius defined using the $\alpha$-norm for any $\alpha>1$; the usual spectral radius is the case $\alpha=2$. Our results imply that any hypergraph Turán problem which has the stability property and whose extremal construction satisfies some rather mild continuity assumptions admits a corresponding spectral result. A particular example is to determine the maximum $\alpha$-spectral radius of any 3-uniform hypergraph on $n$ vertices not containing the Fano plane, when $n$ is sufficiently large. Another is to determine the maximum $\alpha$-spectral radius of any graph on $n$ vertices not containing some fixed color-critical graph, when $n$ is sufficiently large; this generalizes a theorem of Nikiforov who proved stronger results in the case $\alpha=2$. We also obtain an $\alpha$-spectral version of the Erdös--Ko--Rado theorem on $t$-intersecting $k$-uniform hypergraphs.

We obtain new lower bounds for the independence number of $K_r$-free graphs and linear $k$-uniform hypergraphs in terms of the degree sequence. This answers some old questions raised by Caro and Tuza [J. Graph Theory, 15 (1991), pp. 99--107]. Our proof technique is an extension of a method of Caro [New Results on the Independence Number, Technical report, Tel Aviv University, 1979] and Wei [A Lower Bound on the Stability Number of a Simple Graph, TM 81-11217-9, Bell Laboratories, Berkley Heights, NJ, 1981], and we also give a new short proof of the main result of Caro and Tuza using this approach. As byproducts, we also obtain some nontrivial identities involving binomial coefficients, which may be of independent interest.

Let $\mathcal{F}$ be a k‐uniform set system defined on a ground set of size n with no singleton intersection; i.e., no pair $A,B\in\mathcal{F}$ has $|A\cap B|=1$. Frankl showed that $|\mathcal{F}|\leq\binom{n-2}{k-2}$ for $k\geq4$ and n sufficiently large, confirming a conjecture of Erdo˝s and Sós. We determine the maximum size of $\mathcal{F}$ for $k=4$ and all n, and also establish a stability result for general k, showing that any $\mathcal{F}$ with size asymptotic to that of the best construction must be structurally similar to it.

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.