Inducibility of directed paths

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.

arXiv comment17 pages, 4 figures

References in corpus (13)

• On the Number of Pentagons in Triangle-Free Graphs
• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
• Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
• A Note on the Inducibility of 4-vertex Graphs
• Minimum number of monotone subsequences of length 4 in permutations
• Rainbow triangles in three-colored graphs
• A new lower bound based on Gromov's method of selecting heavily covered points
• Counting flags in triangle-free digraphs
• A bound on the inducibility of cycles
• Crossing numbers of complete tripartite and balanced complete multipartite graphs
• Pentagons in triangle-free graphs
• Limits, Regularity and Removal for Finite Structures
• Semidefinite Programming and Ramsey Numbers

Cited by in corpus (7)

• Maximizing five-cycles in $K_r$-free graphs
• Stability from graph symmetrisation arguments with applications to inducibility
• $C_5$ is almost a fractalizer
• The inducibility of oriented stars
• Inducibility of 4-vertex tournaments
• Inducibility of the Net Graph
• Paths of Length Three are $K_{r+1}$-Turán Good