3
$\begingroup$

Many combinatorial problems can be reduced to bounding the number of edges in a given graph with $n$ vertices. Each time I encounter such a problem, I check whether the corresponding graph has a property that is known to imply a bound on number of edges (as probably most people do). For example, whether the graph is planar.

My question is what graph properties imply a bounded number of edges. I assume that there are such properties that I am not familiar with, and it seems quite useful to have a list of these properties. I am only interested in cases where the number of edges is asymptotically smaller than $n^2$ (for example, Turan's Theorem is not relevant).

Some properties that I am already familiar with:

  • Planar graphs have $O(n)$ edges. There are several variants, such as quasi-planar graphs, with linear or almost linear bounds.
  • The Zarankiewicz problem states that a graph that contains no copy of $K_{s,t}$ has $O(n^{2-1/s})$ edges (this is the formulation for the case where $s$ and $t$ are constants).
  • Moore's bound states that a graph of girth larger than $2k$ contains $O(n^{1+1/k})$ edges.
  • Families of graphs that are closed under taking induced subgraphs and have sufficiently small separators have $O(n)$ edges (e.g., see Fox and Pach).
$\endgroup$
  • 1
    $\begingroup$ Any minor-closed class of graphs that excludes at least one complete graph has only a linear number of edges. $\endgroup$ – Gordon Royle Jun 15 '17 at 0:31
  • 1
    $\begingroup$ Graphs with $n$ vertices and excluding $K_t$ as a topological minor (i.e. as a subdivision) have $O(t^2 n)$ edges. $\endgroup$ – David Wood Jun 15 '17 at 9:13
  • 1
    $\begingroup$ Graphs with $n$ vertices that can be drawn on a fixed surface with $O(n)$ crossings have $O(n)$ edges. This follows from the crossing lemma. More generally, graphs with $n$ vertices that can be drawn on a fixed surface with $O(n^{4-3\epsilon})$ crossings have $O(n^{2-\epsilon})$ edges. $\endgroup$ – David Wood Jun 15 '17 at 9:27
  • 1
    $\begingroup$ In the comment about the Zarankiewicz problem, should $O(n^{1-1/s})$ be $O(n^{2-1/s})$? $\endgroup$ – David Wood Jun 15 '17 at 9:42
  • 1
    $\begingroup$ The Zarankiewicz problem generalises to any bipartite Turan problem (i.e. forbidding any fixed bipartite graph as a subgraph). The bound for graphs of girth larger than $2k$ fits into this framework as Bondy and Simonovits proved that any graph without a cycle of length $2k$ has at most $20kn^{1+1/k}$ edges. $\endgroup$ – Jon Noel Jun 16 '17 at 6:48
2
$\begingroup$

In the case of hereditary classes of graphs (which is often not a very restrictive assumption. In particular, all classes from your post and the comments are hereditary) it is necessary and sufficient to forbid a clique and a biclique as an induced subgraph. Namely,

$n$-vertex graphs in a hereditary class $X$ have $o(n^2)$ vertices if and only if graphs in $X$ are ($K_p$, $K_{t,t}$)-free for some constants $p$ and $t$ (i.e., do not contain $K_p$ and $K_{t,t}$ as induced subgraphs). This is equivalent to saying that graphs in $X$ do not contain $K_{q,q}$ as a subgraph for some constant $q$.

For example,

  1. Planar graphs are $(K_5, K_{3,3})$-free;
  2. Graphs of girth larger than 4 are $(K_3, K_{2,2})$-free.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.