Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper provides elementary, flag-algebra-free proofs for the commonality of the house graph and $K_4$ with one edge subdivided. Commonality, in this context, means that random 2-edge-colorings of large complete graphs asymptotically minimize the number of monochromatic copies of these specific graphs. The key result is the successful derivation of this property without relying on the computationally intensive flag algebra method.
Human-friendly proofs reveal that the house graph and $K_4$ with a subdivided edge are common, bypassing complex flag algebra.
A graph $H$ is called common if the number of monochromatic copies of $H$ in a $2$-edge-coloring of a large complete graph is asymptotically minimized by the random coloring with an equal proportion of each color. The house graph and $K_4$ with one edge subdivided once are known to be common by the flag algebra method. Grzesik, Lee, Lidický, and Volec asked for ``human-friendly'' proofs of the commonality of these two graphs. In this short note, we give flag-algebra-free proofs that both graphs are common.