A Note on the Inducibility of -Vertex Graphs

作者：Even Zohar Chaim^*; Linial Nati

来源：Graphs and Combinatorics, 2015, 31(5): 1367-1380.

DOI：10.1007/s00373-014-1475-4

• Inducibility
• Graph density
• Ramsey multiplicity

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 is its extremal density, as an induced subgraph of , where . Already for -vertex graphs many questions are still open. Thus, the inducibility of the -path was addressed in a construction of Exoo (Ars Combin 22:5-10, 1986), but remains unknown. Refuting a conjecture of ErdAs, Thomason (Combinatorica 17(1):125-134, 1997) constructed graphs with a small density of both -cliques and -anticliques. In this note, we merge these two approaches and construct better graphs for both problems.

• 出版日期2015-9