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

DOI10.1007/S00493-013-2907-0zbMATH Open1313.05198arXiv1111.6007OpenAlexW2077110520MaRDI QIDQ485502FDOQ485502

Viktor Harangi

Publication date: 9 January 2015

Published in: Combinatorica (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

graph densityregular graphsunimodular random graphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Cycle density in infinite Ramanujan graphs
• Limit laws for the number of triangles in the generalized random graphs with random node weights
• THE EXACT MINIMUM NUMBER OF TRIANGLES IN GRAPHS WITH GIVEN ORDER AND SIZE
• KOLMOGOROV BOUNDS FOR THE NORMAL APPROXIMATION OF THE NUMBER OF TRIANGLES IN THE ERDŐS–RÉNYI RANDOM GRAPH
• Matchings in regular graphs: minimizing the partition function

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)