Independent sets of random trees and sparse random graphs

DOI10.1002/JGT.23225MaRDI QIDQ6978648zbMATH OpenFDO

Authors Steven Heilman

Publication date 27 May 2025

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1002/JGT.23225

zbMATH Keywords

concentration of measureindependent setrandom graphrandom tree

Mathematics Subject Classification ID

Trees (05C05) Density (toughness, etc.) (05C42) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Inequalities; stochastic orderings (60E15)

Cites work

• A bipartite graph with non-unimodal independent set sequence
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Clique cover products and unimodality of independence polynomials
• Cliques in random graphs
• Generating formulas for the number of trees in a graph
• scientific article; zbMATH DE number 5130736 (Why is no real title available?)
• scientific article; zbMATH DE number 4112649 (Why is no real title available?)
• scientific article; zbMATH DE number 3711987 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1990727 (Why is no real title available?)
• scientific article; zbMATH DE number 2040954 (Why is no real title available?)
• Independent sets in random graphs from the weighted second moment method
• Maximum independent sets on random regular graphs
• Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
• New families of graphs whose independence polynomials have only real roots
• Normal convergence problem? Two moments and a recurrence may be the clues
• On independent sets in random graphs
• On maximal independent sets of nodes in trees
• On the independence number of random graphs
• On the independent set sequence of a tree
• On the unimodality of independence polynomials of some graphs
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• Sofic homological invariants and the weak Pinsker property
• Spectra of large random trees
• The independent set sequence of regular bipartite graphs
• The independent set sequence of some families of trees
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• The unimodality of independence polynomials of some graphs
• Tree/endofunction bijections and concentration inequalities
• Two problems on independent sets in graphs

This page was built for publication: Independent sets of random trees and sparse random graphs

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