×
Bożyk, Łukasz; Grzesik, Andrzej; Kielak, Bartłomiej

On the inducibility of oriented graphs on four vertices. (English) Zbl 1489.05075

Discrete Math. 345, No. 7, Article ID 112874, 20 p. (2022).
Summary: 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.

Cited in 2 Documents

MSC:

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

Keywords:

oriented graph; inducibility; induced subgraph

Software:

SageMath; Flagmatic; CSDP
PDFBibTeX XMLCite
\textit{Ł. Bożyk} et al., Discrete Math. 345, No. 7, Article ID 112874, 20 p. (2022; Zbl 1489.05075)
Full Text: DOI arXiv

References:

[1] Baber, R., Some results in extremal combinatorics, 68-75 (2011), University College London, available at
[2] Balogh, J.; Hu, P.; Lidický, B.; Pfender, F., Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle, Eur. J. Comb., 52, 47-58 (2016) · Zbl 1327.05171
[3] Balogh, J.; Hu, P.; Lidický, B.; Pikhurko, O.; Udvari, B.; Volec, J., Minimum number of monotone subsequences of length 4 in permutations, Comb. Probab. Comput., 24, 658-679 (2015) · Zbl 1371.05137
[4] Borchers, B., CSDP, A C library for semidefinite programming, Optim. Methods Softw., 11, 613-623 (1999) · Zbl 0973.90524
[5] Bollobás, B.; Egawa, Y.; Harris, A.; Jin, G. P., The maximal number of induced r-partite subgraphs, Graphs Comb., 11, 1-19 (1995) · Zbl 0819.05034
[6] Bollobás, B.; Nara, C.; Tachibana, S.-i., The maximal number of induced complete bipartite graphs, Discrete Math., 62, 271-275 (1986) · Zbl 0613.05028
[7] Brown, J.; Sidorenko, A., The inducibility of complete bipartite graphs, J. Graph Theory, 18, 6, 629-645 (1994) · Zbl 0810.05037
[8] Burke, D.; Lidický, B.; Pfender, F.; Phillips, M., Inducibility of 4-vertex tournaments
[9] Choi, I.; Lidický, B.; Pfender, F., Inducibility of directed paths · Zbl 1445.05054
[10] Even-Zohar, C.; Linial, N., A note on the inducibility of 4-vertex graphs, Graphs Comb., 31, 5, 1367-1380 (2015) · Zbl 1321.05143
[11] Falgas-Ravry, V.; Vaughan, E. R., Applications of the semi-definite method to the Turán density problem for 3-graphs, Comb. Probab. Comput., 22, 1, 21-54 (2013) · Zbl 1257.05077
[12] J. Fox, H. Huang, C. Lee, A solution to the inducibility problem for almost all graphs, manuscript.
[13] Hatami, H.; Hirst, J.; Norine, S., The inducibility of blowup graphs, J. Comb. Theory, Ser. B, 109, 196-212 (2014) · Zbl 1301.05234
[14] Hefetz, D.; Tyomkin, M., On the inducibility of cycles, J. Comb. Theory, Ser. B, 133, 243-258 (2018) · Zbl 1397.05087
[15] Hirst, J., The inducibility of graphs on four vertices, J. Graph Theory, 75, 3, 231-243 (2014) · Zbl 1292.05161
[16] P. Hu, B. Lidický, F. Pfender, J. Volec, Inducibility of orientations of \(C_4\), manuscript.
[17] Hu, P.; Ma, J.; Norin, S.; Wu, H., Inducibility of oriented stars
[18] Huang, H., On the maximum induced density of directed stars and related problems, SIAM J. Discrete Math., 28, 1, 92-98 (2014) · Zbl 1292.05146
[19] Kráľ, D.; Norin, S.; Volec, J., A bound on the inducibility of cycles, J. Comb. Theory, Ser. A, 161, 359-363 (2019) · Zbl 1400.05074
[20] Nakata, M., A numerical evaluation of highly accurate multiple-precision arithmetic version of semidefinite programming solver: SDPA-GMP, -QD and -DD, (Proc. IEEE Multi-Conference on Systems and Control (2010)), 29-34, available at
[21] Pippenger, N.; Golumbic, M. C., The inducibility of graphs, J. Comb. Theory, Ser. B, 19, 3, 189-203 (1975) · Zbl 0332.05119
[22] Razborov, A., Flag algebras, J. Symb. Log., 72, 1239-1282 (2007) · Zbl 1146.03013
[23] SageMath, the Sage Mathematics Software System, available at
[24] Vaughan, E. R., Flagmatic: a tool for researchers in extremal graph theory, further developed by J. Sliacan, available at
[25] Yuster, R., On the exact maximum induced density of almost all graphs and their inducibility, J. Comb. Theory, Ser. B, 136, 81-109 (2019) · Zbl 1414.05173
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.