pith. machine review for the scientific record. sign in

arxiv: 1211.4532 · v2 · submitted 2012-11-19 · 🧮 math.CO

Recognition: unknown

On the densities of cliques and independent sets in graphs

Authors on Pith no claims yet
classification 🧮 math.CO
keywords blueedgescoloringextremalknownnumberanalyticalanswers
0
0 comments X
read the original abstract

Let r, s >= 2 be integers. Suppose that the number of blue r-cliques in a red/blue coloring of the edges of the complete graph K_n is known and fixed. What is the largest possible number of red s-cliques under this assumption? The well known Kruskal-Katona theorem answers this question for r=2 or s=2. Using the shifting technique from extremal set theory together with some analytical arguments, we resolve this problem in general and prove that in the extremal coloring either the blue edges or the red edges form a clique.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.