Existence of difficult subgraph-counting identities

About 16 years old · traced to

Let GG be a graph with nn vertices. For a graph JJ, write s(J,G)s(J,G) for the number of induced subgraphs of GG isomorphic to JJ; let Gv−G_v^- and Gv+G_v^+ denote the subgraphs induced by the vertices not adjacent and adjacent to vv, respectively. A subgraph-counting identity has the form

∑v∈V(G)∑a=1Nma(n)∏i=1ks(Ja,i,Gv−)∏j=1ls(Ja,j′,Gv+)=0.\sum_{v\in V(G)} \sum_{a=1}^N m_a(n) \prod_{i=1}^k s(J_{a,i},G^-_v) \prod_{j=1}^l s(J'_{a,j},G^+_v)=0.

Here ma(n)m_a(n) are polynomials in nn, and the complexity condition is

deg⁡ma(n)+∑i=1k∣V(Ja,i)∣+∑j=1l∣V(Ja,j′)∣≤K\deg m_a(n)+\sum_{i=1}^k |V(J_{a,i})|+\sum_{j=1}^l |V(J'_{a,j})|\leq K

for every aa.

Existence conjecture. For every K≥4K\geq 4, there is such an identity that holds for every graph GG with nn vertices, has one graph Ja,iJ_{a,i} or Ja,j′J'_{a,j} with KK vertices, and is not in one of the easily described families.

The paper's proved identity supplies the first example outside the previously known easily described families. The conjecture proposes that difficult identities continue to exist at every complexity level K≥4K\geq4.

References

Primary source

Alexander Engstrom, “A proof of the McKay-Radziszowski subgraph counting conjecture”, arXiv:1002.4304 (2010).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.