Apex conjecture for connected bipartite graphs satisfying Sidorenko's conjecture

Let HH be a connected bipartite graph satisfying Sidorenko's conjecture. For a positive integer aa, let H+aH^{+a} be the graph obtained from HH by adding aa vertices, each adjacent to every vertex of HH, with no edges among the added vertices. Call a graph common when the random 2-edge-colouring asymptotically minimises its monochromatic-copy count.

Apex conjecture. For every positive integer aa, the graph H+aH^{+a} is common. In particular, every complete tripartite graph Kr,s,tK_{r,s,t} is common.

The paper proves commonality for adding arbitrarily many apex vertices when HH is a connected bipartite graph on at most five vertices, but the stated general assertion remains unresolved in the supplied text.

Sources & referencesView supporting material

Primary source

Andrzej Grzesik, Joonkyung Lee, Bernard Lidický and Jan Volec, “On tripartite common graphs”, arXiv:2012.02057 (2022).

Additional references

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

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.