Monochromatic paths in random tournaments. (English) Zbl 1405.05158
Summary: We prove that, with high probability, any 2-edge-coloring of a random tournament on \(n\) vertices contains a monochromatic path of length \(\Omega(n/\sqrt{\log n})\). This resolves a conjecture of I. Ben-Eliezer et al. [J. Comb. Theory, Ser. B 102, No. 3, 743–755 (2012; Zbl 1245.05041)] and implies a nearly tight upper bound on the oriented size Ramsey number of a directed path.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C55 | Generalized Ramsey theory |
| 05C15 | Coloring of graphs and hypergraphs |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05D10 | Ramsey theory |
Keywords:
monochromatic directed path; monochromatic oriented path; Ramsey theory; size Ramsey numberCitations:
Zbl 1245.05041References:
| [1] | N. Alon and J. H. Spencer, The probabilistic method, 4th ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016. · Zbl 1333.05001 |
| [2] | J. Beck, On size Ramsey number of paths, trees, and circuits. I, J. Graph Theory7 (1983), no. 1, 115-129. · Zbl 0508.05047 |
| [3] | I. Ben‐Eliezer, M. Krivelevich, and B. Sudakov, Long cycles in subgraphs of (pseudo)random directed graphs, J. Graph Theory70 (2012), no. 3, 284-296. · Zbl 1244.05195 |
| [4] | I. Ben‐Eliezer, M. Krivelevich, and B. Sudakov, The size Ramsey number of a directed path, J. Combin. Theory Ser. B102 (2012), no. 3, 743-755. · Zbl 1245.05041 |
| [5] | M. Bucić, S. Letzter, and B. Sudakov, Directed Ramsey number for trees, ArXiv e‐prints, http://arxiv.org/abs/1708.04504 (to appear). · Zbl 1378.05123 |
| [6] | M. Bucić, S. Heberle, S. Letzter, and B. Sudakov, Monochromatic trees in random tournaments, (to appear). · Zbl 1466.05033 |
| [7] | P. Erdős et al. The size Ramsey number, Period. Math. Hungar.9 (1978), no. 1-2, 145-161. · Zbl 0331.05122 |
| [8] | T. Gallai, On directed paths and circuits, Theory of Graphs, Proc. Colloq., Tihany, 1966, Hungary, (1968), pp. 115-118. · Zbl 0159.54403 |
| [9] | A. Gyárfás, Vertex coverings by monochromatic paths and cycles, J. Graph Theory7 (1983), no. 1, 131-135. · Zbl 0511.05046 |
| [10] | M. Hasse, Zur algebraischen Begründung der Graphentheorie. I, Math. Nachr.28 (1965), 275-290. · Zbl 0214.51003 |
| [11] | S. Letzter and B. Sudakov, The oriented size Ramsey number of directed paths, ArXiv e‐prints, https://arxiv.org/abs/1712.02403 (to appear). · Zbl 1442.05129 |
| [12] | F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. S2-30 (1929), no. 1, 264. · JFM 55.0032.04 |
| [13] | H. Raynaud, Sur le circuit hamiltonien bi‐coloré dans les graphes orientés, Period. Math. Hungar.3 (1973), 289-297. · Zbl 0267.05114 |
| [14] | D. Reimer, The Ramsey size number of dipaths, Discrete Math.257 (2002), no. 1, 173-175. · Zbl 1012.05116 |
| [15] | B. Roy, Nombre chromatique et plus longs chemins d’un graphe, Rev. Française Informat. Recherche Opérationnelle1 (1967), no. 5, 129-132. · Zbl 0157.31302 |
| [16] | L. M. Vitaver, Determination of minimal coloring of vertices of a graph by means of Boolean powers of the incidence matrix, Dokl. Akad. Nauk SSSR147 (1962), 758-759. · Zbl 0126.39302 |
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.
