Comparing graphs of different sizes

DOI10.1017/S096354831700013XMaRDI QIDQ5366968zbMATH OpenOpenAlexFDO

Authors Russell Lyons

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

independent setsreturn probabilities of random walksspanning trees

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81) Combinatorial probability (60C05)

Abstract: We consider two notions describing how one finite graph may be larger than another. Using them, we prove several theorems for such pairs that compare the number of spanning trees, the return probabilities of random walks, and the number of independent sets, among other combinatorial quantities. Our methods involve inequalities for determinants, for traces of functions of operators, and for entropy.

Recommendations

• Asymptotic Enumeration of Spanning Trees
• Random two-component spanning forests
• Identities and inequalities for tree entropy
• The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph
• scientific article; zbMATH DE number 4072069

Cites work

• Asymptotic Enumeration of Spanning Trees
• Building uniformly random subtrees
• Conditioned Galton-Watson trees do not grow
• Growth of the Number of Spanning Trees of the Erdős–Rényi Giant Component
• scientific article; zbMATH DE number 3109251 (Why is no real title available?)
• Identities and inequalities for tree entropy
• Jensen's inequality for spectral order and submajorization
• On symmetric random walks with random conductances on \(\mathbb Z^d\)
• Processes on unimodular random networks
• Return probabilities of a simple random walk on percolation clusters
• Some intersection theorems for ordered sets and graphs
• Über monotone Matrixfunktionen
• Unimodular random trees

Cited in

(3)

• How unproportional must a graph be?
• Monotonicity of average return probabilities for random walks in random environments
• Monotonicity for continuous-time random walks

This page was built for publication: Comparing graphs of different sizes

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