×

Ramsey numbers for partially-ordered sets. (English) Zbl 1417.05238

Authors’ abstract: We present a refinement of Ramsey numbers by considering graphs with a partial ordering on their vertices. This is a natural extension of the ordered Ramsey numbers. We formalize situations in which we can use arbitrary families of partially-ordered sets to form host graphs for Ramsey problems. We explore connections to well studied Turán-type problems in partially-ordered sets, particularly those in the Boolean lattice. We find a strong difference between Ramsey numbers on the Boolean lattice and ordered Ramsey numbers when the partial ordering on the graphs have large antichains.

MSC:

05D10 Ramsey theory
05C55 Generalized Ramsey theory
06A07 Combinatorics of partially ordered sets

Software:

z3; SageMath
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N.; Frankl, P.; Lovász, L., The chromatic number of Kneser hypergraphs, Trans. Am. Math. Soc., 298, 359-370, (1986) · Zbl 0605.05033
[2] Axenovich, M.; Walzer, S., Boolean lattices: Ramsey properties and embeddings, Order, 34, 287-298, (2017) · Zbl 1375.05262
[3] Balko, M.; Cibulka, J.; Král, K.; Kynčl, J., Ramsey numbers of ordered graphs, Electron Notes Discrete Math., 49, 419-424, (2015) · Zbl 1346.05179
[4] Beineke, L.W., Schwenk, A.J.: On a bipartite form of the Ramsey problem. In: Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), pp. 17-22 (1975)
[5] Choudum, S.; Ponnusamy, B., Ordered Ramsey numbers, Discret. Math., 247, 79-92, (2002) · Zbl 0998.05046
[6] Cibulka, J.; Gao, P.; Krčál, M.; Valla, T.; Valtr, P., On the geometric Ramsey number of outerplanar graphs, Discrete Comput. Geom., 53, 64-79, (2014) · Zbl 1309.05124
[7] Conlon, D., A new upper bound for the bipartite Ramsey problem, J. Graph Theory, 58, 351-356, (2008) · Zbl 1171.05368
[8] Conlon, D.; Fox, J.; Lee, C.; Sudakov, B., Ordered Ramsey numbers, J. Comb. Theory, Series B, 122, 353-383, (2017) · Zbl 1350.05085
[9] Cox, C.; Stolee, D., Ordered Ramsey numbers of loose paths and matchings, Discret. Math., 339, 499-505, (2016) · Zbl 1327.05225
[10] De Bonis, A.; Katona, GO, Largest families without an r-fork, Order, 24, 181-191, (2007) · Zbl 1127.05101
[11] De Bonis, A.; Katona, GO; Swanepoel, KJ, Largest family without a ∪ b ⊆ c ∩ d, J. Comb. Theory, Series A, 111, 331-336, (2005) · Zbl 1070.05077
[12] De Moura, L., Bjørner, N.: Z3: an efficient smt solver. In: Tools and Algorithms for the Construction and Analysis of Systems, pp. 337-340. Springer (2008)
[13] Duffus, D.; Kierstead, HA; Trotter, WT, Fibres and ordered set coloring, J. Comb. Theory, Series A, 58, 158-164, (1991) · Zbl 0757.06001
[14] Erdős, P.; Szekeres, G., A combinatorial problem in geometry, Compos. Math., 2, 463-470, (1935) · Zbl 0012.27010
[15] Fox, J.; Pach, J.; Sudakov, B.; Suk, A., Erdős-szekeres-type theorems for monotone paths and convex bodies, Proc. Lond. Math. Soc., 105, 953-982, (2012) · Zbl 1254.05114
[16] Füredi, Z., An upper bound on Zarankiewicz’ problem, Comb. Probab. Comput., 5, 29-33, (1996) · Zbl 0857.05048
[17] Goddard, W.; Henning, MA; Oellermann, OR, Bipartite Ramsey numbers and Zarankiewicz numbers, Discret. Math., 219, 85-95, (2000) · Zbl 0953.05051
[18] Griggs, J.; Li, W-T; Lu, L., Diamond-free families, J. Comb. Theory (Ser. A), 119, 310-322, (2012) · Zbl 1235.05144
[19] Griggs, JR; Li, W-T, The partition method for poset-free families, J. Comb. Optim., 25, 587-596, (2013) · Zbl 1273.90172
[20] Griggs, JR; Li, W-T, Poset-free families and lubell-boundedness, J. Comb. Theory, Series A, 134, 166-187, (2015) · Zbl 1315.05138
[21] Griggs, JR; Lu, L., On families of subsets with a forbidden subposet, Comb. Probab. Comput., 18, 731-748, (2009) · Zbl 1215.05082
[22] Grósz, D.; Methuku, A.; Tompkins, C., An improvement of the general bound on the largest family of subsets avoiding a subposet, Order, 34, 113-125, (2017) · Zbl 1404.06003
[23] Gunderson, DS; Rödl, V.; Sidorenko, A., Extremal problems for sets forming boolean algebras and complete partite hypergraphs, J. Comb. Theory, Series A, 88, 342-367, (1999) · Zbl 0939.05079
[24] Hattingh, J.; Henning, M., Bipartite Ramsey theory, Utilitas Mathematica, 53, 217-230, (1998) · Zbl 0908.05064
[25] Irving, RW, A bipartite Ramsey problem and the Zarankiewicz numbers, Glasg. Math. J., 19, 13-26, (1978) · Zbl 0367.05051
[26] Johnston, T., Lu, L., Milans, K.G.: Boolean algebras and lubell functions. J. Comb. Theory Series A, July. to appear · Zbl 1319.05131
[27] Kierstead, HA; Trotter, WT, A ramsey theoretic problem for finite ordered sets, Discret. Math., 63, 217-223, (1987) · Zbl 0613.06001
[28] Kramer, L.; Martin, R.; Young, M., On diamond-free subposets of the Boolean lattice, J. Comb. Theory Ser. A, 120, 545-560, (2013) · Zbl 1345.05112
[29] McColm, GL, A ramseyian theorem on products of trees, J. Comb. Theory, Series A, 57, 68-75, (1991) · Zbl 0753.05078
[30] Milans, K.; Stolee, D.; West, D., Ordered Ramsey theory and track representations of graphs, J. Comb., 6, 445-456, (2015) · Zbl 1325.05111
[31] Moshkovitz, G.; Shapira, A., Ramsey theory, integer partitions and a new proof of the ERDős-Szekeres theorem, Adv. Math., 262, 1107-1129, (2014) · Zbl 1295.05255
[32] Nešetřil, J.; Rödl, V., Combinatorial partitions of finite posets and lattices—Ramsey lattices, Algebra Universalis, 19, 106-119, (1984) · Zbl 0546.06002
[33] Sperner, E., Ein Satz über Untermengen einer endlichen Menge, Math. Z., 27, 544-548, (1928) · JFM 54.0090.06
[34] Stein, W. et al.: Sage: open source mathematical software. 7 December 2009 (2008)
[35] Trotter, W.: Ramsey theory and partially ordered sets. In: Graham, R.L. et al. (eds.) Contemporary Trends in Discrete Mathmatics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 49, pp. 337-347 (1999) · Zbl 0930.06006
[36] West, D.: Introduction to Graph Theory. Prentice Hall, Inc., Upper Saddle River (1996) · Zbl 0845.05001
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.