Abstract. Determining the maximum number of edges in an intersecting hypergraph on a fixed ground set under additional constraints is one of the central topics in extremal combinatorics. In contrast, there are few results on analogous problems concerning the maximum order of such hypergraphs. In this paper, we systematically study these vertex analogues.

We give some natural sufficient conditions for balls in a metric space to have small intersection. Roughly speaking, this happens when the metric space is (i) expanding and (ii) well-spread, and (iii) a certain random variable on the boundary of a ball has a small tail. As applications, we show that the volume of intersection of balls in Hamming, Johnson spaces and symmetric groups decay exponentially as their centers drift apart. To verify condition (iii), we prove some large deviation inequalities ‘on a slice’ for functions with Lipschitz conditions. We then use these estimates on intersection volumes to 1) obtain a sharp lower bound on list-decodability of random q-ary codes, confirming a conjecture of Li and Wootters, and 2) improve the classical bound of Levenshtein from 1971 on constant weight codes by a factor linear in dimension, resolving a problem raised by Jiang and Vardy. Our probabilistic point of view also offers a unified framework to obtain improvements on other Gilbert-Varshamov type bounds, giving conceptually simple and calculation-free proofs for$q$-ary codes, permutation codes, and spherical codes. Another consequence is a counting result on the number of codes, showing ampleness of large codes.

We introduce a notion of the crux of a graph $G$, measuring the order of a smallest dense subgraph in $G$. This simple-looking notion leads to some generalizations of known results about cycles, offering an interesting paradigm of “replacing average degree by crux.” In particular, we prove that every graph contains a cycle of length linear in its crux. Long proved that every subgraph of a hypercube $Q^m$ (resp., discrete torus $C_3^m$) with average degree $d$ contains a path of length $2^{d/2}$ (resp., $2^{d/4}$) and conjectured that there should be a path of length $2^{d}-1$ (resp., $3^{d/2}-1$). As a corollary of our result, together with isoperimetric inequalities, we close these exponential gaps giving asymptotically optimal bounds on long paths in hypercubes, discrete tori, and more generally Hamming graphs. We also consider random subgraphs of $C_4$-free graphs and hypercubes, proving near optimal lower bounds on the lengths of long cycles.

An important result of Komlós [Tiling Turán theorems, Combinatorica, 2000] yields the asymptotically exact minimum degree threshold that ensures a graph $G$ contains an $H$-tiling covering an $x$th proportion of the vertices of $G$ (for any fixed $x \in (0,1)$ and graph $H$). We give a degree sequence strengthening of this result which allows for a large proportion of the vertices in the host graph $G$ to have degree substantially smaller than that required by Komlós's theorem. We also demonstrate that for certain graphs $H$, the degree sequence condition is essentially best possible in more than one sense.

Given graphs $H_1,\ldots, H_k$, a graph $G$ is $(H_1,\ldots, H_k)$-free if there is a $k$-edge-coloring $\phi:E(G)\rightarrow [k]$ with no monochromatic copy of $H_i$ with edges of color $i$ for each $i\in[k]$. Fix a function $f(n)$; then the Ramsey--Turán function ${RT}(n,H_1,\ldots,H_k,f(n))$ is the maximum number of edges in an $n$-vertex $(H_1,\ldots,H_k)$-free graph with independence number at most $f(n)$. We determine ${RT}(n,K_3,K_s,\delta n)$ for $s\in\{3,4,5\}$ and sufficiently small $\delta$, confirming a conjecture of Erd\Hos and Sós [ Stud. Sci. Math. Hung., 14 (1979), pp. 27--36]. It is known that ${RT}(n,K_8,f(n))$ has a phase transition at $f(n)=\Theta(\sqrt{n\log n})$. However, the value of ${\rm RT}(n,K_8, o(\sqrt{n\log n}))$ was not known. We determined this value by proving ${RT}(n,K_8,o(\sqrt{n\log n}))=\frac{n^2}{4}+o(n^2)$, answering a question of Balogh, Hu, and Simonovits [ J. Combin. Theory Ser. B, 114 (2015), pp. 148--169]. The proofs utilize, among others, dependent random choice and results from graph packings.

Alon, Balogh, Keevash, and Sudakov proved that the $(k-1)$-partite Turán graph maximizes the number of distinct $r$-edge-colorings with no monochromatic $K_k$ for all fixed $k$ and $r=2,3$, among all $n$-vertex graphs. In this paper, we determine this function asymptotically for $r=2$ among $n$-vertex graphs with a sublinear independence number. Somewhat surprisingly, unlike Alon, Balog, Keevash, and Sudakov's result, the extremal construction from Ramsey--Turán theory, as a natural candidate, does not maximize the number of distinct edge-colorings with no monochromatic cliques among all graphs with a sublinear independence number, even in the 2-colored case. In the second problem, we determine the maximum number of triangles asymptotically in an $n$-vertex $K_k$-free graph $G$ with $\alpha(G)=o(n)$. The extremal graphs have a similar structure to the extremal graphs for the classical Ramsey--Turán problem, i.e., when the number of edges is maximized.