PreprintarXiv licencearXiv
Elementary Proofs of Commonality of the House Graph and K4 with One Edge Subdivided
Abstract
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 K4 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.
Related
- Elementary proofs of congruences modulo 5 for overpartitions with restricted odd differences
- An entropy proof of the commonality of apices of trees
- Are New Parties Shut Out of the UK House of Commons?
- Finding Simple Proofs for First-Order Optimization
- An introduction to the strategy of transcendence proofs
BibTeX
@misc{chen2026elementary,
title = {{Elementary Proofs of Commonality of the House Graph and $K_4$ with One Edge Subdivided}},
author = {Hao Chen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20149},
eprint = {2610.20149},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20149},
}
RIS
TY - UNPB
TI - Elementary Proofs of Commonality of the House Graph and K_4 with One Edge Subdivided
AU - Hao Chen
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20149
UR - https://arxiv.org/abs/2610.20149
AB - 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.
ER -