×

An analogue of the Erdős-Gallai theorem for random graphs. (English) Zbl 1458.05236

Summary: Recently, variants of many classical extremal theorems have been proved in the random environment. We, complementing existing results, extend the Erdős-Gallai Theorem in random graphs. In particular, we determine, up to a constant factor, the maximum number of edges in a \(P_n\)-free subgraph of \(G(N,p)\), practically for all values of \(N,n\) and \(p\). Our work is also motivated by the recent progress on the size-Ramsey number of paths.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C35 Extremal problems in graph theory
05C55 Generalized Ramsey theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ajtai, M.; Komlós, J.; Szemerédi, E., The longest path in a random graph, Combinatorica, 1, 1, 1-12 (1981) · Zbl 0489.05052
[2] Babai, L.; Simonovits, M.; Spencer, J., Extremal subgraphs of random graphs, J. Graph Theory, 14, 5, 599-622 (1990) · Zbl 0738.05048
[3] Bal, D.; DeBiasio, L., New lower bounds on the size-Ramsey number of a path (2019), arXiv preprint arXiv:1909.06354
[4] Balogh, J.; Morris, R.; Samotij, W., Independent sets in hypergraphs, J. Amer. Math. Soc., 28, 3, 669-709 (2015) · Zbl 1310.05154
[5] Beck, J., On size Ramsey number of paths, trees, and circuits. I, J. Graph Theory, 7, 1, 115-129 (1983) · Zbl 0508.05047
[6] Ben-Eliezer, I.; Krivelevich, M.; Sudakov, B., The size Ramsey number of a directed path, J. Combin. Theory Ser. B, 102, 3, 743-755 (2012) · Zbl 1245.05041
[7] Bohman, T.; Frieze, A.; Krivelevich, M.; Loh, P.-S.; Sudakov, B., Ramsey games with giants, Random Struct. Algorithms, 38, 1-2, 1-32 (2011) · Zbl 1215.05157
[8] B. Bollobás, The evolution of sparse graphs, in: Graph Theory and Combinatorics, Proceedings Cambridge Combinatorial Conference in Honour of Paul Erdős, 1984, pp. 335-357.
[9] Conlon, D.; Gowers, W. T., Combinatorial theorems in sparse random sets, Ann. of Math. (2), 184, 2, 367-454 (2016) · Zbl 1351.05204
[10] Dellamonica, D.; Kohayakawa, Y.; Marciniszyn, M.; Steger, A., On the resilience of long cycles in random graphs, Electron. J. Combin., 15, 1 (2008), Research Paper 32, 26 pages · Zbl 1181.05053
[11] Dudek, A.; Prałat, P., On some multicolor Ramsey properties of random graphs, SIAM J. Discrete Math., 31, 3, 2079-2092 (2017) · Zbl 1370.05211
[12] Dudek, A.; Prałat, P., Note on the multicolour size-Ramsey number for paths, Electron. J. Combin., 25, 3 (2018), Research Paper 3.35, 5 pages · Zbl 1395.05179
[13] Erdős, P.; Faudree, R. J.; Rousseau, C. C.; Schelp, R. H., The size Ramsey number, Period. Math. Hungar., 9, 1-2, 145-161 (1978) · Zbl 0331.05122
[14] Erdős, P.; Gallai, T., On maximal paths and circuits of graphs, Acta Math. Hungar., 10, 3-4, 337-356 (1959) · Zbl 0090.39401
[15] Frankl, P.; Rödl, V., Large triangle-free subgraphs in graphs without \(K_4\), Graphs Combin., 2, 1, 135-144 (1986) · Zbl 0596.05037
[16] Frieze, A. M., On large matchings and cycles in sparse random graphs, Discrete Math., 59, 3, 243-256 (1986) · Zbl 0628.05051
[17] Gyárfás, A., Partition coverings and blocking sets in hypergraphs, Commun. Comput. Autom. Inst. Hungar. Acad. Sci., 71, 62 (1977), (in Hungarian)
[18] Haxell, P. E.; Kohayakawa, Y.; Łuczak, T., Turán’s extremal problem in random graphs: Forbidding even cycles, J. Combin. Theory Ser. B, 64, 2, 273-287 (1995) · Zbl 0828.05056
[19] Haxell, P. E.; Kohayakawa, Y.; Łuczak, T., Turán’s extremal problem in random graphs: Forbidding odd cycles, Combinatorica, 16, 1, 107-122 (1996) · Zbl 0853.05072
[20] Johansson, A.; Kahn, J.; Vu, V., Factors in random graphs, Random Struct. Algorithms, 33, 1, 1-28 (2008) · Zbl 1146.05040
[21] Kohayakawa, Y.; Kreuter, B.; Steger, A., An extremal problem for random graphs and the number of graphs with large even-girth, Combinatorica, 18, 1, 101-120 (1998) · Zbl 0910.05059
[22] Kohayakawa, Y.; Łuczak, T.; Rödl, V., On \(K_4\)-free subgraphs of random graphs, Combinatorica, 17, 2, 173-213 (1997) · Zbl 0889.05068
[23] Kohayakawa, Y.; Rödl, V.; Schacht, M., The Turán theorem for random graphs, Combin. Probab. Comput., 13, 1, 61-91 (2004) · Zbl 1048.05075
[24] Komlós, J.; Szemerédi, E., Limit distribution for the existence of Hamiltonian cycles in a random graph, Discrete Math., 43, 1, 55-63 (1983) · Zbl 0521.05055
[25] Krivelevich, M., Expanders—how to find them, and what to find in them, (Surveys in Combinatorics 2019. Surveys in Combinatorics 2019, London Math. Soc. Lecture Note Ser., vol. 456 (2019), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 115-142 · Zbl 1476.05104
[26] Krivelevich, M., Long cycles in locally expanding graphs, with applications, Combinatorica, 39, 1, 135-151 (2019) · Zbl 1438.05142
[27] Krivelevich, M.; Kronenberg, G.; Mond, A., Turán-type problems for long cycles in random and pseudo-random graphs (2019), arXiv preprint arXiv:1911.08539
[28] Pikhurko, O., A note on the Turán function of even cycles, Proc. Amer. Math. Soc., 140, 11, 3687-3692 (2012) · Zbl 1270.05061
[29] Saxton, D.; Thomason, A., Hypergraph containers, Invent. Math., 201, 3, 925-992 (2015) · Zbl 1320.05085
[30] Schacht, M., Extremal results for random discrete structures, Ann. of Math., 333-365 (2016) · Zbl 1351.05207
[31] Spöhel, R.; Steger, A.; Thomas, H., Coloring the edges of a random graph without a monochromatic giant component, Electron. J. Combin., 17, 1 (2010), Research Paper 133, 7 pages · Zbl 1202.05130
[32] Szabó, T.; Vu, V. H., Turán’s theorem in sparse random graphs, Random Struct. Algorithms, 23, 3, 225-234 (2003) · Zbl 1028.05101
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.