Geodesic
Extremal, enumerative and probabilistic results on ordered hypergraph matchings
Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e55

Voir la notice de l'article provenant de la source Cambridge University Press

An ordered r-matching is an r-uniform hypergraph matching equipped with an ordering on its vertices. These objects can be viewed as natural generalisations of r-dimensional orders. The theory of ordered 2-matchings is well developed and has connections and applications to extremal and enumerative combinatorics, probability and geometry. On the other hand, in the case $r \ge 3$ much less is known, largely due to a lack of powerful bijective tools. Recently, Dudek, Grytczuk and Ruciński made some first steps towards a general theory of ordered r-matchings, and in this paper we substantially improve several of their results and introduce some new directions of study. Many intriguing open questions remain. 
Anastos, Michael; Jin, Zhihan; Kwan, Matthew; Sudakov, Benny. Extremal, enumerative and probabilistic results on ordered hypergraph matchings. Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e55. doi: 10.1017/fms.2024.144
@article{10_1017_fms_2024_144,
     author = {Anastos, Michael and Jin, Zhihan and Kwan, Matthew and Sudakov, Benny},
     title = {Extremal, enumerative and probabilistic results on ordered hypergraph matchings},
     journal = {Forum of Mathematics, Sigma},
     pages = {e55},
     year = {2025},
     volume = {13},
     number = {1},
     doi = {10.1017/fms.2024.144},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2024.144/}
}
TY  - JOUR
AU  - Anastos, Michael
AU  - Jin, Zhihan
AU  - Kwan, Matthew
AU  - Sudakov, Benny
TI  - Extremal, enumerative and probabilistic results on ordered hypergraph matchings
JO  - Forum of Mathematics, Sigma
PY  - 2025
SP  - e55
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2024.144/
DO  - 10.1017/fms.2024.144
ID  - 10_1017_fms_2024_144
ER  - 
%0 Journal Article
%A Anastos, Michael
%A Jin, Zhihan
%A Kwan, Matthew
%A Sudakov, Benny
%T Extremal, enumerative and probabilistic results on ordered hypergraph matchings
%J Forum of Mathematics, Sigma
%D 2025
%P e55
%V 13
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2024.144/
%R 10.1017/fms.2024.144
%F 10_1017_fms_2024_144

[1] Aldous, D. and Diaconis, P., ‘Hammersley’s interacting particle process and longest increasing subsequences’, Probab. Theory Related Fields. 103(2) (1995), 199–213. Google Scholar | DOI

[2] Alon, N. and Friedgut, E., ‘On the number of permutations avoiding a given pattern’, J. Combin. Theory Ser. A. 89(1) (2000), 133–140. Google Scholar | DOI

[3] Aronov, B., Dujmović, C., Morin, P., Ooms, A. and Da Silveira, L. F. Schultz Xavier, ‘More Turán-type theorems for triangles in convex point sets’, Electron. J. Combin. 26(1) (2019), Paper No. 1.8, 26. Google Scholar | DOI

[4] Baik, J., Deift, P. and Johansson, K., ‘On the distribution of the length of the longest increasing subsequence of random permutations’, J. Amer. Math. Soc. 12(4) (1999), 1119–1178. Google Scholar | DOI

[5] Baik, J. and Jenkins, R., ‘Limiting distribution of maximal crossing and nesting of Poissonized random matchings’, Ann. Probab. 41(6) (2013), 4359–4406. Google Scholar | DOI

[6] Baik, J. and Rains, E. M., ‘The asymptotics of monotone subsequences of involutions’, Duke Math. J. 109(2) (2001), 205–281. Google Scholar | DOI

[7] Bollobás, B. and Winkler, P., ‘The longest chain among random points in Euclidean space’, Proc. Amer. Math. Soc. 103(2) (1988), 347–353. Google Scholar | DOI

[8] Braß, P., Rote, G. and Swanepoel, K. J., ‘Triangles of extremal area or perimeter in a finite planar point set’, Discrete Comput. Geom. 26(1) (2001), 51–58. Google Scholar | DOI

[9] Braß, P., ‘Turán-type extremal problems for convex geometric hypergraphs’, in Towards a Theory of Geometric Graphs, (Contemp. Math., Vol. 342). (Amer. Math. Soc., Providence, RI, 2004), 25–33. Google Scholar | DOI

[10] Braß, P., Károlyi, G. and Valtr, P., ‘A Turán-type extremal theory of convex geometric graphs’, in Discrete and Computational Geometry (Algorithms Combin., Vol. 25) (Springer, Berlin, 2003), 275–300. Google Scholar | DOI

[11] Brightwell, G., ‘Random -dimensional orders: width and number of linear extensions’, Order. 9(4) (1992), 333–342. Google Scholar | DOI

[12] Brightwell, G., ‘Models of random partial orders’, in Surveys in Combinatorics, 1993 (Keele), (London Math. Soc. Lecture Note Ser., Vol. 187) (Cambridge Univ. Press, Cambridge, 1993), 53–83. Google Scholar

[13] Bucić, M., Sudakov, B. and Tran, T., ‘Erdős-Szekeres theorem for multidimensional arrays’, J. Eur. Math. Soc. (JEMS). 25 (2023), 2927–2947. Google Scholar | DOI

[14] Bukh, B. and Matoušek, J., ‘Erdős–Szekeres-type statements: Ramsey function and decidability in dimension ’, Duke Math. J. 163(12) (2014), 2243–2270. Google Scholar | DOI

[15] Burkill, H. and Mirsky, L., ‘Monotonicity’, J. Math. Anal. Appl. 41 (1973), 391–410. Google Scholar | DOI

[16] Capoyleas, V. and Pach, J., ‘A Turán-type theorem on chords of a convex polygon’, J. Combin. Theory Ser. B. 56(1) (1992), 9–15. Google Scholar | DOI

[17] Chen, W. Y. C., Deng, E. Y. P., Du, R. R. X., Stanley, R. P. and Yan, C. H., ‘Crossings and nestings of matchings and partitions’, Trans Amer. Math. Soc. 359(4) (2007), 1555–1575. Google Scholar | DOI

[18] Cibulka, J., and Kynčl, J., ‘Better upper bounds on the Füredi-Hajnal limits of permutations’, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM, Philadelphia, PA, 2017), 2280–2293. Google Scholar

[19] G. De B. Robinson, ‘On the representations of the symmetric group’, Amer. J. Math. 60(3) (1938), 745–760. Google Scholar | DOI

[20] De Mier, A., ‘-noncrossing and -nonnesting graphs and fillings of Ferrers diagrams’, Combinatorica. 27(6) (2007), 699–720. Google Scholar | DOI

[21] Dudek, A., Grytczuk, J. and Ruciński, A., ‘Ordered unavoidable sub-structures in matchings and random matchings’, Electron. J. Combin. 31(2) (2024), Paper No. 2.15, 27. Google Scholar | DOI

[22] Dudek, A., Grytczuk, J. and Ruciński, A., ‘Erdős–Szekeres type theorems for ordered uniform matchings’, J. Combin. Theory Ser. B. 170(2025), 225–259. Google Scholar | DOI

[23] Dudek, A., Grytczuk, J. and Ruciński, A., On Weak Twins and Up-and-Down Subpermutations (De Gruyter, April 2022), 187–202. Google Scholar

[24] Dujmović, V. and Wood, D. R., ‘On linear layouts of graphs’, Discrete Math Theor. Comput. Sci. 6(2) (2004), 339–357. Google Scholar

[25] Erdős, P. and Kleitman, D. J., ‘On coloring graphs to maximize the proportion of multicolored -edges’, J. Comb. Theory. 5 (1968), 164–169. Google Scholar | DOI

[26] Erdős, P. and Szekeres, G., ‘A combinatorial problem in geometry’, Compos. Math. 2 (1935), 463–470. Google Scholar

[27] Errera, A., ‘Analysis situs: un problème d’énumération, Mémoires de la Classe des sciences. Académie royale de Belgique’, Collection 8. 11(6) (1931), 3–26. Google Scholar

[28] Fox, J., ‘Stanley–Wilf limits are typically exponential’, 2013, arXiv preprint . Google Scholar | arXiv

[29] Fox, J., Pach, J., Sudakov, B. and Suk, A., ‘Erdős–Szekeres-type theorems for monotone paths and convex bodies’, Proc. Lond. Math. Soc (3). 105(5) (2012), 953–982. Google Scholar | DOI

[30] Füredi, Z., Jiang, T., Kostochka, A., Mubayi, D. and Verstraëte, J., ‘Tight paths in convex geometric hypergraphs’, Adv. Comb. 2020;Paper No. 1, 14. Google Scholar

[31] Füredi, Z., Jiang, T., Kostochka, A., Mubayi, D. and Verstraëte, J., ‘Extremal problems for convex geometric hypergraphs and ordered hypergraphs’, Can. J. Math. 73(6) (2021), 1648–1666. Google Scholar | DOI

[32] Füredi, Z., Jiang, T., Kostochka, A., Mubayi, D. and Verstraëte, J., ‘Partitioning ordered hypergraphs’, J. Combin. Theory Ser. A. 177 (2021), Paper No. 105300, 18. Google Scholar | DOI

[33] Füredi, Z., Mubayi, D., O’Neill, J., and Verstraëte, J., ‘Extremal problems for pairs of triangles’, J. Combin. Theory Ser. B. 155 (2022), 83–110. Google Scholar | DOI

[34] Girão, A., Kronenberg, G., and Scott, A., ‘A multidimensional Ramsey theorem’, arXiv preprint . Google Scholar | arXiv

[35] Gowers, W. T. and Long, J., ‘The length of an -increasing sequence of -tuples’, Combin. Probab. Comput. 30(5) (2021), 686–721. Google Scholar | DOI

[36] Groeneboom, P., ‘Ulam’s problem and Hammersley’s process’, Ann. Probab. 29(2) (2001), 683–690. Google Scholar | DOI

[37] Huynh, T., Joos, F. and Wollan, P., ‘A unified Erdős–Pósa theorem for constrained cycles’, Combinatorica. 39(1) (2019), 91–133. Google Scholar | DOI

[38] Janson, S., Łuczak, T. and Rucinski, A., Random Graphs (Wiley-Interscience Series in Discrete Mathematics and Optimization) (Wiley-Interscience, New York, 2000).. Google Scholar | DOI

[39] Johansson, K., ‘The longest increasing subsequence in a random permutation and a unitary random matrix model’, Math. Res. Lett. 5(1–2) (1998), 63–82. Google Scholar | DOI

[40] Jonsson, J., and Welker, V., ‘A spherical initial ideal for Pfaffians’, Illinois J. Math. 51(4) (2007), 1397–1407. Google Scholar | DOI

[41] Justicz, J., Scheinerman, E. R. and Winkler, P., ‘Random intervals’, Amer. Math. Monthly. 97(10) (1990), 881–889. Google Scholar | DOI

[42] Kalmanson, K., ‘On a theorem of Erdős and Szekeres’, J. Comb. Theory Ser. A. 15 (1973), 343–346. Google Scholar | DOI

[43] Kasraoui, A. and Zeng, J., ‘Distribution of crossings, nestings and alignments of two edges in matchings and partitions’, Electron. J. Combin. 13(1) (2006), Research Paper 33, 12. Google Scholar | DOI

[44] Klazar, M., ‘The Füredi–Hajnal conjecture implies the Stanley–Wilf conjecture’, in Formal Power Series and Algebraic Combinatorics (Moscow, 2000) (Springer, Berlin, 2000), 250–255. Google Scholar | DOI

[45] Klazar, M., ‘On identities concerning the numbers of crossings and nestings of two edges in matchings’, S. IAM J. Discrete Math. 20(4) (2006), 960–976. Google Scholar | DOI

[46] Knuth, D. E., ‘Permutations, matrices, and generalized Young tableaux’, Pacific J. Math. 34 (1970), 709–727. Google Scholar | DOI

[47] Krattenthaler, C., ‘Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes’, Adv. Appl. Math. 37(3) (2006), 404–431. Google Scholar | DOI

[48] Linial, N. and Simkin, M., ‘Monotone subsequences in high-dimensional permutations’, Combin. Probab. Comput. 27(1) (2018), 69–83. Google Scholar | DOI

[49] Logan, B. F., Shepp, L. A., ‘A variational problem for random Young tableaux’, Adv. Math. 26(2) (1977), 206–222. Google Scholar | DOI

[50] Lovász, L., and Plummer, M. D., ‘Matching theory’, in North-Holland Mathematics Studies, Vol. 121 (Annals of Discrete Mathematics, 29) (North-Holland Publishing Co., Amsterdam, 1986). Google Scholar

[51] Mcdiarmid, C., ‘Concentration’, in Probabilistic Methods for Algorithmic Discrete Mathematics (Algorithms Combin., vol. 16) (Springer, Berlin, 1998), 195–248. Google Scholar | DOI

[52] Mirsky, L., ‘A dual of Dilworth’s decomposition theorem’, Amer. Math. Monthly. 78 (1971), 876–7. Google Scholar | DOI

[53] Pach, J., and Pinchasi, R., ‘How many unit equilateral triangles can be generated by points in convex position?’, Amer. Math. Monthly. 110(5) (2003), 400–406. Google Scholar | DOI

[54] Pemmaraju, S. V., Exploring the powers of stacks and queues via graph layouts. Thesis (Ph.D.)–Virginia Polytechnic Institute and State University (Ann Arbor, MI, ProQuest LLC, 1992). Google Scholar

[55] Romik, D., ‘The surprising mathematics of longest increasing subsequences’ (Institute of Mathematical Statistics Textbooks, vol. 4) (Cambridge University Press, New York, 2015). Google Scholar | DOI

[56] Sauermann, L. and Zakharov, D., ‘A sharp Ramsey theorem for ordered hypergraph matchings’, 2023, . Google Scholar | arXiv

[57] Schensted, C., ‘Longest increasing and decreasing subsequences’, Canadian J. Math. 13 (1961), 179–191. Google Scholar | DOI

[58] Seppäläinen, T., ‘Large deviations for increasing sequences on the plane’, Probab. Theory Related Fields. 112(2) (1998), 221–44. Google Scholar | DOI

[59] Seppäläinen, T., ‘A growth model in multiple dimensions and the height of a random partial order’, in Asymptotics: Particles, Processes and Inverse Problems (IMS Lecture Notes Monogr. Ser., Vol. 55) (Inst. Math. Statist., Beachwood, OH, 2007), 204–233. Google Scholar | DOI

[60] Stanley, R. P.. ‘Increasing and decreasing subsequences and their variants’, (International Congress of Mathematicians, Vol. I) (Eur. Math. Soc., Zürich, 2007). 545–579. Google Scholar | DOI

[61] Stanley, R. P., Catalan addendum (version of 25 may 2013). 2023. URL: http://www-math.mit.edu/%7Erstan/ec/catadd.pdf. Google Scholar

[62] Steele, J. M., ‘Limit properties of random variables associated with a partial ordering of ’, Ann. Prob. 5(3) (1977), 395–403. Google Scholar

[63] Szabó, T. and Tardos, G., ‘A multidimensional generalization of the Erdős–Szekeres lemma on monotone subsequences’, Combin. Probab. Comput. 10(6) (2001), 557–565. Google Scholar | DOI

[64] Tardos, G., ‘Extremal theory of ordered graphs’, in Proceedings of the International Congress of Mathematicians (World Scientific, Rio de Janeiro, 2018), 3235–3243 . Google Scholar

[65] Veršik, A. M. and Kerov, S. V., ‘Asymptotic behavior of the Plancherel measure of the symmetric group and the limit form of Young tableaux’, Dokl. Akad. Nauk SSSR 233(6) (1977), 1024–1027. Google Scholar

Cité par Sources :