Family-size stabilization conjecture for complete multipartite graphs

Let n3n \geq 3, let 1a1an1 \leq a_1 \leq \cdots \leq a_n, and define

e=#E(Ka1,,an1).e = \#E(K_{a_1, \ldots, a_{n-1}}).

If a1++an1>6a_1 + \cdots + a_{n-1} > 6 and anea_n \geq e, then the family-size stabilization conjecture asserts that

F(Ka1,,an1,e1)=F(Ka1,,an1,an)1.\left|\mathcal{F}(K_{a_1, \ldots, a_{n-1}, e-1})\right| = \left|\mathcal{F}(K_{a_1, \ldots, a_{n-1}, a_n})\right| - 1.

Here Ka1,,anK_{a_1,\ldots,a_n} is the complete multipartite graph with part sizes a1,,ana_1,\ldots,a_n, #E(G)\#E(G) denotes the number of edges of GG, and F(G)\mathcal{F}(G) denotes the family of graphs obtainable from GG by sequences of Triangle-Y and Y-Triangle moves. The conjecture predicts a precise one-unit difference between the family sizes at the indicated parameters, extending the pattern observed in the tables and the proved stabilization result for the related family-size function. The general assertion remains open in the source.

Sources & referencesView supporting material

Primary source

Danielle Gregg, Thomas W. Mattman, Zachary Porat and George Todd, “Family sizes for complete multipartite graphs”, arXiv:2008.12975 (2021).

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.