Abstract 1 Introduction 2 Preliminaries 3 Implicit representation for weakly sparse small classes 4 Short adjacency labels for small classes 5 Conclusion References Appendix A Paths with low crossing number

2025/07/012019/07/01

Adjacency Labeling Schemes for Small Classes

Édouard Bonnet ORCID Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France Julien Duron ORCID Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France John Sylvester ORCID Department of Computer Science, University of Liverpool, UK Viktor Zamaraev ORCID Department of Computer Science, University of Liverpool, UK
Abstract

A graph class admits an implicit representation if, for every positive integer n, its n-vertex graphs have a O(logn)-bit (adjacency) labeling scheme, i.e., their vertices can be labeled by binary strings of length O(logn) such that the presence of an edge between any pair of vertices can be deduced solely from their labels. The famous Implicit Graph Conjecture posited that every hereditary (i.e., closed under taking induced subgraphs) factorial (i.e., containing 2O(nlogn) n-vertex graphs) class admits an implicit representation. The conjecture was recently refuted [Hatami and Hatami, FOCS ’22], and does not even hold among monotone (i.e., closed under taking subgraphs) factorial classes [Bonnet et al., ICALP ’24]. However, monotone small (i.e., containing at most n!cn many n-vertex graphs for some constant c) classes do admit implicit representations.

This motivates the Small Implicit Graph Conjecture: Every hereditary small class admits an O(logn)-bit labeling scheme. We provide evidence supporting the Small Implicit Graph Conjecture. First, we show that every small weakly sparse (i.e., excluding some fixed bipartite complete graph as a subgraph) class has an implicit representation. This is a consequence of the following fact of independent interest proved in the paper: Every weakly sparse small class has bounded expansion (hence, in particular, bounded degeneracy). Second, we show that every hereditary small class admits an O(log3n)-bit labeling scheme, which provides a substantial improvement of the best-known polynomial upper bound of n1ε on the size of adjacency labeling schemes for such classes. This is a consequence of another fact of independent interest proved in the paper: Every small class has neighborhood complexity O(nlogn).

Keywords and phrases:
Adjacency labeling, degeneracy, weakly sparse classes, small classes, implicit graph conjecture
Copyright and License:
[Uncaptioned image] © Édouard Bonnet, Julien Duron, John Sylvester, and Viktor Zamaraev; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Mathematics of computing Combinatorics
; Mathematics of computing Graph theory
Related Version:
Full Version: https://arxiv.org/abs/2409.04821 [49]
Acknowledgements:
We are grateful to Maksim Zhukovskii for many stimulating discussions on the topic of this paper. The first author thanks Szymon Toruńczyk for introducing him to (and answering questions on) the topic of paths with low crossing number.
Funding:
This work has been supported by the Royal Society (IES\R1\231083), by the ANR projects TWIN-WIDTH (ANR-21-CE48-0014) and Digraphs (ANR-19-CE48-0013), and also the EPSRC project EP/T004878/1: Multilayer Algorithmics to Leverage Graph Structure.
Editor:
Raghu Meka

1 Introduction

A class of graphs is a set of graphs which is closed under isomorphism. For a class of graphs 𝒳 we denote by 𝒳n the set of graphs in 𝒳 with vertex set [n]. Let 𝒳 be a class of graphs and b: be a function. A b(n)-bit adjacency labeling scheme (or simply b(n)-bit labeling scheme) for 𝒳 is a pair (encoder, decoder) of algorithms where for any n-vertex graph G𝒳n the encoder assigns binary strings, called labels, of length b(n) to the vertices of G such that the adjacency between any pair of vertices can be inferred by the decoder only from their labels. We note that the decoder depends on the class 𝒳, but not on the graph G. The function b() is the size of the labeling scheme. Adjacency labeling schemes were introduced by Kannan, Naor, and Rudich [35, 36], and independently by Muller [41] in the late 1980s and have been actively studied since then.

The binary word, obtained by concatenating labels of the vertices of a graph G𝒳n assigned by an adjacency labeling scheme, uniquely determines graph G. Thus, a b(n)-bit labeling scheme cannot represent more than 2nb(n) graphs on n vertices, and therefore, if 𝒳 admits a b(n)-bit labeling scheme, then |𝒳n|2nb(n). This implies a lower bound of log|𝒳n|n on the size b(n) of any adjacency labeling scheme for 𝒳. We say that a graph class 𝒳 admits an implicit representation, if it admits an information-theoretic order optimal adjacency labeling scheme, i.e., if 𝒳 has a b(n)-bit labeling scheme, where b(n)=O(log|𝒳n|/n). A natural and important question is: which classes admit an adjacency labeling scheme of a size that matches this information-theoretic lower bound?

Of particular interest is the case of adjacency labeling schemes of size O(logn). This is because, under the natural assumption that vertices get assigned pairwise distinct labels, logn is a lower bound on the size of any labeling scheme. Thus, understanding the expressive power of the labeling schemes of size of order logn is a natural question.

By the above discussion adjacency labeling schemes of size O(logn) can only exist for (at most) factorial graph classes, i.e., classes 𝒳 in which the number |𝒳n| of n-vertex graphs grows not faster than 2Θ(nlogn). It is known that the latter condition alone is not enough to guarantee adjacency labels of size O(logn) [41]. Kannan, Naor, and Rudich [35] asked if the extra restriction on 𝒳 of being hereditary, i.e., closed under taking induced subgraphs, would be enough for the existence of O(logn)-bit adjacency labeling scheme. This question was later stated by Spinrad [46] in the form of a conjecture, reiterated by Scheinerman [29, Chapter 6], that became known as the Implicit Graph Conjecture.

  • (IGC):

    Any hereditary factorial graph class admits an O(logn)-bit labeling scheme.

The conjecture remained open for three decades until it was recently refuted in a strong form by Hatami and Hatami, who showed that for any δ there exists a hereditary factorial class that does not admit an (n1/2δ)-bit labeling scheme [33]. This refutation leaves wide open the question of characterizing hereditary graph classes that admit O(logn)-bit labeling schemes and no plausible conjectural dichotomy is currently available.

It was recently shown that IGC does not hold even in the family of monotone graph classes, the hereditary classes which are closed under taking (not necessarily induced) subgraphs [11]. On the positive side, it was shown in the same work that IGC holds for every monotone small class, i.e., a monotone class 𝒳 with |𝒳n|n!cn for some constant c>0.

The hereditary small classes form a subfamily of hereditary factorial classes that contains many classes of practical or theoretical importance. For instance, forests [44], planar graphs [47], classes of bounded treewidth [8], proper minor-closes classes [43], unit interval graphs [32], classes of bounded clique-width [3], and more generally, classes of bounded twin-width [13] are all small. All of these classes are known to admit order-optimal, and, sometimes, even asymptotically optimal adjacency labeling schemes. For example, forests admit a (logn+O(1))-bit labeling scheme [5], planar graphs admit a (1+o(1))logn-bit labeling scheme [19], classes of bounded treewidth admit a (1+o(1))logn-bit labeling scheme [28], proper minor-closed classes admit a (2+o(1))logn-bit labeling scheme [28], graphs of clique-width at most k admit a O(klogklogn)-bit labeling scheme [46, 7], and graphs of twin-width at most k admit a 22O(k)logn-bit labeling scheme [13]. It is known that not every hereditary (and even monotone) small class admits an asymptotically optimal labeling scheme of size (1+o(1))logn [10]. However, this does not rule out the existence of order optimal labeling schemes of size O(logn) for all hereditary small classes. Alon [4] recently showed that every hereditary class 𝒳 with |𝒳n|=2o(n2) (which include all hereditary small classes) admits an adjacency labeling scheme of size n1ε for some ε>0 depending on the class. To our knowledge, no better upper bound was established for hereditary small classes.

The importance of hereditary small classes and the existence of O(logn)-bit labeling schemes for all monotone small classes motivated the formulation of the Small Implicit Graph Conjecture.

  • (Small IGC) [11]:

    Any hereditary small graph class admits an O(logn)-bit labeling scheme.

1.1 Our contribution

In this paper we provide evidence toward the Small Implicit Graph Conjecture in two independent directions. First, we show that the Small IGC holds in the important special case of weakly sparse graph classes. Secondly, we obtain an adjacency labeling scheme of polylogarithmic size for any hereditary small class substantially improving upon the best-known polynomial-size upper bound on adjacency labeling schemes for such classes.

Our first result is a consequence of a structural property of small classes of graphs. To state this property, we need to introduce some terms. A hereditary class 𝒳 is said to be weakly sparse if there exists an integer t such that the complete bipartite graph Kt,t is not a subgraph of any graph of 𝒳. The degeneracy of a graph G is the minimum number k such that every induced subgraph of G contains a vertex of degree at most k. We defer a formal definition of bounded expansion until Section 2 as it is somewhat technical. Instead, we note that bounded expansion generalizes bounded degeneracy, thus Theorem 1 a fortiori holds when the former is replaced by the latter.

Theorem 1.

Every weakly sparse small class has bounded expansion.

This structural insight into small graph classes is of independent interest due to the significance of weakly sparse graph classes. The notion of weakly sparseness is the broadest form of sparsity. It generalizes the properties of bounded degree, bounded degeneracy, and nowhere denseness [42]. By the celebrated Kővári–Sós–Turán theorem [37], among hereditary classes, weakly sparse classes are precisely the classes of graphs with a truly subquadratic number of edges. It is often observed that the extra restriction of being weakly sparse significantly simplifies the structure of graphs possessing a particular property. For example, weakly sparse graph classes of bounded clique-width have bounded treewidth [31]; weakly sparse graph classes of bounded twin-width have bounded expansion, and thus bounded degeneracy [13] (a fact that Theorem 1 generalizes, as it was proven in the same paper that every class of bounded twin-width is small); weakly sparse string graphs have bounded degeneracy [26], and even polynomial expansion [23]; weakly sparse graph classes that are well-quasi-ordered by the induced-subgraph relation have bounded pathwidth [6], etc.

A conjecture from 2016 [1], driving an ongoing program in algorithmic graph theory, suggests that, under some widely-believed complexity-theoretic assumption, a hereditary graph class admits a fixed-parameter tractable (FPT) first-order (FO) model-checking algorithm if and only if it is monadically dependent.111As with the other side remarks, we do not define the technical terms in this sentence since they will not reappear. It was recently proven that every hereditary small class is monadically dependent [17] (and, in the same paper, the only if part of the conjecture was established). Thus, if the conjecture holds, it should in particular be true that every hereditary small class admits an FPT FO model-checking algorithm. Theorem 1 confirms that this is indeed the case within weakly sparse classes, as such an algorithm is known to exist for classes of bounded expansion [22].

Dvořák and Norine proved that if the expansion of a class is upper bounded by a sufficiently slowly-growing subexponential function, then the class is small [24]. From the definition of expansion given in the next section, it should be clear that the converse cannot hold since the small classes consisting of all complete graphs or of all bipartite complete graphs have unbounded expansion. A minimum requirement to establish a partial converse is thus that the class is weakly sparse. Theorem 1 confirms that under this condition the expansion of any small class is indeed bounded (albeit not necessarily by a subexponential nor a single-exponential function).

We apply Theorem 1 to obtain our first main result that the Small IGC holds for weakly sparse graph classes. This follows from a classical labeling scheme for classes of bounded degeneracy [35] (see also [11, Lemma 3.5]).

Theorem 2.

Every weakly sparse small class admits an O(logn)-bit adjacency labeling scheme.

Our second main result holds more generally for any hereditary small class and goes some way toward the full strength of the Small IGC.

Theorem 3.

Every hereditary small class admits an O(log3n)-bit adjacency labeling scheme.

This result is based on our second structural result of independent interest that hereditary small graph classes have low neighborhood complexity.

Theorem 4.

The neighborhood complexity of any hereditary small graph class is O(nlogn).

The neighborhood complexity is a measure of structural complexity of graphs. Informally (a formal definition is given in Section 2), it reflects the diversity of the set system of the vertex neighborhoods in the graph. Low neighborhood complexity of graph classes implies nice structural and algorithmic properties. For example, in the universe of monotone graph classes, linear neighborhood complexity characterizes classes of bounded expansion [45], and almost linear neighborhood complexity characterizes nowhere dense classes [25]. Low neighborhood complexity is also used to obtain FPT algorithms for various graph problems (see for instance [25, 14]), and was recently used as a central ingredient of an FPT algorithm for the FO model-checking problem on monadically stable graph classes [16]. It is known that every hereditary graph class of bounded twin-width has linear neighborhood complexity [14] (see also [12] for improved bounds). We omit formal definitions and result statements, and refer the reader to the respective work.

We obtain our Theorem 3 by combining Theorem 4 with some known result from the theory of sets systems about paths with low crossing number. In a standard form the latter result is not suitable for our need, and therefore we reformulate it and provide a self-contained proof. We believe that the result stated in this form can be of use for other needs.

1.2 Organization

The paper is organized as follows. In Section 3, we prove that weakly sparse small classes have bounded expansion (and thus bounded degeneracy); from this, we derive an O(logn)-bit adjacency labeling scheme for such classes. In Section 4.1, we show that every hereditary small class has neighborhood complexity O(nlogn). In Section 4.2, we use this result together with a classical result from the theory of set systems stated in a suitable form, to obtain O(log3n)-bit labeling schemes for all hereditary small classes. In Appendix A, we provide a self-contained proof of the required form of the result from the theory of set systems. In the next section, we introduced necessary notation and state auxiliary facts.

2 Preliminaries

Graphs

We denote by V(G) and E(G) the vertex set and edge set of a graph G, respectively. When we refer to an n-vertex graph G as labeled, we mean that the vertex set of G is [n], and we distinguish two different labeled graphs even if they are isomorphic. For a set of graphs X, we denote by Lab(X) the set of all labeled graphs isomorphic to a graph in X. A graph H is an induced subgraph of G (resp. subgraph of G), if it can be obtained by removing vertices of G (resp. by removing vertices and edges of G). A subgraph H of G is spanning if V(H)=V(G). We denote by G[S] the subgraph of G induced by S, i.e., obtained by removing every vertex of V(G)S.

The degree of a vertex v in G, denoted by deg(v), is the number of vertices in G adjacent to v. The minimum (respectively, maximum) degree of G is the minimum (respectively, maximum) degree of a vertex in G. The average degree of G is the ratio vV(G)deg(v)/|V(G)|. Recall that the degeneracy of G is the minimum number k such that every induced subgraph of G contains a vertex of degree at most k. The following are immediate consequences of these definitions: (1) if the minimum degree of G is at least d, then the average degree of G and the degeneracy of G is at least d; (2) if the degeneracy of G is at least d, then G contains an induced subgraph of minimum degree at least d. One more relation between these three parameters is the following folklore result, which is not hard to derive by iteratively removing vertices of degree less than d/2.

Observation 5.

If the average degree of a graph G is at least d, then G contains an induced subgraph of minimum degree, and thus average degree, at least d/2.

We use GS as a shorthand for G[V(G)S], and Gv, for G{v}. We denote by Aut(G) the automorphism group of a graph G, and we set aut(G):=|Aut(G)|. If X is a set of pairwise non-isomorphic n-vertex graphs, then the number of labeled graphs isomorphic to a graph in X is exactly

|Lab(X)|=GXn!aut(G). (1)

For any non-negative integer r, the r-subdivision of a graph G, denoted by r-subd(G), is the graph obtained from G by adding one path Puv on r vertices for each edge uvE(G), and by replacing each edge uvE(G) by a (r+1)-edge path uPuvv. In the special case were r=0, r-subd(G) is the graph G. We will refer to a vertex from one of the paths Puv as a subdivision vertex and to other vertices as branching vertices.

For completeness, we include a definition222Actually, we rather give an established characterization [20] as it is more compact. of classes of bounded expansion. A class 𝒞 has bounded expansion if there is a function f: such that for every integer r0, no r-subdivision of a graph of average degree larger than f(r) is a subgraph of a graph in 𝒞. We will only apply existing results on classes of bounded expansion, and we will do so in a black-box fashion. Thus the reader should only observe that these classes are weakly sparse and of bounded average degree (by virtue of satisfying the given property for r=0).

Graph Classes

A class of graphs is hereditary if it is closed under taking induced subgraphs, and it is monotone if it closed under taking subgraphs. A hereditary graph class is small if there exists a constant c such that the number of n-vertex labeled graphs in the class is at most n!cn for every n.

Graph contiguity

The contiguity of a graph G, denoted ctg(G), is the minimum integer k such that there exists a linear order of its vertices in which the neighborhood of each vertex of G can be partitioned into at most k disjoint intervals. For a function k: and a class of graphs 𝒞, we say that 𝒞 has contiguity at most k, if for every n-vertex graph G𝒞 the contiguity of G is at most k(n).

The idea of contiguity was introduced in the context of range searching under the name of crossing number of spanning paths [48] (see also Appendix A). Independently, it was introduced in the context of DNA reconstruction under the name of k-consecutive ones property [30], which generalizes the notion of consecutive ones property for matrices [15, 27]. More recently, the concept was utilized as part of an FPT algorithm for the FO model-checking problem on monadically stable graph classes [16], and has appeared in the context of implicit graph representations [4, 2, 9]. In particular, Alon used it to show that every hereditary graph class 𝒳 with |𝒳n|=2o(n2) admits a n1ε-bit labeling scheme for some ε=ε(𝒳)>0 [4]. This was done via the following simple connection between contiguity and adjacency labeling schemes.

Proposition 6.

Let k: be a function, and 𝒞 be a class of graphs of contiguity at most k. Then 𝒞 admits an adjacency labeling scheme of size at most (2k(n)+1)logn.

Proof.

Let G be a n-vertex graph in 𝒞. To construct adjacency labels for G of the target size, we fix a linear ordering σ of the vertices of G witnessing contiguity at most k(n). The label of a vertex v of G then consists of its position in σ, followed by the positions of the endpoints of the at most k(n) intervals describing the neighborhood of v. The decoder infers adjacency between two vertices u and v by testing if the position of u in σ belongs to one of the intervals describing the neighborhood of v.

Set systems, shatter functions, and neighborhood complexity

A pair (X,𝒮), where X is a finite set and 𝒮 is a family of subsets of X is called a set system. The incidence matrix M of the set system (X,𝒮) is the matrix with |X| columns and |𝒮| rows indexed by the elements of X and 𝒮, respectively, where Mij is 1 if the i-th set of 𝒮 contains the j-th element of X, and 0 otherwise.

The primal shatter function of a set system (X,𝒮) is the function π𝒮 given by

π𝒮(m)=maxAX,|A|=m|{YA:Y𝒮}|.

The set system (X,𝒮), where X=𝒮, 𝒮={Sx:xX}, and Sx={S𝒮:xX}, is called the dual set system of (X,𝒮). The shatter function of (X,𝒮) is called the dual shatter function of (X,𝒮). Note that if M is the incidence matrix of (X,S), then the transpose of M is the incidence matrix of (X,𝒮). A subset AX is shattered by 𝒮 if every subset B of A can be obtained as the intersection B=AY for some Y𝒮, i.e., {YA|Y𝒮}=2A. The Vapnik–Chervonenkis dimension (or VC dimension for short) of 𝒮 is the maximum of the sizes of all shattered subsets of X.

Given a vertex v of a graph G, we use standard notation NG(v) to denote the set {u:vuE(G)} of neighbors of v in G. The neighborhood set system of G is the set system (V(G),𝒩G) where

𝒩G={NG(v):vV(G)}.

Observe that the adjacency matrix of G is the incidence matrix of (V(G),𝒩G). Thus, since the adjacency matrix of an undirected graph is symmetric, the primal and the dual shatter functions of a neighborhood set system coincide.

Observation 7.

For neighborhood set systems, the primal and dual shatter functions coincide. That is, for any n-vertex graph G,

π𝒩G(m)=π𝒩G(m)for all m[n].

We define the neighborhood complexity of a graph G, denoted by νG, as the primal (equivalently, dual) shatter function of its neighborhood set system, i.e., νG(m)=π𝒩G(m)=π𝒩G(m) for all m[|V(G)|].

Given a graph class 𝒞, the neighborhood complexity of 𝒞 is the function ν𝒞: defined by

ν𝒞(n):=supG𝒞,AV(G),|A|=n|{N(v)A:vV(G)}|=supG𝒞π𝒩(G)(n)=supG𝒞νG(n).

3 Implicit representation for weakly sparse small classes

In this section we prove Theorem 1, which states that any weakly sparse small class has bounded expansion, and hence, in particular, bounded degeneracy. Together with the known labeling scheme for bounded degeneracy graphs (see e.g. [11, Lemma 3.5]), this immediately implies that any weakly sparse small class admits an O(logn)-bit adjacency labeling scheme (Theorem 2).

The proof of Theorem 1 relies on the fact (Corollary 10) that for any weakly sparse class 𝒳 of unbounded expansion there exists an integer r1 such that 𝒳 contains r-subdivisions of graphs of arbitrarily large average degree. This is a consequence of the forward direction of a characterization of classes of (un)bounded expansion by Dvořák [21] and a classical result due to Kühn and Osthus [39], both stated below.

Theorem 8 ([21, Theorem 5, (a)(c)]).

A hereditary graph class 𝒳 has unbounded expansion if and only if there is an integer r0 such that for any integer d, 𝒳 contains the r-subdivision of a graph of average degree at least d.

Theorem 9 ([39, Theorem 2]).

For all d,t, there exists an integer D:=D(d,t) such that every Kt,t-free graph G of average degree at least D contains 1-subd(F) as an induced subgraph for some graph F of average degree at least d.

We now extract the announced fact, of which we will only need the only if direction.

Corollary 10.

A weakly sparse graph class 𝒳 is of unbounded expansion if and only if there is an integer r1 such that for any integer d, 𝒳 contains the r-subdivision of a graph of average degree at least d.

Proof.

The if part follows directly from Theorem 8. For the only if part, we first apply the corresponding implication in Theorem 8. If r1, we are done. If instead r=0, then 𝒳 contains graphs of arbitrarily large average degree. Therefore, Theorem 9 implies that 𝒳 contains 1-subdivisions of graphs of arbitrarily large average degree, i.e., the sought statement holds for r=1.

Equipped with this tool, the proof of Theorem 1 shows the contrapositive as follows. Assuming a weakly sparse class 𝒳 has unbounded expansion, we fix a positive integer r such that 𝒳 contains r-subdivisions of graphs of arbitrarily large average degree, which exists by Corollary 10. Let F be a graph with large average degree such that the r-subdivision of F is in 𝒳. First, we extract from F a subgraph H with large minimum degree that contains a bounded-degree spanning tree. This is possible due to Observation 5 and the following lemma.

Lemma 11 ([11, Lemma 3.3]).

Let F be a graph of minimum degree d. Then F has an induced subgraph H of minimum degree at least d with a spanning tree of maximum degree at most d.

Next, we use the properties of H to show that it contains many (not necessarily induced) subgraphs each with a small number of automorphisms, which are translated to many induced subgraphs with a small number of automorphisms in the r-subdivision of H and thus in the r-subdivision of the original graph F. This allows us to lower bound the number of labeled graphs on the same number of vertices in 𝒳 by counting subgraphs of H, and finally conclude that 𝒳 is not small. The quantitative connection is made possible by the following observations.

Observation 12.

For any integer r0, two graphs G and H are isomorphic if and only if r-subd(G) and r-subd(H) are isomorphic.

Observation 13.

Let F be a graph. For any integer r>0, for every subgraph H of F, the graph r-subd(H) is isomorphic to an induced subgraph of r-subd(F).

Observation 14.

Let G be a connected graph containing a vertex of degree at least 3, then

aut(r-subd(G))=aut(G).
Proof.

We start by showing that any automorphism φ of r-subd(G) maps branching vertices to branching vertices and subdivision vertices to subdivision vertices. First, note that as G has a vertex of degree at least 3, the graph r-subd(G) also has a vertex of degree at least 3 (hence a branching vertex) say u, which must be mapped by φ to a vertex of degree at least 3 (hence, to a branching vertex), say v. Now, since G is connected, the branching vertices are exactly the ones that are at distances 0(modr+1) from u, and they are mapped to vertices that are at distances 0(modr+1) from v, and thus, to branching vertices. Hence, the restriction φ~ of φ to the branching vertices of r-subd(G) is a permutation of the vertices of G. We claim that φ~ is an automorphism of G. Indeed, two vertices a and b are adjacent in G if and only if a and b are at distance r+1 in r-subd(G) if and only if φ(a) and φ(b) are at distance r+1 in r-subd(G) if and only if φ~(a)=φ(a) and φ~(b)=φ(b) are adjacent in G.

From this, we deduce that φφ~ is a bijection between the automorphisms of r-subd(G) and the automorphisms of G: it is injective since an automorphism of r-subd(G) is uniquely determined by the images of the branching vertices, and surjective since there are at least as many automorphisms of r-subd(G) as there are of G. Hence, aut(r-subd(G))=aut(G).

Before proceeding to our main result, we provide some basic facts about automorphisms, which we will rely on. Given two graphs F and G, we denote by #Sub(FG) the number of subgraphs of G isomorphic to F, and by #Emb(FG) the number of embeddings of F into G, i.e., the number of injective homomorphisms from F to G. Thus

#Emb(FG)=#Sub(FG)aut(F).

For instance, if G is the cycle on an even number n of vertices, and F is the disjoint union of n/2 edges, then #Sub(FG)=2 and aut(F)=(n/2)!2n2, so #Emb(FG)=(n/2)!2n2+1.

We will use the following two well known facts (see [38]).

Lemma 15.

Let F be a spanning subgraph of a graph G. Then

aut(G)#Emb(FG)=#Sub(FG)aut(F).
Lemma 16.

Let G be a connected graph of maximum degree Δ. Then

aut(G)nΔ!(Δ1)nΔ1nΔn.

We apply the above two facts to upper bound the number of automorphisms of a graph containing a bounded-degree spanning tree in terms its average degree.

Lemma 17.

Let d1 and G be a connected n-vertex graph with at most dn edges, which has a spanning tree T of maximum degree τ. Then aut(G)(6τd)n.

Proof.

By Lemma 16, aut(T)nτn(2τ)n. Moreover, #Sub(TG) is at most the number of ways of choosing n1 edges among E(G). Hence

#Sub(TG)(dnn1)(ednn1)n1=(1+1n1)n1(ed)n1e(ed)n1(ed)n,

where in the penultimate inequality we used the fact that 1+xex for any real x. Hence, by Lemma 15, we have aut(G)#Sub(TG)aut(T)(ed)n(2τ)n(6τd)n.

We are now ready to prove the main result of this section.

See 1

Proof.

For the sake of contradiction, suppose that a weakly sparse graph class 𝒳 has unbounded expansion, but there exists a constant c such that for every n the number of labeled n-vertex graphs in 𝒳 is at most n!cn. Let r1 be an integer such that 𝒳 contains r-subdivisions of graphs of arbitrary large average degree, which exists by Corollary 10.

Let δ:=24, d:=max(δ2,δc2r). Let F be a graph of average degree at least 4d, such that r-subd(F) is in 𝒳, and let F be a subgraph of F of minimum degree at least 2d, which exists by Observation 5. By Lemma 11, F contains a subgraph H of minimum degree at least 2d with a spanning tree T of maximum degree 2d. If H has more than d|V(H)| edges, we remove all but d|V(H)|(|V(H)|1) of them from the set E(H)E(T) to obtain a spanning subgraph with exactly d|V(H)| edges that still contains T as a spanning tree. We denote this subgraph by H and let k:=|V(H)|, and thus |E(H)|=dk.

Let be the set of spanning subgraphs of H that contain T as a subgraph and have exactly δk edges. Then, since δd, we have

||=(dk(k1)δk(k1))(dkkδkk)(d1δ1)(δ1)k(dδ)(δ1)k.

Since every graph in has δkdk edges and contains a spanning tree of maximum degree 2d, from Lemma 17,

maxAaut(A)(62dd)k(4d)2k. (2)

Thus, denoting by 𝒰 the set of pairwise non-isomorphic graphs in , we obtain

|𝒰|||maxAaut(A)(dδ)(δ1)k1(4d)2k=(dδ)(δ+1)kδ2k42kd4k=(dδ)(δ+1)k62kd4k (3)

Let r-subd(𝒰) be the set of r-subdivisions of graphs in 𝒰, and observe that every graph in r-subd(𝒰) has exactly N:=(rδ+1)k vertices. Since every graph in 𝒰 is a subgraph of F, and r-subd(F) is in 𝒳, Observation 13 implies that every graph in r-subd(𝒰) is in 𝒳. Thus, to contradict the assumption that, for every n, class 𝒳 has at most n!cn labeled n-vertex graphs, it is enough to show that |Lab(r-subd(𝒰))|>cNN!. This is what we do in the remainder of the proof.

It follows from Observation 12 that r-subd(𝒰) is a set of pairwise non-isomorphic graphs and |r-subd(𝒰)|=|𝒰|. Furthermore, since every graph A in is connected and has k vertices and δkk+1 edges, it contains a vertex of degree at least 3 and thus, by Observation 14, aut(r-subd(A))=aut(A). Therefore, from Equation 1, we have

|Lab(r-subd(𝒰))||r-subd(𝒰)|N!maxAaut(r-subd(A))=|𝒰|N!maxAaut(A),

and thus, from (2) and (3), and the fact that N/r=(δ+1/r)k(δ+1)k, we obtain

|Lab(r-subd(𝒰))|(dδ)N/r62kd4kN!(4d)2k>(dδ)N/rN!d6k,

Finally, since N4r=(rδ+1)k4r>δk4=6k, and d satisfies both dδ and (d/δ)1/rc2, we have

|Lab(r-subd(𝒰))|>(dδ)N2r(dδ)N2rN!d6k(dδ)N2rdN4rN!d6k>((dδ)1/r)N2N!cNN!,

which completes the proof.

4 Short adjacency labels for small classes

In this section we prove:

See 3

To do so, we first show a result of independent interest (in Section 4.1), that the neighborhood complexity of any small class is at most O(nlogn). Then, we prove in Section 4.2 that such neighborhood complexity implies O(log2n) contiguity. The latter together with Proposition 6 implies Theorem 3. The core part of this proof strategy is to show how the bound on the neighborhood complexity can be translated to the bound on contiguity. This is done via a classical result from the theory of set systems of bounded Vapnik-Chervonenkis dimension on so-called paths with low crossing number (Theorem 18) applied to neighborhood set systems. While the result about paths with low crossing number is a known fact, we need it in somewhat unusual form that we could not find elsewhere in the literature. Therefore, in Appendix A we present a self-contained proof of this result in a suitable form.

4.1 Neighborhood complexity of small classes

In this section we show that small classes have low neighborhood complexity.

See 4

Proof.

Let 𝒞 be a hereditary small class of graphs and c1 be a constant such that |𝒞n|n!cn holds for every n. To prove the claim, we will show that for every graph H in 𝒞 it holds that

νH(m)<9c2mlog(m+1) for all m[|V(H)|].

Suppose this is not the case. Then, by definition, there exists a graph H𝒞 and an n-element set AV(H) such that |{NH(v)A:vV(H)}|9c2nlog(n+1). Note that the latter inequality implies n4. Let BV(H) be any maximum-size set of vertices whose neighborhoods have pairwise distinct intersections with A in the graph H, and let B:=BA. Denote by G the subgraph of H induced by AB. By the assumption, we have

  1. 1.

    |A|=n,

  2. 2.

    |B||B||A|9c2nlog(n+1)n>8c2nlogn,

  3. 3.

    AB=, and

  4. 4.

    all vertices in B have pairwise distinct neighborhoods in A in graph G.

Let n1:=nlogn and N:=n1+n. We will show that the hereditary closure of G contains more than N!cN labeled graphs on N vertices, i.e., that |Lab(IndSubN(G))|>N!cN, where IndSubN(G) is the set of N-vertex induced subgraphs of G. This would contradict our assumption on the number of graphs in 𝒞. To do this, let us first fix a labeling of A using the integers from 1 to n. We claim that any two distinct labeled subsets X1,X2B of size n1, labeled with the integers from n+1 to N, induce two distinct labeled graphs G1=G[AX1] and G2=G[AX2] contained in 𝒞. Indeed, since all vertices in B have pairwise distinct neighborhoods in A, G1 and G2 contain a vertex with the same label in [n+1,N] but different neighborhoods in A (i.e. different neighborhoods among vertices with labels from [n]).

Hence, the number of N-vertex labeled graphs in 𝒞 that are induced subgraphs of G is lower bounded by the number of ways to choose a labeled subset of size n1 from B, which is

n1!(|B|n1)n1!(|B|n1)n1>n1!(8c2)n1. (4)

We want to show that this is more than the total number of N-vertex labeled graphs in 𝒞, which, by assumption, does not exceed

N!cN=(n1+n)!cn1+nn1!(n1+n)nc2n1. (5)

From Equation 4 and Equation 5, we should then show that

n1!(8c2)n1n1!(n1+n)nc2n1,

which is equivalent to establishing that

8n1=23n1(n1+n)n=2nlog(n1+n).

The latter indeed holds since

nlog(n1+n) nlog(2nlogn)
nlog2+nlogn+nloglogn
n(1+log2)+nlogn+nloglogn
nlogn+nlogn+nloglogn
n1+n1+n1=3n1,

where the penultimate inequality holds because n4.

4.2 From neighborhood complexity to contiguity

In this section, we first show how to translate a bound on neighborhood complexity to a bound on contiguity (Theorem 20), and then apply it to obtain bounds on contiguity for hereditary small classes (Theorem 21). A crucial technical tool that we use to establish this translation is a suitable form of a known result about paths with low crossing number (Theorem 18). To state this result we must first introduce the required notions.

Let (X,𝒮) be a set system. A set S𝒮 crosses a 2-element set {x,y}X if exactly one of x and y belongs to S. Let be a multiset of 2-element subsets in X. The crossing number of with respect to a set S𝒮 is the number of elements in that are crossed by S. The crossing number of with respect to 𝒮 is the maximum crossing number of with respect to a set S𝒮. If (X,), considered as a graph, is a path spanning all elements of X, then we say that (X,) is a path on X. In this case, the crossing number of is referred to as the crossing number of the corresponding path. We are now ready to state the main technical tool whose self-contained proof can be found in Appendix A.

Theorem 18.

Let X be an n-element set, f:00 be a strictly increasing function, and d be a natural number. Let (X,𝒮) be a set system of VC dimension d that satisfies π𝒮(m)f(m) for all m[n]. Then there exists a path on X with crossing number at most

2log|𝒮|+10dj=1n1f1(j/2).

We will apply Theorem 18 to neighborhood set systems. Its importance in our context is due to (a) the fact that the dual shatter function of the neighborhood set system of a graph coincides with its primal dual function (Observation 7), i.e., the neighborhood complexity of the graph; and (b) the following observation about close relationship between the crossing number of a path for the neighborhood set system and the contiguity of the graph.

Observation 19.

Let G be an n-vertex graph. If there exists a path on V(G) that has crossing number with respect to 𝒩G at most k, then the contiguity of G is at most k/2+1.

Proof.

Let {{v1,v2},{v2,v3},,{vn1,vn}} be a path on V(G) with crossing number with respect to 𝒩G at most k. We claim that the linear ordering σ=v1,v2,,vn of V(G) witnesses the target bound on the contiguity of G.

Let v be an arbitrary vertex in G and let N be its neighborhood. For convenience, mark a vertex of G by 1 if it belongs to N and 0 otherwise. This marking together with the ordering σ correspond to the binary word w=w1w2wn, where wi is the mark of vi for every i[n]. A relation between pairs crossed and neighborhoods partitioned now follows from two observations:

  1. 1.

    in the word w, the maximal intervals of consecutive 1s correspond to intervals of consecutive vertices in σ that partition the neighborhood N of v;

  2. 2.

    each pair of consecutive letters wiwi+1 in w with wiwi+1 corresponds to a crossing of {vi,vi+1} by N.

To conclude, each interval in the partition of N corresponds to two crossings apart from the at most two intervals at each end of the ordering which each corresponds to one crossing. Thus the number of intervals is at most 2+k22k/2+1, as claimed.

The next theorem translates a bound on neighborhood complexity to a bound on contiguity. It follows directly from Theorem 18, ˜19, Observation 7, and the definition of neighborhood complexity.

Theorem 20.

Let G be an n-vertex graph, f:00 be a strictly increasing function, and d be a natural number. If (V,𝒩G) has VC dimension d and νG(m)f(m) for all m[n], then

ctg(G)1+logn+5dj=1n1f1(j/2).

We now apply Theorem 20 to hereditary small classes, which have O(nlogn) neighborhood complexity by Theorem 4, to obtain a bound on their contiguity in closed form.

Theorem 21.

Let 𝒳 be a hereditary small class, then the contiguity of 𝒳 is O(log2n).

Proof.

Since 𝒳 is a small class, by Theorem 4 there exists some constant C such that ν𝒳f(n) where f(n):=Cnlogn. Consequently, for every n and every n-vertex graph G𝒳, we have π𝒩G(m)f(m) for all m[n]. Thus, by definition, the VC dimension d of (V(G),𝒩G) satisfies 2dCdlogd, which implies

dlogC+logd+loglogdlogC+4d/5,

and therefore d4logC.

Now, by Theorem 20, we have

ctg(G)1+logn+20logCj=1n1f1(j). (6)

Since f is increasing on [1,) with image [0,), its inverse f1 exists on [0,), and is also increasing. The exact inverse f1 is somewhat complicated, in particular f1(1)=eW(ln(2)/C), where W() is the Lambert function. We consider f1(1)>0 just as a constant depending on C, and show that

f1(x)xClogx for all x2. (7)

To show (7), since logx1 for all x2 and we can assume C1, we have

f(xClogx)=CxClogxlog(xClogx)x. (8)

Thus, applying f1 to both sides of (8) gives f1(x)xClogx, establishing (7).

Then, by (6),

ctg(G) 1+logn+20logCj=1n1f1(j)
1+logn+20logCeW(ln(2)/C)+20logCj=2nClogjj
=Θ(log2n),

as claimed.

The main Theorem 3 of this section is a consequence of Theorems 4, 21, and 6.

5 Conclusion

In this paper we obtained strong evidence in support of the Small Implicit Graph Conjecture that posits that every hereditary small class admits an O(logn)-bit adjacency labeling scheme. Specifically, we showed that (1) every weakly sparse small class admits such a labeling scheme; (2) every hereditary small class admits an O(log3n)-bit adjacency labeling scheme. To obtain these results we established two structural properties of hereditary small classes that are of independent interest. The first property is that every weakly sparse small class has bounded degeneracy, and even, bounded expansion. The second property is that every hereditary small class has neighborhood complexity O(nlogn).

The latter property leaves a tantalizing open question of whether the bound on the neighborhood complexity can be further improved. All hereditary small classes known to us have linear neighborhood complexity (e.g., classes of bounded twin-width [14, 12]), which motivates the following:

Conjecture 22.

Every hereditary small class of graphs has neighborhood complexity O(n).

If this conjecture is true, our approach would imply O(log2n)-bit labeling schemes for all hereditary small classes.

References

  • [1] Algorithms, Logic and Structure Workshop in Warwick – Open Problem Session, 2016. URL: https://warwick.ac.uk/fac/sci/maths/people/staff/daniel_kral/alglogstr/openproblems.pdf.
  • [2] Bogdan Alecu, Vladimir E. Alekseev, Aistis Atminas, Vadim Lozin, and Viktor Zamaraev. Graph parameters, implicit representations and factorial properties. Discrete Mathematics, 346(10):113573, 2023. doi:10.1016/j.disc.2023.113573.
  • [3] Peter Allen, Vadim V. Lozin, and Michaël Rao. Clique-width and the speed of hereditary properties. Electron. J. Comb., 16(1), 2009. doi:10.37236/124.
  • [4] Noga Alon. Implicit representation of sparse hereditary families. Discret. Comput. Geom., to appear, 2023. doi:10.1007/s00454-023-00521-0.
  • [5] Stephen Alstrup, Søren Dahlgaard, and Mathias Bæk Tejs Knudsen. Optimal induced universal graphs and adjacency labeling for trees. Journal of the ACM (JACM), 64(4):1–22, 2017. doi:10.1145/3088513.
  • [6] Aistis Atminas, Vadim V Lozin, and Igor Razgon. Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation. Journal of Combinatorics, 10(2):327–337, 2019. doi:10.4310/JOC.2019.v10.n2.a8.
  • [7] Avah Banerjee. An adjacency labeling scheme based on a decomposition of trees into caterpillars. In Combinatorial Algorithms: 33rd International Workshop, (IWOCA 2022), proceedings, pages 114–127. Springer, 2022. doi:10.1007/978-3-031-06678-8_9.
  • [8] Lowell W Beineke and Raymond E Pippert. The number of labeled k-dimensional trees. Journal of Combinatorial Theory, 6(2):200–205, 1969.
  • [9] Édouard Bonnet, Julien Duron, John Sylvester, and Viktor Zamaraev. Symmetric-Difference (Degeneracy) and Signed Tree Models. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), volume 306 of LIPIcs, pages 32:1–32:16, 2024. doi:10.4230/LIPIcs.MFCS.2024.32.
  • [10] Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, and Maksim Zhukovskii. Small but unwieldy: A lower bound on adjacency labels for small classes. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), pages 1147–1165, 2024. doi:10.1137/1.9781611977912.44.
  • [11] Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, and Maksim Zhukovskii. Tight bounds on adjacency labels for monotone graph classes. In 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, volume 297 of LIPIcs, pages 31:1–20, 2024. doi:10.4230/LIPIcs.ICALP.2024.31.
  • [12] Édouard Bonnet, Florent Foucaud, Tuomo Lehtilä, and Aline Parreau. Neighbourhood complexity of graphs of bounded twin-width. European Journal of Combinatorics, 115:103772, 2024. doi:10.1016/j.ejc.2023.103772.
  • [13] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width II: small classes. Combinatorial Theory, 2 (2), 2022. doi:10.5070/c62257876.
  • [14] Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, and Rémi Watrigant. Twin-width and polynomial kernels. Algorithmica, 84(11):3300–3337, 2022. doi:10.1007/s00453-022-00965-5.
  • [15] Kellogg S Booth and George S Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. Journal of computer and system sciences, 13(3):335–379, 1976. doi:10.1016/S0022-0000(76)80045-1.
  • [16] Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michał Pilipczuk, and Szymon Toruńczyk. First-order model checking on monadically stable graph classes. arXiv preprint, 2023. arXiv:2311.18740.
  • [17] Jan Dreier, Nikolas Mählmann, and Szymon Toruńczyk. Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 1550–1560, New York, NY, USA, 2024. Association for Computing Machinery. doi:10.1145/3618260.3649739.
  • [18] R. M. Dudley. Central limit theorems for empirical measures. Ann. Probab., 6(6):899–929, 1978.
  • [19] Vida Dujmović, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, and Pat Morin. Adjacency labelling for planar graphs (and beyond). Journal of the ACM (JACM), 68(6):1–33, 2021. doi:10.1145/3477542.
  • [20] Zdeněk Dvořák. Asymptotical structure of combinatorial objects. PhD thesis, 2007.
  • [21] Zdeněk Dvořák. Induced subdivisions and bounded expansion. Eur. J. Comb., 69:143–148, 2018. doi:10.1016/J.EJC.2017.10.004.
  • [22] Zdenek Dvorák, Daniel Král, and Robin Thomas. Testing first-order properties for subclasses of sparse graphs. J. ACM, 60(5):36:1–36:24, 2013. doi:10.1145/2499483.
  • [23] Zdenek Dvorák and Sergey Norin. Strongly sublinear separators and polynomial expansion. SIAM J. Discret. Math., 30(2):1095–1101, 2016. doi:10.1137/15M1017569.
  • [24] Zdeněk Dvořák and Serguei Norine. Small graph classes and bounded expansion. J. Comb. Theory, Ser. B, 100(2):171–175, 2010. doi:10.1016/J.JCTB.2009.06.001.
  • [25] Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Neighborhood complexity and kernelization for nowhere dense classes of graphs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, volume 80 of LIPIcs, pages 63:1–63:14, 2017. doi:10.4230/LIPICS.ICALP.2017.63.
  • [26] Jacob Fox and János Pach. Applications of a new separator theorem for string graphs. Comb. Probab. Comput., 23(1):66–74, 2014. doi:10.1017/S0963548313000412.
  • [27] Delbert Fulkerson and Oliver Gross. Incidence matrices and interval graphs. Pacific journal of mathematics, 15(3):835–855, 1965.
  • [28] Cyril Gavoille and Arnaud Labourel. Shorter implicit representation for planar graphs and bounded treewidth graphs. In 15th Annual European Symposium on Algorithms, ESA 2007, volume 4698 of LNCS, pages 582–593. Springer, 2007. doi:10.1007/978-3-540-75520-3_52.
  • [29] Ralucca Gera, Stephen Hedetniemi, and Craig Larson, editors. Graph theory—favorite conjectures and open problems. 1. Problem Books in Mathematics. Springer, 2016.
  • [30] Paul W Goldberg, Martin C Golumbic, Haim Kaplan, and Ron Shamir. Four strikes against physical mapping of DNA. Journal of Computational Biology, 2(1):139–152, 1995. doi:10.1089/cmb.1995.2.139.
  • [31] Frank Gurski and Egon Wanke. The tree-width of clique-width bounded graphs without Kn,n. In Graph-Theoretic Concepts in Computer Science, 26th International Workshop, WG 2000, volume 1928 of LNCS, pages 196–205. Springer, 2000. doi:10.1007/3-540-40064-8_19.
  • [32] Phil Hanlon. Counting interval graphs. Transactions of the American Mathematical Society, 272(2):383–426, 1982.
  • [33] Hamed Hatami and Pooya Hatami. The implicit graph conjecture is false. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022), pages 1134–1137. IEEE, 2022. doi:10.1109/FOCS54457.2022.00109.
  • [34] David Haussler. Sphere Packing Numbers for Subsets of the Boolean n-Cube with Bounded Vapnik-Chervonenkis Dimension. J. Comb. Theory, Ser. A, 69(2):217–232, 1995.
  • [35] Sampath Kannan, Moni Naor, and Steven Rudich. Implicit representation of graphs. In Proceedings of the twentieth annual ACM symposium on Theory of computing (STOC 1988), pages 334–343, 1988. doi:10.1145/62212.62244.
  • [36] Sampath Kannan, Moni Naor, and Steven Rudich. Implicit representation of graphs. SIAM Journal on Discrete Mathematics, 5(4):596–603, 1992. doi:10.1137/0405049.
  • [37] Tamás Kővári, Vera T. Sós, and Pál Turán. On a problem of Zarankiewicz. In Colloquium Mathematicum, volume 3, pages 50–57. Polska Akademia Nauk, 1954.
  • [38] Ilia Krasikov, Arieh Lev, and Bhalchandra D Thatte. Upper bounds on the automorphism group of a graph. Discrete Mathematics, 256(1-2):489–493, 2002. doi:10.1016/S0012-365X(02)00393-X.
  • [39] Daniela Kühn and Deryk Osthus. Induced subdivisions in Ks,s-free graphs of large average degree. Comb., 24(2):287–304, 2004. doi:10.1007/S00493-004-0017-8.
  • [40] Jiří Matoušek. Geometric discrepancy, volume 18 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 2010. An illustrated guide, Revised paperback reprint of the 1999 original. doi:10.1007/978-3-642-03942-3.
  • [41] John H. Muller. Local Structure in Graph Classes. PhD thesis, Georgia Institute of Technology, 1988.
  • [42] Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. doi:10.1007/978-3-642-27875-4.
  • [43] Serguei Norine, Paul Seymour, Robin Thomas, and Paul Wollan. Proper minor-closed families are small. Journal of Combinatorial Theory, Series B, 96(5):754–757, 2006. doi:10.1016/j.jctb.2006.01.006.
  • [44] Richard Otter. The number of trees. Ann. of Math. (2), 49:583–599, 1948. doi:10.2307/1969046.
  • [45] Felix Reidl, Fernando Sánchez Villaamil, and Konstantinos Stavropoulos. Characterising bounded expansion by neighbourhood complexity. European Journal of Combinatorics, 75:152–168, 2019. doi:10.1016/j.ejc.2018.08.001.
  • [46] Jeremy P Spinrad. Efficient Graph Representations, volume 19. Fields Institute monographs. American Mathematical Soc., 2003. URL: http://www.ams.org/bookstore-getitem/item=fim-19.
  • [47] William Thomas Tutte. A census of planar triangulations. Canadian Journal of Mathematics, 14:21–38, 1962.
  • [48] Emo Welzl. Partition trees for triangle counting and other range searching problems. In Herbert Edelsbrunner, editor, Proceedings of the Fourth Annual Symposium on Computational Geometry (SoCG 1988), pages 23–33. ACM, 1988. doi:10.1145/73393.73397.
  • [49] Édouard Bonnet, Julien Duron, John Sylvester, and Viktor Zamaraev. Adjacency labeling schemes for small classes, 2024. doi:10.48550/arXiv.2409.04821.

Appendix A Paths with low crossing number

The main goal of this section is to provide a self-contained proof of Theorem 18. To state the theorem, we recall definitions of some crucial notions. Given a set system (X,𝒮), we say that a set S𝒮 crosses a 2-element set {x,y}X if exactly one of x and y belongs to S. Let be a multiset of 2-element subsets in X. The crossing number of with respect to a set S𝒮 is the number of elements in that are crossed by S. The crossing number of with respect to 𝒮 is the maximum crossing number of with respect to a set S𝒮. If (X,), considered as a graph, is a tree or a path spanning all elements of X, then we say that (X,) is a tree or a path on X, respectively. In this case, the crossing number of is referred to as the crossing number of the corresponding tree or path, respectively.

See 18

This theorem is a known result stated in an unusual form, but one that is useful for us. The main feature of the above formulation is that the bound on the dual shatter function is given in a general form (expressed as a function f) rather than polynomial; in turn, the bound on the crossing number is expressed via the inverse of f. More specifically, the above formulation has two main differences compared to the standard one (for instance [40, 48]). First, in a standard formulation, the bound on the dual shatter function is π𝒮(m)mr for some constant r>1. Second, the resulting bound on the crossing number of a path on X is in the form of O(n11/r). Note that if we take f(m) to be mr in Theorem 18, then f1(m)=m1/r and

2log|𝒮|+10dj=1n1(j/2)1/r

can be upper bounded by O(n11/r), which recovers the result in a standard form.

The benefit of the present formulation is that one can apply Theorem 18 when a preferable upper bound on π𝒮(m) is non-polynomial. For example, if f(m)=mg(m) for some non-decreasing function g(m), then Theorem 18 gives a bound of O(g(n)logn) on the crossing number. In particular, this becomes useful when g(m)=mo(1); e.g., if g(m)=log(m), the bound on the crossing number becomes O(log2n).

To provide a self-contained proof of Theorem 18, we need to state a number of auxiliary known results in a suitable (non-standard) form and repeat their proofs with some adjustments. Before each statement we explain how its formulation and proof differs from standard ones. We hope this exposition might be of use in some other work.

Packing lemma

We begin with Haussler’s Packing Lemma [34] (Lemma 23), which is an improvement over a quantitatively weaker Packing Lemma obtained by Dudley [18] and re-discovered by Welzl [48]. The proof below is a simplification by Chazelle of Haussler’s proof [34], which is taken from Matoušek’s book [40].

A set system (X,𝒮) is δ-separated if for any two distinct sets S1,S2𝒮 their symmetric difference contains at least δ elements, i.e., |(S1S2)(S2S1)|δ. In a standard formulation, the lemma assumes that the shatter function π𝒮(m) is bounded by O(mr) for some r, and the bound on the cardinality of a δ-separated set 𝒫 is O((n/δ)r). For our purposes, in Lemma 23, we state the bound on |𝒫| directly in terms of the shatter function. Note that the standard form of the lemma follows from ours if one uses the bound π𝒮(m)=O(mr). The difference of the proof below from the one in [40] is that in Equation 13 we bound t in terms of the shatter function directly, rather than in terms of the bound on the shatter function.

Lemma 23 (Packing Lemma, see [40, Lemma 5.14]).

Let (X,𝒮) be a set system on an n-element set of VC dimension d. Let δ[n] be an integer, and let 𝒫𝒮 be δ-separated. Then,

|𝒫|2π𝒮(4dnδ).

Before we prove this lemma we must introduce an auxiliary graph construction. For a set system (X,𝒮), we define the unit distance graph UD(𝒮) to be the graph with

V(UD(𝒮))=𝒮andE(UD(𝒮))={{S,S}:|SΔS|=1}.

We will also need the following bound on the number of its edges.

Lemma 24 ([40, Lemma 5.15]).

If (X,𝒮) is a set system of VC dimension d on a finite set X then the unit distance graph UD(𝒮) has at most d|𝒮| edges.

With this, we are now ready to prove the Packing Lemma.

Proof of Lemma 23.

Choose a random s-element subset AX, where s is given by

s:=4dnδ. (9)

Set 𝒬:={SA:S𝒫}, and for each set Q𝒬 define its weight w(Q) as the number of sets S𝒫 with SA=Q. Note that

Q𝒬w(Q)=|𝒫|.

Let E:=E(UD(𝒬)) be the edge set of the unit distance graph UD(𝒬), and define an edge weighting of UD(𝒬) by giving each edge e={Q,Q}E weight w(e):=min(w(Q),w(Q)). Let

W=eEw(e),

where we note that this random variable depends on the random choice of A. The desired bound on |𝒫| in the Packing Lemma is obtained by estimating the expectation of W in two different ways.

First, we claim that for any set AX, we have the following (deterministic) bound on W

W2dQ𝒬w(Q)=2d|𝒫|. (10)

To see this, note first that the VC dimension of 𝒫 is at most d, and thus, by Lemma 24, the unit distance graph UD(𝒬) has some vertex Q0 of degree at most 2d. By removing Q0, the total edge weight drops by at most 2dw(Q0), and we are left with a unit distance graph on (X,𝒬), where 𝒬=𝒬Q0 and 𝒬 has VC dimension at most d. We can thus repeat this process until no vertices are left, and we see that the sum of edge weights removed is at most 2d times the sum of vertex weights, as claimed.

Next, we bound the expectation 𝔼[W] from below by considering the following random experiment. First, we choose a random (s1)-element set AX, and then we choose a random element aXA. The set A=A{a} is a uniform random s-element subset of X, we consider UD(𝒬) with the same edge weighting as above. Each edge of UD(𝒬) is a pair of sets of 𝒬 differing in exactly one element of A. We let E1E be the edges for which the difference element is a, and let W1 be the sum of their weights. By symmetry, we have

𝔼[W]=s𝔼[W1]. (11)

We are going to bound 𝔼[W1] from below. Let AX be an arbitrary but fixed (s1)-element set. We estimate the conditional expectation 𝔼[W1A]; that is, the expected value of W1 when conditioned on a fixed set A, and aXA is selected uniformly at random. Divide the sets of 𝒫 into equivalence classes 𝒫1,𝒫2,,𝒫t according to their intersection with the set A. By the definition of π𝒮(x) and since it is non-decreasing, we have

tπ𝒮(s1)π𝒮(s). (12)

Let 𝒫i be one of the equivalence classes, and b:=|𝒫i|. Suppose that an element aXA has been chosen. If b1 sets of 𝒫i contain a and b2=bb1 sets do not contain a, then the class 𝒫i gives rise to an edge of E1 of weight min(b1,b2). Note that b1 and b2 depend on the choice of a while b does not.

For any non-negative real numbers b1,b2 with b1+b2=b, we have min(b1,b2)b1b2/b. The value b1b2 is the number of ordered pairs of sets (S1,S2) with S1,S2 being two sets from the class 𝒫i where one contains a and the other one does not. Now, since 𝒫 is δ-separated by hypothesis, if S1,S2𝒫i are two distinct sets, then they differ in at least δ elements. Therefore, the probability that S1 and S2 differ in a random element aXA is at least δns+1δ/n. Hence the expected contribution of each pair (S1,S2) of distinct sets of 𝒫i to the quantity b1b2 is at least δ/n, thus

𝔼[b1b2A]b(b1)δn.

Consequently, the expected contribution 𝔼[min(b1,b2)A] of the equivalence class 𝒫i to the sum of edge weights W1 is at least 𝔼[b1b2/bA](b1)δ/n. Summing up over all equivalence classes, and using the bound on t from (12),

𝔼[W1]𝔼[W1A]δni=1t(|𝒫i|1)δn(|𝒫|t)δn(|𝒫|π𝒮(s)). (13)

Combining this with the estimate (10), the equality (11), and the definition (9) of s, leads to

2d|𝒫|sδn(|𝒫|π𝒮(s))4d(|𝒫|π𝒮(s)).

Rearranging gives |𝒫|2π𝒮(s), so the statement follows from (9).

Short Edge Lemma

A standard form of the Short Edge Lemma assumes a polynomial bound on the dual shatter function, i.e., π𝒮(m)=O(mr) for some constant r>1, and the resulting bound is expressed via the bound O(m1/r) on the inverse of π𝒮(m). In our presentation of the Short Edge Lemma (Lemma 25) below we use a bound on the dual shatter function in a general from expressed as a function f, and the resulting bound is stated in terms of f1, the inverse of f. As before, by plugging in the bound π𝒮(m)=O(mr) in Lemma 25 one would recover the standard form of the lemma. The proof is taken from [40] with suitable adjustments.

Lemma 25 (Short Edge Lemma, see [40, Lemma 5.18]).

Let X be an n-element set, f:00 be a strictly increasing function, and d be a natural number. Let (X,𝒮) be a set system of VC dimension d with π𝒮(m)f(m) for all m[n]. Then, for any multiset 𝒬 with elements from 𝒮, there exist elements x,yX such that the edge {x,y} is crossed by at most

5d|𝒬|f1(n/2)

sets of 𝒬.

Proof.

We form a set system 𝒟 which is dual to 𝒬. That is, we consider the multiset 𝒬 as the ground set (if some set appears in 𝒬 several times, then it is considered with the appropriate multiplicity). For each xX, we let Dx be the set of all sets of 𝒬 containing x, and we set

𝒟={Dx:xX}.

The symmetric difference DxΔDy of two sets from 𝒟 consists of the sets in 𝒬 crossing the pair {x,y}. We thus want to show that DxΔDy is small for some xy. We may assume DxDy for xy, as otherwise we are done, and hence |𝒟|=|X|=n.

The primal shatter function π𝒟 is certainly no larger than the dual shatter function π𝒮, and hence π𝒟(m)f(m) by the assumption on π𝒮. Suppose that any two sets Dx,Dy𝒟 have symmetric difference at least δ, then the packing lemma (Lemma 23) implies

n=|𝒟|2π𝒮(4d|𝒬|δ)2f(4d|𝒬|δ).

Since f is strictly increasing, f1 is also strictly increasing. Therefore, we have

f1(n/2)4d|𝒬|δ5d|𝒬|δ,

and therefore

δ5d|𝒬|f1(n/2),

as claimed.

Trees with low crossing number

As with the Short Edge Lemma, the following result (Theorem 26) is stated with a general bound f on the dual shatter function and the resulting bound on the crossing number of a tree is expressed in terms of f1, the inverse of f. The proof is taken from [40], which is very similar to Welzl’s original proof [48]. The statement in [40] is for crossing number of matchings, and therefore it is slightly modified to work for trees as in [48].

Theorem 26 (see [40, Lemma 5.17]).

Let X be an n-element set, f:00 be a strictly increasing function, and d be a natural number. Let (X,𝒮) be a set system of VC dimension d with π𝒮(m)f(m) for all m[n]. Then there exists a tree T on X with crossing number at most

log|𝒮|+5dj=1n1f1(j/2).
Proof.

We build T by selecting edges one by one according to the following strategy.

  1. 1.

    Suppose {u1,v1},,{ui,vi} have already been selected.

  2. 2.

    Define the weight wi(S) of a set S𝒮 as 2ki(S), where ki(S) is the number of edges among {u1,v1},,{ui,vi} crossed by S. In particular, w0(S)=1 for all S𝒮.

  3. 3.

    We select the next edge {ui+1,vi+1} from Xi=X{u1,u2,,ui} as a pair of points with the total weight of sets crossing {ui+1,vi+1} being the smallest possible.

  4. 4.

    We continue in this manner until n1 edges have been selected.

Let E:={{u1,v1},{u2,v2},{un1,vn1}}. Then T=(X,E) is a tree. Next, we will bound the crossing number k of the resulting tree T. To this end, we estimate the final total weight of all sets of 𝒮, i.e.,

wn1(𝒮)=S𝒮wn1(S).

By definition of wn1 we have klogwn1(𝒮).

Let us investigate how wi+1(𝒮) increases compared to wi(𝒮). Let 𝒮i+1 denote the collection of the sets of 𝒮 crossing {ui+1,vi+1}. For each set in 𝒮i+1 the weight increases by a multiplicative factor of two, and for the other sets it remains unchanged. From this we get

wi+1(𝒮)=wi(𝒮)wi(𝒮i+1)+2wi(𝒮i+1)=wi(𝒮)[1+wi(𝒮i+1)wi(𝒮)].

We now estimate wi(𝒮i+1)wi(𝒮) using the Short Edge Lemma (Lemma 25). To begin we define a multiset 𝒬i of sets by adding SXi to 𝒬i with multiplicity wi(S) for every S𝒮. Thus

|𝒬i|=S𝒮wi(S)=wi(𝒮).

Note that, by the construction of 𝒬i, the number of sets in 𝒬i that cross {ui+1,vi+1} is wi(𝒮i+1). Furthermore, by our choice of edge in (2) and (3), the edge {ui+1,vi+1} is crossed by the minimum number of sets in 𝒬i. Thus, by applying the Short Edge Lemma on the set system (Xi,{SXi:S𝒮}) to the multiset 𝒬i, and defining ni:=|Xi|=ni, we obtain:

wi(𝒮i+1)5dwi(𝒮)f1(ni/2).

Hence, we have

wi+1(𝒮)wi(𝒮)[1+5df1((ni)/2)].

Therefore

wn1w0(𝒮)i=0n1[1+5df1((ni)/2)]=|𝒮|j=1n[1+5df1(j/2)].

Taking logarithms of both sides and using the inequality ln(1+x)x we obtain

k logwn1(𝒮)log|𝒮|+5dj=1n1f1(j/2),

as claimed.

From a tree to a path

Finally, Theorem 18 is obtained from Theorem 26 by using the following Lemma 27 to “convert” a tree with crossing number k to a path with crossing number at most 2k. The argument is taken from [48] and we provided it here for completeness.

Lemma 27 ([48, Lemma 3.3]).

Let (X,𝒮) be a set system, and T be a tree on X with crossing number at most k with respect to 𝒮. Then, there exists a path on X with crossing number at most 2k with respect to 𝒮.

Proof.

We begin with the following claim.

Claim 28.

Given any family of two element sets on X, replacing any pair {x,y},{y,z} by the set {x,z} will not increase the crossing number with respect to 𝒮.

Proof of Claim.

If any S𝒮 crosses {x,z}, then exactly one of x or y is not contained in S. Thus, S must cross one of {x,y} or {y,z}. Let 𝒟={{u1,u2},{u2,u3},,{u1,u}} be a multiset consisting of edges from T in the order they are traversed in a depth-first search (DFS) tour333A DFS tour visits all vertices of the tree starting from a given vertex and going as far as possible down a given branch, then backtracking until it finds an unexplored path. of T starting from an arbitrary vertex. Additionally, let x1,,xn be a labeling of X in the order they are discovered by the DFS tour 𝒟.

Note that each edge of T appears exactly twice in 𝒟, thus the crossing number of 𝒟 is at most 2k. We can now apply Claim 28 iteratively to reduce 𝒟 to {{x1,x2},{x2,x3},, {xn1,xn}} without increasing the crossing number with respect to 𝒮.