Conjecture on clique counts forcing long cycles in bipartite graphs

Let GG be a connected bipartite graph with bipartition (X,Y)(X,Y). Suppose

X=nY=b,|X|=n\le |Y|=b,

let h=nk2h=\left\lfloor\frac{n-k}{2}\right\rfloor, and assume that δ(G)r1\delta(G)\ge r\ge 1, where n2k+2rn\ge 2k+2r and kZk\in\mathbb{Z}. For positive integers ss and tt, write N(Ks,t,G)N(K_{s,t},G) for the number of copies of Ks,tK_{s,t} in GG. Clique-count long-cycle conjecture. If

N(Ks,t,G)>{max{fs,t(b,n,nk,r),fs,s(b,n,nk,h)},s=t,max{fs,t(b,n,nk,r)+ft,s(b,n,nk,r),\fs,t(b,n,nk,h)+ft,s(b,n,nk,h)},st,N(K_{s,t},G)>\begin{cases}\max\{f_{s,t}(b,n,n-k,r),f_{s,s}(b,n,n-k,h)\},&s=t,\\[2pt]\max\{f_{s,t}(b,n,n-k,r)+f_{t,s}(b,n,n-k,r),\f_{s,t}(b,n,n-k,h)+f_{t,s}(b,n,n-k,h)\},&s\ne t,\end{cases}

then GG contains a cycle of length 2n2k2n-2k. This conjecture proposes a clique-count extremal condition for forcing a cycle of the specified length in a not necessarily balanced bipartite graph; the supplied excerpt gives no resolution or further context for the functions fs,tf_{s,t}, so the claim remains open here.

Sources & referencesView supporting material

Primary source

Changchang Dong, Mei Lu, Jixiang Meng and Bo Ning, “The generalized Tur'an number of long cycles in graphs and bipartite graphs”, arXiv:2406.17371 (2024).

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.