Poset limits can be totally ordered

Hladký, Jan; Máthé, András; Patel, Viresh; Pikhurko, Oleg

doi:10.1090/S0002-9947-2015-06299-0

Poset limits can be totally ordered
HTML articles powered by AMS MathViewer

by Jan Hladký, András Máthé, Viresh Patel and Oleg Pikhurko PDF

Trans. Amer. Math. Soc. 367 (2015), 4319-4337 Request permission

Abstract:

S. Janson [Poset limits and exchangeable random posets, Combinatorica 31 (2011), 529–563] defined limits of finite posets in parallel to the emerging theory of limits of dense graphs.

We prove that each poset limit can be represented as a kernel on the unit interval with the standard order, thus answering an open question of Janson. We provide two proofs: real-analytic and combinatorial. The combinatorial proof is based on a Szemerédi-type Regularity Lemma for posets which may be of independent interest.

Also, as a by-product of the analytic proof, we show that every atomless ordered probability space admits a measure-preserving and almost order-preserving map to the unit interval.

References

Tim Austin, On exchangeable random variables and the statistics of large graphs and hypergraphs, Probab. Surv. 5 (2008), 80–145. MR 2426176, DOI 10.1214/08-PS124
V. I. Bogachev, Measure theory. Vol. I, II, Springer-Verlag, Berlin, 2007. MR 2267655, DOI 10.1007/978-3-540-34514-5
Christian Borgs, Jennifer Chayes, and László Lovász, Moments of two-variable functions and the uniqueness of graph limits, Geom. Funct. Anal. 19 (2010), no. 6, 1597–1619. MR 2594615, DOI 10.1007/s00039-010-0044-0
C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi, Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing, Adv. Math. 219 (2008), no. 6, 1801–1851. MR 2455626, DOI 10.1016/j.aim.2008.07.008
Graham Brightwell and Nicholas Georgiou, Continuum limits for classical sequential growth models, Random Structures Algorithms 36 (2010), no. 2, 218–250. MR 2583061, DOI 10.1002/rsa.20278
Persi Diaconis and Svante Janson, Graph limits and exchangeable random graphs, Rend. Mat. Appl. (7) 28 (2008), no. 1, 33–61. MR 2463439
Reinhard Diestel, Graph theory, 4th ed., Graduate Texts in Mathematics, vol. 173, Springer, Heidelberg, 2010. MR 2744811, DOI 10.1007/978-3-642-14279-6
Gábor Elek and Balázs Szegedy, A measure-theoretic approach to the theory of dense hypergraphs, Adv. Math. 231 (2012), no. 3-4, 1731–1772. MR 2964622, DOI 10.1016/j.aim.2012.06.022
Carlos Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo Moreira, Balázs Ráth, and Rudini Menezes Sampaio, Limits of permutation sequences, J. Combin. Theory Ser. B 103 (2013), no. 1, 93–113. MR 2995721, DOI 10.1016/j.jctb.2012.09.003
Carlos Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo Moreira, and Rudini Menezes Sampaio, Limits of permutation sequences through permutation regularity, E-Print arXiv.org:1106.1663, 2011.
Svante Janson, Poset limits and exchangeable random posets, Combinatorica 31 (2011), no. 5, 529–563. MR 2886098, DOI 10.1007/s00493-011-2591-x
Svante Janson, Limits of interval orders and semiorders, J. Comb. 3 (2012), no. 2, 163–183. MR 2980748, DOI 10.4310/JOC.2012.v3.n2.a2
László Lovász and Balázs Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B 96 (2006), no. 6, 933–957. MR 2274085, DOI 10.1016/j.jctb.2006.05.002
László Lovász and Balázs Szegedy, Szemerédi’s lemma for the analyst, Geom. Funct. Anal. 17 (2007), no. 1, 252–270. MR 2306658, DOI 10.1007/s00039-007-0599-6
Viresh Patel, Partitions of combinatorial structures, PhD Thesis, London School of Economics, 2009.
Hans Jürgen Prömel, Angelika Steger, and Anusch Taraz, Counting partial orders with a fixed number of comparable pairs, Combin. Probab. Comput. 10 (2001), no. 2, 159–177. MR 1833068, DOI 10.1017/S0963548301004503
Alexander A. Razborov, Flag algebras, J. Symbolic Logic 72 (2007), no. 4, 1239–1282. MR 2371204, DOI 10.2178/jsl/1203350785
Miklós Simonovits and Vera T. Sós, Szemerédi’s partition and quasirandomness, Random Structures Algorithms 2 (1991), no. 1, 1–10. MR 1099576, DOI 10.1002/rsa.3240020102
Balázs Szegedy, Gowers norms, regularization and limits of functions on abelian groups, E-Print arxiv.org:1010.6211, 2010.
Endre Szemerédi, Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, pp. 399–401 (English, with French summary). MR 540024
Terence Tao, A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal lemma, J. Anal. Math. 103 (2007), 1–45. MR 2373263, DOI 10.1007/s11854-008-0001-0