Abstract. We study how many copies of a graph [Formula: see text] that another graph [Formula: see text] with a given number of cliques is guaranteed to have. For example, one of our main results states that for all [Formula: see text], if [Formula: see text] is an [Formula: see text]-vertex graph with [Formula: see text] triangles and [Formula: see text] is sufficiently large in terms of [Formula: see text], then [Formula: see text] contains at least [Formula: see text] copies of [Formula: see text], and, furthermore, we show that these bounds are essentially best possible provided that either [Formula: see text] or certain bipartite analogues of well-known conjectures for Turán numbers hold.

The long standing Zarankiewicz's conjecture states that the crossing number cr(Km,n) of the complete bipartite graph is Z(m,n):= [m/2][m-1/2][n/2][n-1/2]. Using flag algebras we show that cr(Kn,n) ≥ 0.9118 • Z(n, n) + o(n4). We also show that the rectilinear crossing number cr-(Kn,n) of Kn,n is at least 0.987 • Z(n,n) + o(n4). Finally, we show that if a drawing of Kn,n has no K3,4 that has exactly two crossings, and these crossings share exactly one vertex, then it has at least Z(n,n) + o(n4) crossings. This is a local restriction inspired by Turán type problems that gives an asymptotically tight result.

Abstract. For a hypergraph [Formula: see text], define the minimum positive [Formula: see text]-degree [Formula: see text] to be the largest integer [Formula: see text] such that every [Formula: see text]-set which is contained in at least one edge of [Formula: see text] is contained in at least [Formula: see text] edges. For [Formula: see text] and [Formula: see text], we prove that for [Formula: see text]-vertex [Formula: see text]-intersecting [Formula: see text]-graphs [Formula: see text] with [Formula: see text], the unique hypergraph with the maximum number of edges is the hypergraph [Formula: see text] consisting of every edge which intersects a set of size [Formula: see text] in at least [Formula: see text] vertices provided [Formula: see text] is sufficiently large. This generalizes work of Balogh, Lemons, and Palmer who proved this for [Formula: see text], as well as the Erdős-Ko-Rado theorem when [Formula: see text].

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.