The conjecture that the equal-weight subgraph-count property is quasi-random

Let FF be a graph with e(F)>1e(F)>1, and let m=Fm=|F|. For a graph property P(F;1/m,,1/m)\mathcal P(F;1/m,\dots,1/m) and its weaker version \widetilde\mathcal P(F;1/m,\dots,1/m), the source context defines these as properties concerning equal-weight subgraph counts. Equal-weight subgraph-count conjecture. Theorem~ holds for any graph FF with e(F)>1e(F)>1; equivalently, P(F;1/m,,1/m)\mathcal P(F;1/m,\dots,1/m) and \widetilde\mathcal P(F;1/m,\dots,1/m) are quasi-random properties for every such graph FF. The conjecture extends the theorem proved for regular graphs, stars, and disconnected graphs; the only indicated counterexample is F=K2F=K_2, which has e(F)=1e(F)=1.

Sources & referencesView supporting material

Primary source

Svante Janson and Vera T. Sós, “More on quasi-random graphs, subgraph counts and graph limits”, arXiv:1405.6808 (2014).

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.