Finitely forcible graphons and permutons
arXiv:1307.2444
Abstract
We investigate when limits of graphs (graphons) and permutations (permutons) are uniquely determined by finitely many densities of their substructures, i.e., when they are finitely forcible. Every permuton can be associated with a graphon through the notion of permutation graphs. We find permutons that are finitely forcible but the associated graphons are not. We also show that all permutons that can be expressed as a finite combination of monotone permutons and quasirandom permutons are finitely forcible, which is the permuton counterpart of the result of Lovasz and Sos for graphons.
arXiv comment30 pages, 18 figures
References in corpus (6)
- On the Number of Pentagons in Triangle-Free Graphs
- Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
- Asymptotic Structure of Graphs with the Minimum Number of Triangles
- Limits of permutation sequences through permutation regularity
- Turán densities of hypercubes
- Infinite dimensional finitely forcible graphon