EUVIMEDEUVIMED entdecken
Crossref

Disconnected Common Graphs via Supersaturation

Jae-baek Lee, Jonathan Noel

The Electronic Journal of Combinatorics · 14.04.2026 · 33 (2)

DOI: 10.37236/12664 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 14.04.2026. Verfasst von Jae-baek Lee und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A graph $H$ is said to be \emph{common} if the number of monochromatic labelled copies of $H$ in a $2$-colouring of the edges of a large complete graph is asymptotically minimized by a random colouring. It is well known that the disjoint union of two common graphs may be uncommon; e.g., $K_2$ and $K_3$ are common, but their disjoint union is not. We investigate the commonality of disjoint unions of multiple copies of $K_3$ and $K_2$. As a consequence of our results, we obtain an example of a pair of uncommon graphs whose disjoint union is common. Our approach is to reduce the problem of showing that certain disconnected graphs are common to a constrained optimization problem in which the constraints are derived from supersaturation bounds related to Razborov's Triangle Density Theorem. We also improve bounds on the Ramsey multiplicity constant of a triangle with a pendant edge and the disjoint union of $K_3$ and $K_2$.

Zitieren

APA

Lee, J., & Noel, J. (2026). Disconnected Common Graphs via Supersaturation. The Electronic Journal of Combinatorics, 33(2). https://doi.org/10.37236/12664

Vancouver

Lee J, Noel J. Disconnected Common Graphs via Supersaturation. The Electronic Journal of Combinatorics. 2026;33(2). doi:10.37236/12664

BibTeX
@article{Lee2026,
  author = {Lee, Jae-baek and Noel, Jonathan},
  title = {Disconnected Common Graphs via Supersaturation},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  volume = {33},
  number = {2},
  doi = {10.37236/12664}
}
Kostenlos starten →