Graph property

A graph property is a class of finite graphs closed under isomorphism. Its labelled order-$n$ slice consists of members on vertex set $[n]$. Closure under taking arbitrary subgraphs and closure under taking only induced subgraphs lead respectively to subgraph-closed graph properties and hereditary graph properties.

All edges of a simple undirected graph have at least one common endpoint. The empty graph is included when there is at least one vertex, and isolated vertices are permitted. This is the star predicate with isolated vertices allowed; a connected star graph is a special case. Its decision-tree depth is the full number $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ of edge bits for $n\ge 3$.

For $n\ge 3$, a full star graph requires every nonincident edge to be certified absent, and fixing those bits suffices. Rejection is certified by at most three present edges with empty common intersection; a triangle needs all three. Hence query certificate complexity is $\max \{3,(\genfrac{}{}{0ex}{}{n-1}{2})\}=\Theta (n^2)$ for this property.

For $n\ge 3$, count the empty graph once, all one-edge graphs once, and each larger accepted graph under its unique center. The latter weighted contribution is $n(n-2)$, giving $1-\left(\genfrac{}{}{0ex}{}{n}{2}\right)+n(n-2)$. Its nonzero value proves evasiveness by the alternating-sum criterion for decision-tree evasiveness.

The speed counts the labelled graphs with a given property on vertex set $[n]$. For proper unbounded hereditary graph properties, its base-two logarithm has leading term $(1-1/r)\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, where $r$ is the property's colouring number.

A hereditary graph property is closed under taking induced subgraphs. It can be described by forbidden induced graphs. Unlike subgraph closure, this condition allows edges to be essential to membership. Its colouring number of a hereditary graph property governs its quadratic enumeration rate.

This parameter measures the largest completely unrestricted clique-independent partition class contained in the property. It is zero for bounded-order hereditary classes and infinite for all graphs. For proper unbounded classes it is a positive integer; it differs from the degeneracy-based colouring number of an individual graph.

For a proper hereditary graph property with unbounded orders, the colouring number determines the leading labelled speed. The lower bound comes from one contained clique-independent partition class. For the upper bound, forbid one induced graph from each next-size partition type and use the induced regularity template lemma. Its intermediate-pair graph is clique-free, and sparse or almost-complete pairs have negligible entropy. Bounded-order properties have colouring number zero and are outside this formula.

Graphs in $\mathcal{C}(a,b)$ admit a partition into $a$ total classes, of which $b$ are designated cliques and $a-b$ are designated independent sets. Cross edges are arbitrary and empty classes are allowed. Balanced cross-edge choices give quadratic labelled speed coefficient $1-1/a$. Comparing this count with every $(a+1)$-class type shows that the hereditary colouring number of this class is exactly $a$.

Membership is preserved under deleting vertices and edges. This is the decreasing meaning of monotonicity in extremal graph enumeration; it differs from an increasing monotone graph property used for random-graph thresholds. For a proper unbounded class, its least excluded chromatic number determines the leading quadratic logarithm of its labelled speed.

Here $r+1$ is the least chromatic number of an excluded graph, for a proper unbounded subgraph-closed property. All subgraphs of a balanced Turan graph give the lower bound. For the upper bound, a regularity reduced graph is clique-free, so its dense pairs have the Turan theorem edge bound; sparse pairs contribute only small binary entropy and the bounded partition description costs only a linear number of bits.