by J. A. Makowsky and V. Rakita. On Weakly Distinguishing Graph Polynomials. Discrete Mathematics & Theoretical Computer Science (Oct. 31, 2018). arXiv: 1810.13300 [math.CO]. Submitted.
Let \(P\) be a graph polynomial. A graph \(G\) is \(P\)-unique if every graph \(H\) with \(P(G)=P(H)\) is isomorphic to \(G\). A graph \(H\) is a \(P\)-mate of \(G\) if \(P(G)=P(H)\) and \(H\) is not isomorphic to \(G\). It is a natural question to ask whether a given graph polynomial distinguishes graphs. Literature about such questions mainly focused on finding (families of) \(P\)-unique graphs. One of the main graph polynomials under investigation is the Tutte polynomial \(T\). One knows several families of \(T\)-unique graphs. On the contrary it is known for example that all trees of the same order share the same Tutte polynomial. Moreover Bollobas, Pebody and Riordan have proven that there exist non-isomorphic \(k\)-connected graphs with the same Tutte polynomial, for any \(k\).
The two authors of the present article follow a different approach. Instead of trying to find \(P\)-unique graphs, they are interested in determining the asymptotic proportion of $P$-unique graphs. \(P\) is weakly distinguishing if a uniform random graph has a \(P\)-mate asymptotically almost surely. In this article, the authors prove that many graph polynomials (not including the Tutte polynomial) are weakly distinguishing. In other words, for many graph polynomials, a graph is a.a.s. not unique.
Definitions and results
Denote by \(\mathcal{G}(n)\) the set of simple labelled graphs with \(n\) vertices and by \(\mathcal{G}\) the set of all simple labelled graphs. Let \(P:\mathcal{G}\to\mathbb{Z}[x]\) be a graph polynomial. Denote by \(U_P(n)\) the set of \(P\)-unique graphs of order \(n\), and by \(\beta_P(n)\) the cardinality of the image of \(\bigcup_{k=0}^n\mathcal{G}(k)\) by \(P\). Remark that \(P\) is weakly distinguishing if \(\lim_{n\to\infty}\frac{|U_P(n)|}{|\mathcal{G}(n)|}=0\). For a family \(\mathcal{C}\) of graphs, we also note \(\beta_{P,\mathcal{C}}(n)\) the cardinality of the image of \(\bigcup_{k=0}^n\mathcal{G}(k)\cap\mathcal{C}\) by \(P\).
Let \(G=(V,E)\) be a graph and \(A\subset V\). The subgraph of \(G\) induced by \(A\) is denoted by \(G[A]\).
Let \(Q\) be a graph property. The graph polynomial associated to \(Q\) is defined as \[P_Q(G;x)=\sum_{\substack{A\subset V(G),\\G[A]\in Q}}x^{|A|}.\]
For a vertex \(v\in V(G)\), let \(d_G(v)\) denote the degree of \(v\) in \(G\).
The degree polynomial \(Deg(G;x)\) is defined as \(\sum_{v\in V(G)}x^{d_G(v)}\).
For a fixed \(m\in\mathbb{N}\) and a graph \(G\), we say that a proper colouring \(f:V(G)\to [k]\) of \(G\) with \(k\) colours is \(m\)-harmonious if for every \(S\subset [k]\) of cardinality \(m\), \(S\) is the colour set of a clique in \(G\) at most once. The \(m\)-harmonious polynomial of \(G\) is defined as the number \(h_m(G;k)\) of \(m\)-harmonious colourings of \(G\) with \(k\) colours. It is indeed a polynomial in \(k\).
Let \(Q\) be a graph property. We say that a function \(f:\mathbb{N}\to\mathbb{N}\) is an independence (resp. a clique) function for \(Q\) if for every graph \(G\in Q\), \(G\) has an independent set (resp. a complete subgraph) with \(f(|V(G)|)\) vertices.
\(Deg\) is weakly distinguishing.
\(h_m\) is weakly distinguishing.
Let \(Q\) be a graph property that has an independence or a clique function \(f\) such that for all \(n\in\mathbb{N}\), \(f(n)\geqslant n/a\) for some fixed \(a\in\mathbb{N}\). Then \(P_Q\) is weakly distinguishing.
Which classes of graphs have an independence (or clique) function satisfying the hypothesis of the last theorem?
- Cliques and independent sets (obviously),
- \(k\)-degenerate graphs (i.e. graphs in which every induced subgraph has a vertex of degree at most \(k\)). They have an independent set of size \(\lceil\frac{n}{k+1}\rceil\). Among \(k\)-degenerate graphs, one finds graphs with treewidth at most \(k\) and graphs of degree at most \(k\).
- A \(k\)-colourable graph has an independent set of size at least \(\lceil\frac{n}{k}\rceil\).
- Let \(\mathcal{C}\) be a graph property. A function \(\gamma : V(G)\to [k]\) is a \(\mathcal{C}\)-colouring if every color class induces a graph in \(\mathcal{C}\). If \(\mathcal{C}\) has an independence (resp. clique) function \(g\), then the graphs which are \(\mathcal{C}\)-colourable with at most \(k\) colours have an independence (clique) function \(f(n)=\lceil\frac{g(n)}{k}\rceil\).
Ideas of proofs
First theorem
This is a simple, but clever, counting argument. First of all, it is a fact that the number of simple graphs of order \(n\) is asymptotically equal to \(2^{\binom{n}2}/n!\). Now, note that the degree of a vertex in such a graph is bounded above by \(n-1\) so that the degree of \(Deg\) is at most \(n-1\). Moreover for every \(0\leqslant i\leqslant n-1\), the coefficient of \(x^i\) in \(Deg\) is an integer between \(0\) and \(n\). Thus, \(\beta_{Deg}(n)\leqslant (n+1)^n\). Finally, \[\frac{|U_P(n)|}{|\mathcal{G}(n)|}\leqslant\frac{\beta_{Deg}(n)}{|\mathcal{G}(n)|}\to 0\text{ as }n\to\infty.\]
Second theorem
The proof of the second theorem requires the following
Let \(P\) be a graph polynomial and \(\mathcal{C}\) be a family of graphs such that \(\lim_{n\to\infty}|\mathcal{C}(n)|/|\mathcal{G}(n)|=1.\) If \(\lim_{n\to\infty}|U_P(n)\cap\mathcal{C}(n)|/|\mathcal{G}(n)|=0\) then \(P\) is weakly distinguishing.
Then Makowsky and Rakita identify such a class of graphs:
Let \(\mathcal{C}\) be the class of graphs \(G\) with the property that for every two vertices \(u,v\in V(G)\), there are vertices \(w_1,w_2,\dotsc,w_{m-1}\in V(G)\) such that \(\{u,w_1,\dotsc,w_{m-1}\}\) and \(\{v,w_1,\dotsc,w_{m-1}\}\) induce a complete graph. Then almost all graphs are in \(\mathcal{C}\).
Finally they use the fact that \(h_m(G;k)\) is constant on each \(\mathcal{C}(n)\) (because any \(m\)-harmonious colouring of \(G\in\mathcal{C}\) has to assign a different colour to each vertex).
Third theorem
Its proof relies on the previous lemma about asymptotically full classes and on the two following theorems: by Frieze
For a graph \(G\), denote by \(\alpha(G)\) the size of its largest independent set of vertices. Then, for almost all graphs of order \(n\), \(\alpha(G)\sim 4\log\frac n 2\).
and by Bollobas and Erdös
Almost all graphs of order \(n\) have a clique of size \(\frac 2{\log 2}\log n\).
Now let \(f\) be an independence function and set \(\epsilon=1/10\). Let \(\mathcal{C}\) be the class of graphs \(G\) with \(\alpha(G)\leqslant 4\log\frac n 2+\epsilon\). By Frieze's theorem, almost all graphs are in \(\mathcal{C}\). If \(G\in\mathcal{C}\), and \(H\) is an induced subgraph of \(G\) with \(H\in Q\), then there is an independent set of size \(\frac{|V(H)|}a\) in \(H\), hence in \(G\) so that \(|V(H)|\leqslant a(4\log\frac n 2+\epsilon)\). This implies that\[P_Q(G;x)=\sum_{k=0}^{a(4\log\frac n 2+\epsilon)}b_k x^k\text{ with }0\leqslant b_k\leqslant\binom{n}{k} \text{ for all }k.\] Thus, \(\beta_{Q,\mathcal{C}}(n)\leqslant\prod_{k=0}^{a(4\log\frac n 2+\epsilon)}\binom{n}{k}\leqslant\binom{n}{a(4\log\frac n 2+\epsilon)}^{a(4\log\frac n 2+\epsilon)}\) and \(\lim_{n\to\infty}|U_P(n)\cap\mathcal{C}(n)|/|\mathcal{G}(n)|=0\).
Recent Comments