Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Poset limits can be totally ordered


Authors: Jan Hladký, András Máthé, Viresh Patel and Oleg Pikhurko
Journal: Trans. Amer. Math. Soc. 367 (2015), 4319-4337
MSC (2010): Primary 06A06, 28Axx
DOI: https://doi.org/10.1090/S0002-9947-2015-06299-0
Published electronically: February 3, 2015
MathSciNet review: 3324929
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Tim Austin, On exchangeable random variables and the statistics of large graphs and hypergraphs, Probab. Surv. 5 (2008), 80-145. MR 2426176 (2010g:60016), https://doi.org/10.1214/08-PS124
  • [2] Vladimir Bogachev, Measure theory. Vol. I, II, Springer-Verlag, Berlin, 2007. MR 2267655 (2008g:28002)
  • [3] 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 (2011d:05242), https://doi.org/10.1007/s00039-010-0044-0
  • [4] Christian Borgs, Jennifer Chayes, László Lovász, Vera T. Sós, and Katalin Vesztergombi, Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing, Adv. Math. 219 (2008), no. 6, 1801-1851. MR 2455626 (2009m:05161), https://doi.org/10.1016/j.aim.2008.07.008
  • [5] Graham Brightwell and Nicholas Georgiou, Continuum limits for classical sequential growth models, Random Structures Algorithms 36 (2010), no. 2, 218-250. MR 2583061 (2011f:60190), https://doi.org/10.1002/rsa.20278
  • [6] Persi Diaconis and Svante Janson, Graph limits and exchangeable random graphs, Rend. Mat. Appl. (7) 28 (2008), no. 1, 33-61. MR 2463439 (2010a:60127)
  • [7] Reinhard Diestel, Graph theory, 4th ed., Graduate Texts in Mathematics, vol. 173, Springer, Heidelberg, 2010. MR 2744811 (2011m:05002)
  • [8] 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, https://doi.org/10.1016/j.aim.2012.06.022
  • [9] 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, https://doi.org/10.1016/j.jctb.2012.09.003
  • [10] 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.
  • [11] Svante Janson, Poset limits and exchangeable random posets, Combinatorica 31 (2011), no. 5, 529-563. MR 2886098, https://doi.org/10.1007/s00493-011-2591-x
  • [12] Svante Janson, Limits of interval orders and semiorders, J. Comb. 3 (2012), no. 2, 163-183. MR 2980748, https://doi.org/10.4310/JOC.2012.v3.n2.a2
  • [13] 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 (2007m:05132), https://doi.org/10.1016/j.jctb.2006.05.002
  • [14] 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 (2008a:05129), https://doi.org/10.1007/s00039-007-0599-6
  • [15] Viresh Patel, Partitions of combinatorial structures, PhD Thesis, London School of Economics, 2009.
  • [16] 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 (2002e:06003), https://doi.org/10.1017/S0963548301004503
  • [17] Alexander A. Razborov, Flag algebras, J. Symbolic Logic 72 (2007), no. 4, 1239-1282. MR 2371204 (2008j:03040), https://doi.org/10.2178/jsl/1203350785
  • [18] 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 (92c:05142), https://doi.org/10.1002/rsa.3240020102
  • [19] Balázs Szegedy, Gowers norms, regularization and limits of functions on abelian groups, E-Print arxiv.org:1010.6211, 2010.
  • [20] 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 (81i:05095)
  • [21] 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 (2009e:60022), https://doi.org/10.1007/s11854-008-0001-0

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 06A06, 28Axx

Retrieve articles in all journals with MSC (2010): 06A06, 28Axx


Additional Information

Jan Hladký
Affiliation: Mathematics Institute, University of Warwick, Coventry, CV4 7AL, United Kingdom
Address at time of publication: Institute of Mathematics, Academy of Sciences of the Czech Republic, Žitná 25, 110 00, Praha, Czech Republic
Email: J.Hladky@warwick.ac.uk, honzahladky@gmail.com

András Máthé
Affiliation: Mathematics Institute, University of Warwick, Coventry, CV4 7AL, United Kingdom
Email: A.Mathe@warwick.ac.uk

Viresh Patel
Affiliation: School of Mathematics, Birmingham University, Edgbaston, Birmingham B15 2TT, United Kingdom
Address at time of publication: School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, United Kingdom
Email: viresh.s.patel@googlemail.com

Oleg Pikhurko
Affiliation: Mathematics Institute and DIMAP, University of Warwick, Coventry, CV4 7AL, United Kingdom

DOI: https://doi.org/10.1090/S0002-9947-2015-06299-0
Keywords: Homomorphism density, ordered probability space, partially ordered set, poset kernel, Regularity Lemma
Received by editor(s): November 11, 2012
Received by editor(s) in revised form: August 2, 2013
Published electronically: February 3, 2015
Additional Notes: The first author was supported by an EPSRC fellowship.
The second author was supported by the EPSRC (grant EP/G050678/1), the Hungarian Scientific Research Fund (grants 72655 and 104178) and the Leverhulme Trust.
The third author was supported by the EPSRC (grant EP/J008087/1).
The fourth author was supported by the European Research Council (grant agreement no. 306493) and the National Science Foundation of the USA (grant DMS-1100215).
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society