Compactness results in extremal graph theory (Q1837701)

(From the authors' abstract:) ``Let \(L\) be a given family of \dots 'prohibited graphs'. Let \(\text{ex}(n,L)\) denote the maximum number of edges a simple graph of order n can have without containing subgraphs from \(L\). A typical extremal graph problem is to determine \(\text{ex}(n,L)\), or, at least, to find good bounds on it. Results asserting that, for a given \(L\), there exists a 'much smaller' \(L^*\subset L\) for which \(\text{ex}(n,L)\approx \text{ex}(n,L^*)\) will be called compactness results. The main purpose of this paper is to prove some compactness results for the case when \(L\) consists of cycles. One of our main tools will be finding lower bounds on the number of paths \(p^{k+1}\) in a graph on \(n\) vertices and \(E\) edges \dots a `supersaturated' version of a well known theorem of Erdős and Gallai.'' Among the theorems proved, presented in the context of open conjectures, are: Theorem 1: Let \(k\) be a natural number. Then \(\text{ex}(n,\{C^3,\dots,C^{2k},C^{2k+1}\})\leq(n/2)^{1+(1/k)}+2^k\cdot(n/2)^{1-(1/k)}\). Theorem 2: \(\text{ex}(n,\{C^4,C^5\})=(n/2)^{3/2}+0(n)\). Theorem 3*: Let \(T\) be a tree with a fixed 2-colouring: A graph \(L\) is obtained from \(T\) by joining a new vertex to each vertex of one colour class by disjoint paths, each k edges long. Then, if \(\text{ex}(n,L)\geq cn^{1+(1/k)}\), then is a \(t\) for which \[ \lim_{n\to\infty}(ex(n,\{L,C^3,C^5,\dots\})/ex(n,\{L,C^3,C^5,\dots,C^{2_{t-1}}\}))=1 \] Theorem 5: If \(f(n,d)\) is the minimum number of walks \(W^{k+1}\) a graph \(G^n\) can have with average degree \(d\), then every graph of order \(n\) and average degree \(d\) contains at least \((1/2)\cdot f(n,d)-0(f(n,d))\) paths \(p^{k+1}\), as \(d\to\infty\).