On pattern-avoiding permutons

被引:1
作者
Garbe, Frederik [1 ,2 ,6 ]
Hladky, Jan [3 ]
Kun, Gabor [4 ,5 ]
Pekarkova, Kristyna [2 ]
机构
[1] Heidelberg Univ, Inst Informat, Heidelberg, Germany
[2] Masaryk Univ, Fac Informat, Brno, Czech Republic
[3] Czech Acad Sci, Inst Comp Sci, Prague, Czech Republic
[4] HUN REN Alfred Renyi Inst Math, Budapest, Hungary
[5] Eotvos Lorand Univ, Inst Math, Budapest, Hungary
[6] Heidelberg Univ, Inst Informat, Neuenheimer Feld 205, D-69120 Heidelberg, Germany
基金
欧洲研究理事会;
关键词
pattern-avoidance; permutations; permutons; removal lemma;
D O I
10.1002/rsa.21208
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
The theory of limits of permutations leads to limit objects called permutons, which are certain Borel measures on the unit square. We prove that permutons avoiding a given permutation of order k$$ k $$ have a particularly simple structure. Namely, almost every fiber of the disintegration of the permuton (say, along the x-axis) consists only of atoms, at most (k-1)$$ \left(k-1\right) $$ many, and this bound is sharp. We use this to give a simple proof of the "permutation removal lemma."
引用
收藏
页码:46 / 60
页数:15
相关论文
共 19 条
  • [1] BOGACHEV V. I, 2007, Measure Theory, V1, DOI DOI 10.1371/journal.pgen.1000083
  • [2] Bona M., 2012, Combinatorics of Permutations
  • [3] Bóna M, 2010, DISCRETE MATH THEOR, V12, P89
  • [4] Large Deviation Principle for Random Permutations
    Borga, Jacopo
    Das, Sayan
    Mukherjee, Sumit
    Winkler, Peter
    [J]. INTERNATIONAL MATHEMATICS RESEARCH NOTICES, 2024, 2024 (03) : 2138 - 2191
  • [5] Cooper J., COMBINATORIAL PROBLE
  • [6] Cooper JN, 2006, ELECTRON J COMB, V13
  • [7] SPEARMANS FOOTRULE AS A MEASURE OF DISARRAY
    DIACONIS, P
    GRAHAM, RL
    [J]. JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES B-METHODOLOGICAL, 1977, 39 (02): : 262 - 268
  • [8] Cliques in Dense Inhomogeneous Random Graphs
    Dolezal, Martin
    Hladky, Jan
    Mathe, Andras
    [J]. RANDOM STRUCTURES & ALGORITHMS, 2017, 51 (02) : 275 - 314
  • [9] A measure-theoretic approach to the theory of dense hypergraphs
    Elek, Gabor
    Szegedy, Balazs
    [J]. ADVANCES IN MATHEMATICS, 2012, 231 (3-4) : 1731 - 1772
  • [10] Erdos P., 1935, Compos. Math., V2, P463