Math 426/529: Extremal Combinatorics

A graph \(G'\) is a subgraph of a graph \(G\) if \(V(G')\subseteq V(G)\) and \(E(G')\subseteq E(G)\text{.}\) Two graphs \(G_1\) and \(G_2\) are isomorphic if there is a bijection \(f:V(G_1)\to V(G_2)\text{,}\) called a graph isomorphism, such that \(uv\in E(G_1)\) if and only if \(f(u)f(v)\in E(G_2)\text{.}\) Say that an copy of a graph \(H\) in a graph \(G\) is a subgraph of \(G\) that is isomorphic to \(H\text{.}\) The number of copies of \(H\) in \(G\) is therefore the number of such subgraphs. A graph \(G\) is \(H\)-free if it does not contain a copy of \(H\text{.}\) Note that, here, we are speaking about “unlabelled” copies of \(H\text{.}\)

A large part of extremal graph theory is focused on understanding the “interaction” between the number of copies of “small” graphs \(H_1,H_2,\dots,H_k\) within a “large” graph \(G\text{.}\) For instance, a typical question in this area is as follows:

This can be thought of as maximizing the number of copies of the complete graph on \(2\) vertices subject to having no copies of \(H\text{.}\) We denote this maximum number by \(\ex(n,H)\) and call it the extremal number of \(H\) (or \(n\)th extremal number, if such precision is necessary). The focus of this chapter and the one which follows it is on determining, or estimating, the value of \(\ex(n,H)\) for different graphs \(H\text{.}\)

Before moving on, it is useful to introduce some standard graph-theoretic terminology. Given a graph \(G\) and \(v\in V(G)\text{,}\) say that \(u\in V(G)\) is a neighbour of \(v\) or is adjacent to \(v\) if \(uv\in E(G)\text{.}\) Let \(N(v)\) be the set of neighbours of \(v\) and \(d(v):=|N(v)|\) be the degree of \(v\text{.}\) We sometimes write \(N_G(v)\) or \(d_G(v)\) if the graph is not clear from context. Let \(\delta(G):=\min\{d(v): v\in V(G)\}\) and \(\Delta(G):=\max\{d(v):v\in V(G)\}\) be the minimum and maximum degrees of \(G\text{,}\) respectively. Given a set \(S\subseteq V(G)\text{,}\) the subgraph of \(G\) induced by \(S\) is the graph \(G[S]\) with vertex set \(S\) and edge set \(\{uv\in E(G): u,v\in S\}\text{.}\) Given disjoint sets \(A\) and \(B\) of vertices, let \(e(A)\) be the number of edges of \(G\) contained in \(A\) and \(e(A,B)\) be the number of edges with one endpoint in \(A\) and one endpoint in \(B\text{;}\) again, we may write \(e_G\) in situations in cases when we need to specify the graph \(G\text{.}\) The complement of a graph \(G\text{,}\) denoted \(\overline{G}\text{,}\) is the graph with vertex set \(V(G)\) in which two vertices are adjacent if and only if they are not adjacent in \(G\text{.}\)

While our main focus will be on graphs, we will sometimes consider other closely related combinatorial objects. Unless stated otherwise, the graphs that we consider are “simple” in the sense that they do not contain loops (i.e. an edge between a vertex and itself) or multiple edges (i.e. more than one copy of the same edge). If we wish to refer to a graph with loops or multiple edges, then we will use the term multigraph. We mainly focus on undirected graphs, meaning that each edge is an unordered pair in \(\binom{V}{2}\text{;}\) a directed graph or digraph for short is a pair \((V,A)\) where \(A\subseteq V\times V\) is a set of ordered pairs. In a directed graph, the elements of \(A\) are called arcs. A tournament is a directed graph \((V,A)\) such that \(A\) contains no loops and contains exactly one of \((u,V)\) or \((v,u)\) for any distinct \(u,v\in V\text{.}\) For \(k\geq2\text{,}\) a \(k\)-uniform hypergraph is a pair \((V,E)\) where \(E\subseteq \binom{V}{k}\text{;}\) i.e. it is the natural generalization of a graph in which edges have cardinality \(k\text{.}\) Most of the notation and terminology that we will introduce for graphs extends naturally to multigraphs, directed graphs, tournaments and hypergraphs.