A Note on the Inducibility of 4-vertex Graphs

Abstract

There is much recent interest in understanding the density at which constant size graphs can appear in a very large graph. Specifically, the inducibility of a graph H is its extremal density, as an induced subgraph of G, where |G| -> infinity. Already for 4-vertex graphs many questions are still open. Thus, the inducibility of the 4-path was addressed in a construction of Exoo (1986), but remains unknown. Refuting a conjecture of Erdos, Thomason (1997) constructed graphs with a small density of both 4-cliques and 4-anticliques. In this note, we merge these two approaches and construct better graphs for both problems.

2 tables

References in corpus (6)

• On the minimal monochromatic K4-density
• Counting monochromatic copies of K_4: a new lower bound for the Ramsey multiplicity problem
• The inducibility of blow-up graphs
• On the densities of cliques and independent sets in graphs
• On the local profiles of trees
• On the number of 4-cycles in a tournament

Cited by in corpus (15)

• Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
• Inducibility of directed paths
• Polynomial to exponential transition in Ramsey theory
• Decomposing graphs into edges and triangles
• Stability from graph symmetrisation arguments with applications to inducibility
• The feasible region of induced graphs
• $C_5$ is almost a fractalizer
• On the inducibility of small trees
• Inducibility of d-ary trees
• On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices
• Inducibility of 4-vertex tournaments
• Inducibility of the Net Graph
• Planar graphs with the maximum number of induced 6-cycles
• Inducibility in $H$-free graphs and inducibility of Turán graphs
• Common Pairs of Graphs