pipette
ENEnglish

On Colorful Kruskal--Katona Theorems

Ting-Wei Chao, Maya Sankar, Hung-Hsun Hans Yu

Preprint

En palabras de los autores

What is the maximum number of rainbow triangles in an edge-colored graph with edges and colors? Using entropic techniques, we prove an upper bound of rainbow triangles with ; this constant is best possible whenever there exists an affine plane of order . We also show that constructions attaining at least 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 of colors is odd, this count is instead maximized by blowups of a properly edge-colored .

Resultado principalLimitación que admiten los autores

Apareció: viernes, 2 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 42 pages, 4 figures