Inducibility of directed paths

DOI10.1016/J.DISC.2020.112015MaRDI QIDQ785814zbMATH OpenOpenAlexFDO

Authors Ilkyoo Choi, Bernard Lidický, Florian Pfender

Publication date 12 August 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

induced subgraphdirected pathinducibility

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Abstract: A long standing open problem in extremal graph theory is to describe all graphs that maximize the number of induced copies of a path on four vertices. The character of the problem changes in the setting of oriented graphs, and becomes more tractable. Here we resolve this problem in the setting of oriented graphs without transitive triangles.

Recommendations

• On the inducibility of oriented graphs on four vertices
• A note on the inducibility of 4-vertex graphs
• The inducibility of graphs on four vertices
• On the Maximum Induced Density of Directed Stars and Related Problems
• scientific article; zbMATH DE number 3891406

Cites work

• A Solution to the 2/3 Conjecture
• A bound on the inducibility of cycles
• A new bound for the 2/3 conjecture
• A new lower bound based on Gromov's method of selecting heavily covered points
• A note on the inducibility of 4-vertex graphs
• A problem of Erdős on the minimum number of \(k\)-cliques
• Flag algebras
• Hypergraphs do jump
• Limits of order types
• 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
• Monochromatic triangles in three-coloured graphs
• On crossing numbers of complete tripartite and balanced complete multipartite graphs
• On the density of transitive tournaments
• On the exact maximum induced density of almost all graphs and their inducibility
• On the inducibility of cycles
• On the maximum number of five-cycles in a triangle-free graph
• On the number of pentagons in triangle-free graphs
• Pentagons in triangle-free graphs
• Quasirandom permutations are characterized by 4-point densities
• Rainbow triangles in three-colored graphs
• The codegree threshold for 3-graphs with independent neighborhoods
• The inducibility of graphs
• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube

Cited in

(10)

• Paths of length three are \(K_{r+1}\)-Turán-good
• On the inducibility of oriented graphs on four vertices
• Maximum density of vertex-induced perfect cycles and paths in the hypercube
• Maximizing five-cycles in \(K_r\)-free graphs
• A note on the inducibility of 4-vertex graphs
• Stability from graph symmetrisation arguments with applications to inducibility
• The inducibility of oriented stars
• Finite paths are universal
• C5 ${C}_{5}$ is almost a fractalizer
• scientific article; zbMATH DE number 5585075 (Why is no real title available?)

Describes a project that uses

Uses Software

• Flagmatic

This page was built for publication: Inducibility of directed paths

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