Exact bipartite Komlós–Sárközy–Szemerédi conjecture
Exact bipartite Komlós–Sárközy–Szemerédi conjecture
A bipartite graph is balanced when its two parts have equal size, and denotes its minimum degree. A balanced rooted tree on vertices has vertices in each partition class, and denotes its maximum degree.
Exact bipartite Komlós–Sárközy–Szemerédi conjecture. For each , there are such that for every , if is a balanced bipartite graph on vertices with , and is a balanced rooted tree on vertices with , then embeds in with the root of embedded in .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.