Existence of difficult subgraph-counting identities

From papers

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 GvG_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

vV(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

degma(n)+i=1kV(Ja,i)+j=1lV(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 K4K\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,jJ'_{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 K4K\geq4.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.