A note on the inducibility of 4-vertex graphs

DOI10.1007/S00373-014-1475-4zbMATH Open1321.05143arXiv1312.1205OpenAlexW2120140145MaRDI QIDQ497330FDOQ497330

Authors: Nathan Linial, Chaim Even-Zohar 

Publication date: 24 September 2015

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1312.1205

Recommendations

• The inducibility of graphs on four vertices
• On the inducibility of oriented graphs on four vertices
• Inducibility of directed paths
• On the exact maximum induced density of almost all graphs and their inducibility
• The inducibility of complete bipartite graphs

zbMATH Keywords

graph densityinducibilityRamsey multiplicity

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Generalized Ramsey theory (05C55)

Cites Work

• Large networks and graph limits
• Applications of the Semi-Definite Method to the Turán Density Problem for 3-Graphs
• Flag algebras
• The minimum number of monochromatic 4-term progressions in \(\mathbb Z_p\)
• The patterns of permutations
• On the page number of complete odd-partite graphs
• Title not available (Why is that?)
• Nowhere-zero 3-flows in triangularly connected graphs
• On Sets of Acquaintances and Strangers at any Party
• Title not available (Why is that?)
• On the densities of cliques and independent sets in graphs
• On the 3-local profiles of graphs
• Sur le problème de Goodman pour les quadrangles et la majoration des nombres de Ramsey
• On Erdős's conjecture on multiplicities of complete subgraphs: Lower upper bound for cliques of size 6
• Multiplicities of subgraphs
• A Disproof of a Conjecture of Erdős in Ramsey Theory
• On the Ramsey multiplicity of complete graphs
• 2-colorings of complete graphs with a small number of monochromatic \(K_ 4\) subgraphs
• The maximal number of induced complete bipartite graphs
• The inducibility of graphs
• Graph products and monochromatic multiplicities
• The maximal number of induced \(r\)-partite subgraphs
• Title not available (Why is that?)
• The inducibility of complete bipartite graphs
• The inducibility of blow-up graphs
• The inducibility of graphs on four vertices
• On the number of complete subgraphs contained in certain graphs
• On a conjecture of Erdős for multiplicities of cliques
• On the number of 4-cycles in a tournament
• On the local profiles of trees
• Title not available (Why is that?)
• Graphs with Few 3‐Cliques and 3‐Anticliques are 3‐Universal

Cited In (23)

• The feasible region of induced graphs
• On the exact maximum induced density of almost all graphs and their inducibility
• Further results on the inducibility of \(d\)-ary trees
• Maximising the number of induced cycles in a graph
• Sharp bounds for decomposing graphs into edges and triangles
• Decomposing graphs into edges and triangles
• C5 ${C}_{5}$ is almost a fractalizer
• Inducibility in binary trees and crossings in random tanglegrams
• On tripartite common graphs
• On the inducibility of oriented graphs on four vertices
• The maximum number of induced C5's in a planar graph
• Inducibility of \(d\)-ary trees
• On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices
• Planar graphs with the maximum number of induced 6-cycles
• Inducibility in the hypercube
• Inducibility of directed paths
• The inducibility of graphs on four vertices
• On the inducibility of cycles
• Stability from graph symmetrisation arguments with applications to inducibility
• Title not available (Why is that?)
• Inducibility and universality for trees
• Maximum density of vertex-induced perfect cycles and paths in the hypercube
• Compactness and finite forcibility of graphons

Uses Software

• Flagmatic

This page was built for publication: A note on the inducibility of 4-vertex graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q497330)