The graph positivity conjecture

Consider rr-regular bipartite graphs with v=2nv=2n vertices. Let mim_i be the number of ii-matchings, and let mi\overline{m}_i be the number of ii-matchings in the complete graph on the same vertices. Define

d(i)=ln(miri)ln(mi(v1)i),d(i)=\ln\left(\frac{m_i}{r^i}\right)-\ln\left(\frac{\overline{m}_i}{(v-1)^i}\right),

and let Δd(i)=d(i+1)d(i)\Delta d(i)=d(i+1)-d(i). A graph satisfies graph positivity when Δkd(i)0\Delta^k d(i)\geq 0 for all meaningful ii and kk. The graph positivity conjecture. For fixed rr, as nn tends to infinity, the fraction of graphs that satisfy graph positivity approaches one. This conjecture is supported by computer evidence, including the reported behavior for small regular bipartite graphs; the supplied text gives no proof or disproof.

Sources & referencesView supporting material

Primary source

Paul Federbush, “The Genius Conjectures (via Bell Polynomials)”, arXiv:2002.03814 (2020).

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.