New bounds on the Ramsey number \(r ( I_m , L_n )\). (English) Zbl 1456.05170
Summary: We investigate the Ramsey number \(r ( I_m , L_n )\) which is the smallest natural number \(k\) such that every oriented graph on \(k\) vertices contains either an independent set of size \(m\) or a transitive tournament on \(n\) vertices. Continuing research by J. A. Larson and W. J. Mitchell [Ann. Comb. 1, No. 3, 245–252 (1997; Zbl 0895.05043)] and earlier work by J. C. Bermond [Discrete Math. 9, 313–321 (1974; Zbl 0288.05111)] we establish two new upper bounds for \(r ( I_m , L_3 )\) which are paramount in proving \(r ( I_4 , L_3 ) = 15 < 23 = r ( I_5 , L_3 )\) and \(r ( I_m , L_3 ) = \Theta ( m^2 / \log m )\), respectively. We furthermore elaborate on implications of the latter on upper bounds for \(r ( I_m , L_n )\).
MSC:
| 05D10 | Ramsey theory |
| 05C55 | Generalized Ramsey theory |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
References:
| [1] | Ajtai, M.; Komlós, J.; Szemerédi, E., A note on Ramsey numbers, J. Combin. Theory Ser. A, 29, 3, 354-360 (1980) · Zbl 0455.05045 |
| [2] | Alon, N., Independence numbers of locally sparse graphs and a Ramsey type problem, Random Structures Algorithms, 9, 3, 271-278 (1996) · Zbl 0876.05049 |
| [3] | Baumgartner, J. E., Improvement of a partition theorem of Erdös and Rado, J. Combin. Theory Ser. A, 17, 134-137 (1974) · Zbl 0282.05003 |
| [4] | Bermond, J.-C., Some Ramsey numbers for directed graphs, Discrete Math., 9, 313-321 (1974) · Zbl 0288.05111 |
| [5] | Caro, Y., New Results on the Independence NumberTech. Report (1979), Tel-Aviv University |
| [6] | Erdős, P.; Rado, R., A partition calculus in set theory, Bull. Amer. Math. Soc., 62, 427-489 (1956), http://www.ams.org/journals/bull/1956-62-05/S0002-9904-1956-10036-0/S0002-9904-1956-10036-0.pdf · Zbl 0071.05105 |
| [7] | Erdős, P.; Moser, L., On the representation of directed graphs as unions of orderings, Magy. Tud. Akad. Mat. Kut. Int. Közl., 9, 125-132 (1964), http://www.renyi.hu/p̃_erdos/1964-22.pdf · Zbl 0136.44901 |
| [8] | Erdős, P.; Rado, R., Partition relations and transitivity domains of binary relations, J. Lond. Math. Soc., 42, 624-633 (1967) · Zbl 0204.00905 |
| [9] | Grinstead, C.; Roberts, S., On the Ramsey numbers R (3, 8) and R (3, 9), J. Combin. Theory Ser. B, 33, 27-51 (1982) · Zbl 0497.05043 |
| [10] | Hajnal, A.; Larson, J. A., Handbook of Set Theory, Vol. 1, xiv+736 (2010), Springer: Springer Dordrecht, chapter Partition relations, http://www.math.rutgers.edu/ |
| [11] | Kim, J. H., The Ramsey number \(R ( 3 , t )\) has order of magnitude \(t^2 / \log t\), Random Structures Algorithms, 7, 3, 173-207 (1995) · Zbl 0832.05084 |
| [12] | Larson, J. A.; Mitchell, W. J., On a problem of Erdős and Rado, Ann. Comb., 1, 3, 245-252 (1997) · Zbl 0895.05043 |
| [13] | Momihara, K.; Suda, S., Upper bounds on the size of transitive subtournaments in digraphs, Linear Algebra Appl., 530, 230-243 (2017) · Zbl 1367.05090 |
| [14] | Moon, J. W., On maximal transitive subtournaments, Proc. Edinb. Math. Soc. (2), 17, 345-349 (1970) · Zbl 0234.05108 |
| [15] | Nosal, E., On Arrow Relations w(k, w) 2(2) (m, n, k Less than w): A Study in the Partition Calculus (1975), ProQuest LLC: ProQuest LLC Ann Arbor, MI, http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:NK25043, Thesis (Ph.D.)-University of Calgary (Canada) |
| [16] | Nosal, E., Partition relations for denumerable ordinals, J. Combin. Theory Ser. B, 27, 2, 190-197 (1979) · Zbl 0432.05011 |
| [17] | Radziszowski, S. P., Small Ramsey numbers, Electron. J. Combin., 1, 30 (1994), Dynamic Survey 1, (electronic) http://www.combinatorics.org/Surveys/index.html |
| [18] | Reid, K. B.; Parker, E. T., Disproof of a conjecture of Erdős and Moser on tournaments, J. Comb. Theory, 9, 225-238 (1970) · Zbl 0204.24605 |
| [19] | Sánchez-Flores, A., On tournaments and their largest transitive subtournaments, Graphs Combin., 10, 4, 367-376 (1994) · Zbl 0811.05029 |
| [20] | Sánchez-Flores, A., On tournaments free of large transitive subtournaments, Graphs Combin., 14, 2, 181-200 (1998) · Zbl 0918.05058 |
| [21] | Stearns, R., The voting problem, Amer. Math. Monthly, 66, 761-763 (1959) · Zbl 0090.25101 |
| [22] | Wei, V. K., A Lower Bound on the Stability Number of a Simple Graph81-11217-9 (1981), Bell Laboratories Technical Memorandum: Bell Laboratories Technical Memorandum Murray Hill, NJ |
| [23] | Williams, N. H., Combinatorial Set Theory. Studies in Logic and the Foundations of Mathematics (1977), North-Holland Publishing Co.: North-Holland Publishing Co. Amsterdam · Zbl 0362.04008 |
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.
