A Partial Characterization of Robinsonian L^p Graphons

2024/11/28 by Teddy Mishura, Mishura, Teddy
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Point processes and geometric inequalities

paper · pdf · doi:10.48550/arxiv.2411.18886

Abstract

We present a characterization of Robinsonian L^p graphons for p > 5. Each L^p graphon w is the limit object of a sequence of edge density-normalized simple graphs \G_n/‖G_n‖₁\ under the cut distance δ_\Box. A graphon w is Robinson if it satisfies the Robinson property: if x≤ y≤ z, then w(x,z)≤ min\w(x,y),w(y,z)\, and it is Robinsonian if δ_\Box(w,u)=0 for some Robinson u. In previous work, the author and collaborators introduced a graphon parameter Λ that recognizes the Robinson property, where Λ(w) = 0 precisely when w is Robinson. Using functional analytic arguments, we show here that for p > 5, the Robinsonian L^p graphons w are precisely those that are the cut distance limit object of graphs G_n such that Λ(G_n/‖G_n‖₁) → 0.

Related

• Robust Recovery of Robinson Property in L^p-Graphons: A Cut-Norm Approach
• Graphons, cut norm and distance, couplings and rearrangements
• Weak regularity and finitely forcible graph limits
• Graphons of Line Graphs
• Regularity partitions and the topology of graphons