Exact bipartite Komlós–Sárközy–Szemerédi conjecture

A bipartite graph G=(A,B,E)G=(A,B,E) is balanced when its two parts have equal size, and δ(G)\delta(G) denotes its minimum degree. A balanced rooted tree on 2n2n vertices has nn vertices in each partition class, and Δ(T)\Delta(T) denotes its maximum degree.

Exact bipartite Komlós–Sárközy–Szemerédi conjecture. For each γ>0\gamma>0, there are c,n0>0c,n_0>0 such that for every nn0n\ge n_0, if G=(A,B,E)G=(A,B,E) is a balanced bipartite graph on 2n2n vertices with δ(G)(12+γ)n\delta(G)\ge(\frac12+\gamma)n, and TT is a balanced rooted tree on 2n2n vertices with Δ(T)cnlogn\Delta(T)\le\frac{cn}{\log n}, then TT embeds in GG with the root of TT embedded in AA.

This is proposed as the direct bipartite analogue of the Komlós–Sárközy–Szemerédi theorem. The source describes it as a belief rather than a proved result, so it remains open.

Sources & referencesView supporting material

Primary source

Cristina G. Fernandes, Tássio Naia, Giovanne Santos and Maya Stein, “Packing large balanced trees into bipartite graphs”, arXiv:2410.13290 (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.