Abstract
Let m(n) be the maximum integer such that every partially ordered set P with n elements contains two disjoint subsets A and B, each with cardinality m(n), such that either every element of A is greater than every element of B or every element of A is incomparable with every element of B. We prove that \(m(n)=\Theta\left(\frac{n}{\log n}\right)\). Moreover, for fixed ε ∈ (0,1) and n sufficiently large, we construct a partially ordered set P with n elements such that no element of P is comparable with \(n^{\varepsilon } \) other elements of P and for every two disjoint subsets A and B of P each with cardinality at least \(\frac{14n}{\epsilon\log_2 n}\), there is an element of A that is comparable with an element of B.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alon, N.: Eigenvalues and expanders. Theory of computing (Singer Island, Fla., 1984). Combinatorica 6(2), 83–96 (1986)
Alon, N.: Ramsey graphs cannot be defined by real polynomials. J. Graph Theory 14(6), 651–661 (1990)
Alon, N., Milman, V.D.: \(\lambda\sb 1,\) isoperimetric inequalities for graphs, and superconcentrators. J. Comb. Theory Ser. B 38(1), 73–88 (1985)
Alon, N., Pach, J., Pinchasi, R., Radoičić, R., Sharir, M.: Crossing patterns of semi-algebraic sets. J. Comb. Theory Ser A 111, 310-326 (2005)
Barak, B., Kindler, G., Shaltiel, R., Sudakov, B., Wigderson, A.: Simulating independence: new constructions of condensers, Ramsey graphs, dispersers and extractors. In: Proc. of the 37th ACM STOC, pp. 1–10 (2005)
Benczúr, A., András, A., Förster, J., Király, Z.: Dilworth’s theorem and its application for path systems of a cycle — implementation and analysis. Algorithms – ESA ’99 (Prague). Lecture Notes Computer Science, vol. 1643, pp. 498–509. Springer, Berlin Heidelberg New York (1999)
Berge, C.: Les problèmes de coloration en théorie des graphes. Publ. Inst. Stat. Univ. Paris 9, 123–160 (1960)
Chiu, P.: Cubic Ramanujan graphs. Combinatorica 12(3), 275–285 (1992)
Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51–229.
Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. Math. 51(2), 161–166 (1950)
Erdős, P., Hajnal, A., Pach, J.: Ramsey-type theorem for bipartite graphs. Geombinatorics 10, 64–68 (2000)
Erdős, P., Komlós, J.: On a problem of Moser. Combinatorial theory and its applications, I. (Proc. Colloq., Balatonfüred, 1969), pp. 365–367. North-Holland, Amsterdam (1970)
Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463–470 (1935)
Fox, J., Pach, J.: A bipartite analogue of Dilworth’s theorem for multiple partial orders, preprint.
Gessel, I., Rota, G-C (ed.): Classic Papers in Combinatorics. Birkhauser Boston, MA (1987)
Graham, R.L., Rothschild, B.L., Spencer, J.: Ramsey Theory, 2nd edn. John Wiley, New York (1990)
Greene, C., Kleitman, D.J.: The structure of Sperner k-families. J. Comb. Theory Ser. A. 20(1), 41–68 (1976)
Larman, D., Matoušek, J., Pach, J., Töröcsik, J.: A Ramsey-type result for convex sets. Bull. Lond. Math. Soc. 26(2), 132–136 (1994)
Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8(3), 261–277 (1988)
Matoušek, J., Welzl, E.: Good splitters for counting points in triangles. J. Algorithms 13(2), 307–319 (1992)
Morgenstern, M.: Existence and explicit constructions of q + 1 regular Ramanujan graphs for every prime power q. J. Comb. Theory Ser. B. 62(1), 44–62 (1994)
Murty, M.R.: Ramanujan graphs. J. Ramanujan Math. Soc. 18(1), 1–20 (2003)
Pach, J., Solymosi, J.: Crossing patterns of segments. J. Comb. Theory Ser. A. 96, 316–325 (2001)
Pach, J., Törőcsik, J.: Some geometric applications of Dilworth’s theorem. Discrete Comput. Geom. 12(1), 1–7 (1994)
Pach, J., Tóth, G.: Comments on Fox News. Geombinatorics 15, 150–154 (2006)
Pudlák, P., Rödl, V.: Pseudorandom sets and explicit constructions of Ramsey graphs. Complexity of computations and proofs. Quad. Mat. 13, 327–346, Dept. Math., Seconda Univ. Napoli, Caserta, Italy (2004)
Seinsche, D.: On a property of the class of n-colorable graphs. J. Comb. Theory Ser. B. 16, 191–193 (1974)
Tietze, H.: Über das Problem der Nachbargeibiete im Raum. Monatshefte Math. 16, 211–216 (1905)
Tóth, G., Valtr, P.: Geometric graphs with few disjoint edges. 14th Annual ACM Symposium on Computational Geometry, Minneapolis, MN, 1998. Discrete Comput. Geom. 22(4), 633–642 (1999)
Trotter, W.T.: Combinatorics and Partially Ordered Sets. Dimension Theory. Johns Hopkins Series in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD 1992
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fox, J. A Bipartite Analogue of Dilworth’s Theorem. Order 23, 197–209 (2006). https://doi.org/10.1007/s11083-006-9043-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-006-9043-z