On the inducibility of oriented graphs on four vertices

DOI10.1016/J.DISC.2022.112874MaRDI QIDQ2138968zbMATH OpenOpenAlexFDO

Authors Łukasz Bożyk, A. Grzesik, Bartłomiej Kielak

Publication date 17 May 2022

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

induced subgraphinducibilityoriented graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Semidefinite programming (90C22)

Abstract: We consider the problem of determining the inducibility (maximum possible asymptotic density of induced copies) of oriented graphs on four vertices. We provide exact values for more than half of the graphs, and very close lower and upper bounds for all the remaining ones. It occurs that, for some graphs, the structure of extremal constructions maximizing density of its induced copies is very sophisticated and complex.

Recommendations

• Inducibility of directed paths
• The inducibility of graphs on four vertices
• A note on the inducibility of 4-vertex graphs
• The inducibility of complete bipartite graphs
• On the exact maximum induced density of almost all graphs and their inducibility

Cites work

• A bound on the inducibility of cycles
• A note on the inducibility of 4-vertex graphs
• Applications of the Semi-Definite Method to the Turán Density Problem for 3-Graphs
• CSDP, A C library for semidefinite programming
• Flag algebras
• Inducibility of directed paths
• Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
• Minimum Number of Monotone Subsequences of Length 4 in Permutations
• On the exact maximum induced density of almost all graphs and their inducibility
• On the inducibility of cycles
• On the Maximum Induced Density of Directed Stars and Related Problems
• The inducibility of blow-up graphs
• The inducibility of complete bipartite graphs
• The inducibility of graphs
• The inducibility of graphs on four vertices
• The maximal number of induced \(r\)-partite subgraphs
• The maximal number of induced complete bipartite graphs

Cited in

(8)

• A note on the inducibility of 4-vertex graphs
• The inducibility of graphs on four vertices
• C5 ${C}_{5}$ is almost a fractalizer
• Stability from graph symmetrisation arguments with applications to inducibility
• The inducibility of oriented stars
• Inducibility of the net graph
• Inducibility of four-vertex tournaments
• Inducibility of directed paths

Describes a project that uses

Uses Software

• Flagmatic
• CSDP
• SageMath

This page was built for publication: On the inducibility of oriented graphs on four vertices

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