On the minimal monochromatic K4-density

Abstract

We use Razborov's flag algebra method to show a new asymptotic lower bound for the minimal density $m_4$ of monochromatic $K_4$'s in any 2-coloring of the edges of the complete graph $K_n$ on $n$ vertices. The hitherto best known lower bound was obtained by Giraud, who proved that m_4>1/46, whereas the best known upper bound by Thomason states that m_4<1/33. We can show that m_4>1/35.

Cited by in corpus (9)

• Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
• A Note on the Inducibility of 4-vertex Graphs
• Minimum number of monotone subsequences of length 4 in permutations
• Variants of the Erdos-Szekeres and Erdos-Hajnal Ramsey problems
• On the 3-local profiles of graphs
• Densities of 3-vertex graphs
• Edges not in any monochromatic copy of a fixed graph
• Ramsey multiplicity and the Turán coloring
• Graphs with few 3-cliques and 3-anticliques are 3-universal