On the density of triangles and squares in regular finite and unimodular random graphs

DOI10.1007/S00493-013-2907-0MaRDI QIDQ485502zbMATH OpenOpenAlexFDO

Authors Viktor Harangi

Publication date 9 January 2015

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

graph densityregular graphsunimodular random graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81)

Abstract: We explicitly describe the possible pairs of triangle and square densities for r-regular finite simple graphs. We also prove that every r-regular unimodular random graph can be approximated by r-regular finite graphs with respect to these densities. As a corollary one gets an explicit description of the possible pairs of the third and fourth moments of the spectral measure of r-regular unimodular random graphs.

Review text

The authors explicitly describe the possible pairs of triangle and square densities for \(r\)-regular finite simple graphs. Further, they also prove that every \(r\)-regular unimodular random graph can be approximated by \(r\)-regular finite graphs with respect to these densities. As a corollary, one gets an explicit description of the possible pairs of the third and fourth moments of the spectral measure of \(r\)-regular unimodular random graphs. The study of unimodular random graphs was initiated by \textit{D. Aldous} and \textit{R. Lyons} [Electron. J. Probab. 12, 1454-1508 (2007; Zbl 1131.60003)].

Recommendations

• The measurable Kesten theorem
• Subgraph distributions in dense random regular graphs
• Regular graphs with many triangles are structured
• Triangles in regular graphs with density below one half
• Sparse regular random graphs: spectral density and eigenvectors

Cites work

• A Survey on Spectra of infinite Graphs
• scientific article; zbMATH DE number 3821782 (Why is no real title available?)
• scientific article; zbMATH DE number 3189017 (Why is no real title available?)
• On complete subgraphs of different orders
• On the existence of regular n-graphs with given girth
• On the Minimal Density of Triangles in Graphs
• On the number of \(C_ 5's\) in a triangle-free graph
• Processes on unimodular random networks
• Regular Graphs with Given Girth and Restricted Circuits
• The measurable Kesten theorem

Cited in

(8)

• Limit laws for the number of triangles in the generalized random graphs with random node weights
• Matchings in regular graphs: minimizing the partition function
• KOLMOGOROV BOUNDS FOR THE NORMAL APPROXIMATION OF THE NUMBER OF TRIANGLES IN THE ERDŐS–RÉNYI RANDOM GRAPH
• Finite approximation for unimodular random networks
• The exact minimum number of triangles in graphs with given order and size
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Cycle density in infinite Ramanujan graphs
• The ineffectiveness of the regularity lemma for bounded degree graphs

This page was built for publication: On the density of triangles and squares in regular finite and unimodular random graphs

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