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).
Improve this question
$\endgroup$
7
  • 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
    Commented Jun 15, 2017 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
    Commented Jun 15, 2017 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
    Commented Jun 15, 2017 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
    Commented Jun 15, 2017 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
    Commented Jun 16, 2017 at 6:48

1 Answer 1

Reset to default
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.
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .