Lower-bound conjecture for spanning trees containing a forest in complete tripartite graphs

Let X1,X2X_1,X_2 and X3X_3 be the partite sets of the complete tripartite graph Kn1,n2,n3K_{n_1,n_2,n_3}, where Xi=ni|X_i|=n_i for i3i\in \llbracket 3\rrbracket. Let FF be a spanning forest in Kn1,n2,n3K_{n_1,n_2,n_3} with kk components T1,T2,,TkT_1,T_2,\ldots,T_k. Write n=n1+n2+n3n=n_1+n_2+n_3 and ns,i=XsV(Ti)n_{s,i}=|X_s\cap V(T_i)| for s=1,2,3s=1,2,3 and iki\in \llbracket k\rrbracket. The lower-bound conjecture. The number τF(Kn1,n2,n3)\tau_F(K_{n_1,n_2,n_3}) of spanning trees of Kn1,n2,n3K_{n_1,n_2,n_3} containing all edges of FF satisfies

τF(Kn1,n2,n3)1n1n2+n1n3+n2n3(i=1k((nn1)n1,i+(nn2)n2,i+(nn3)n3,i))\tau_F(K_{n_1,n_2,n_3})\geq \frac{1}{n_1n_2+n_1n_3+n_2n_3}\left(\prod_{i=1}^{k}\left((n-n_1)n_{1,i}+(n-n_2)n_{2,i}+(n-n_3)n_{3,i}\right)\right) (1i=1kn1,in2,i+n1,in3,i+n2,in3,i(nn1)n1,i+(nn2)n2,i+(nn3)n3,i).\qquad\cdot\left(1-\sum_{i=1}^{k}\frac{n_{1,i}n_{2,i}+n_{1,i}n_{3,i}+n_{2,i}n_{3,i}}{(n-n_1)n_{1,i}+(n-n_2)n_{2,i}+(n-n_3)n_{3,i}}\right).

This conjecture seeks a general lower bound for the number of spanning trees containing a prescribed spanning forest in a complete tripartite graph; its status is not resolved in the supplied source material.

Sources & referencesView supporting material

Primary source

Fengming Dong and Jun Ge, “Counting spanning trees in a complete bipartite graph which contain a given spanning forest”, arXiv:2103.05294 (2022).

Additional references

2 papers in this index state this conjecture (2014–2021). The statement above is taken from the most recent of them; the others are arXiv:1403.2916.

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.