Exchangeable interval hypergraphs and limits of ordered discrete structures

DOI10.1214/19-AOP1384zbMATH Open1464.60030arXiv1802.09015MaRDI QIDQ784163FDOQ784163

Authors: Julian Gerstenberg 

Publication date: 31 July 2020

Published in: The Annals of Probability (Search for Journal in Brave)

Abstract: A hypergraph $(V,E)$ is called an interval hypergraph if there exists a linear order $l$ on $V$ such that every edge $einE$ is an interval w.r.t. $l$; we also assume that $jinE$ for every $jinV$. Our main result is a de Finetti-type representation of random exchangeable interval hypergraphs on $mathbbN$ (EIHs): the law of every EIH can be obtained by sampling from some random compact subset $K$ of the triangle $(x,y):0leqxleqyleq1$ at iid uniform positions $U_1,U_2,dots$, in the sense that, restricted to the node set $[n]:=1,dots,n$ every non-singleton edge is of the form $e=iin[n]:x<U_i<y$ for some $(x,y)inK$. We obtain this result via the study of a related class of stochastic objects: erased-interval processes (EIPs). These are certain transient Markov chains $(I_n,et{a}_n{)}_{ninmathbbN}$ such that $I_n$ is an interval hypergraph on $V=[n]$ w.r.t. the usual linear order (called interval system). We present an almost sure representation result for EIPs. Attached to each transient Markov chain is the notion of Martin boundary. The points in the boundary attached to EIPs can be seen as limits of growing interval systems. We obtain a one-to-one correspondence between these limits and compact subsets $K$ of the triangle with $(x,x)inK$ for all $xin[0,1]$. Interval hypergraphs are a generalizations of hierarchies and as a consequence we obtain a representation result for exchangeable hierarchies, which is close to a result of Forman, Haulk and Pitman. Several ordered discrete structures can be seen as interval systems with additional properties, i.e. Schr"oder trees and binary trees. We describe limits of Schr"oder trees as certain tree-like compact sets. Considering binary trees we thus obtain a homeomorphic description of the Martin boundary of R'emy's tree growth chain, which has been analyzed by Evans, Gr"ubel and Wakolbinger.

Full work available at URL: https://arxiv.org/abs/1802.09015

Recommendations

• Multigraph limits and exchangeability
• scientific article; zbMATH DE number 3884212
• Interval \(k\)-graphs and orders
• scientific article; zbMATH DE number 4091559
• Algorithmic characterizations of interval orderd hypergraphs and applications
• Combinatorial aspects of interval orders and interval graphs
• Graph limits and exchangeable random graphs
• Hypergraphs of Bounded Disjointness
• The order-interval hypergraph of a finite poset and the König property
• scientific article; zbMATH DE number 4117862

zbMATH Keywords

hierarchyexchangeabilityHausdorff distancesimplexMartin boundarybinary tree[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Schr%EF%BF%BD%EF%BF%BDder+tree&go=Go Schr��der tree]interval hypergraphlimits of discrete structurespoly-adic filtration

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Boundary theory for Markov processes (60J50) Exchangeability for stochastic processes (60G09)

Cites Work

• Limits of permutation sequences
• Large networks and graph limits
• A course in metric geometry
• Graph limits and exchangeable random graphs
• The Representation of Partition Structures
• Title not available (Why is that?)
• Lectures on Choquet's theorem
• Title not available (Why is that?)
• Uniform generation of a Schröder tree
• The depth first processes of Galton-Watson trees converge to the same Brownian excursion
• Probabilistic Symmetries and Invariance Principles
• Interval graph limits
• Equipped graded graphs, projective limits of simplices, and their boundaries
• On exchangeable random variables and the statistics of large graphs and hypergraphs
• The representation of composition structures
• Pattern-avoiding permutations and Brownian excursion. I: Shapes and fluctuations.
• Interval hypergraphs and D-interval hypergraphs
• Doob-Martin boundary of Rémy's tree growth chain
• Title not available (Why is that?)
• A representation of exchangeable hierarchies by sampling from random real trees
• Radix sort trees in the large
• General erased-word processes: product-type filtrations, ergodic laws and Martin boundaries
• Doob-Martin compactification of a Markov chain for growing random words sequentially
• Poly-adic filtrations, standardness, complementability and maximality
• Persisting randomness in randomly growing discrete structures: graphs and search trees
• Filtrations of the erased-word processes

Cited In (5)

• General erased-word processes: product-type filtrations, ergodic laws and Martin boundaries
• The order-interval hypergraph of a finite poset and the König property
• Exchangeability and continuum limits of discrete random structures
• Degree bounds for linear discrepancy of interval orders and disconnected posets
• A representation of exchangeable hierarchies by sampling from random real trees

This page was built for publication: Exchangeable interval hypergraphs and limits of ordered discrete structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q784163)