PreprintCC BY-NC-SA 4.0arXiv
On Colorful Kruskal--Katona Theorems
Abstract
What is the maximum number of rainbow triangles in an edge-colored graph with m edges and r colors? Using entropic techniques, we prove an upper bound of Crm3/2 rainbow triangles with Cr=√((2(r−2))/9r); this constant is best possible whenever there exists an affine plane of order r−1. We also show that constructions attaining at least (Cr−εr)m3/2 rainbow triangles must exhibit an affine plane structure, which further improves the upper bound if no such affine plane exists. We also consider the problem of counting properly edge-colored cliques of larger sizes. Surprisingly, if the number r of colors is odd, this count is instead maximized by blowups of a properly edge-colored Kr+1.
Related
- Dimensional colorful Helly theorems and topological variants
- Kruskal-style algorithm for Boltzmann equation molecule reduction
- Mapping Schwarzschild Spacetime: From Kruskal to Diamond and Golden Representations
- On the Number of Iterations in a Kruskal-Type Process
- Beyond Kruskal: Polynomial-Time Tensor Decomposition under the Lovitz-Petrov Condition
BibTeX
@misc{chao2026colorful,
title = {{On Colorful Kruskal--Katona Theorems}},
author = {Ting-Wei Chao and Maya Sankar and Hung-Hsun Hans Yu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02165},
eprint = {2610.02165},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02165},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - On Colorful Kruskal--Katona Theorems
AU - Ting-Wei Chao
AU - Maya Sankar
AU - Hung-Hsun Hans Yu
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02165
UR - https://arxiv.org/abs/2610.02165
AB - What is the maximum number of rainbow triangles in an edge-colored graph with m edges and r colors? Using entropic techniques, we prove an upper bound of C_rm^3/2 rainbow triangles with C_r=√((2(r−2))/9r); this constant is best possible whenever there exists an affine plane of order r−1. We also show that constructions attaining at least (C_r−ε_r)m^3/2 rainbow triangles must exhibit an affine plane structure, which further improves the upper bound if no such affine plane exists. We also consider the problem of counting properly edge-colored cliques of larger sizes. Surprisingly, if the number r of colors is odd, this count is instead maximized by blowups of a properly edge-colored K_r+1.
ER -