On the independence number of random interval graphs

DOI10.1017/S0963548301004813MaRDI QIDQ2777890zbMATH OpenWikidataFDO

Authors Stéphane Boucheron, W. Fernandez de la Vega

Publication date 17 September 2002

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

Full work available at URL https://doi.org/10.1017/S0963548301004813

zbMATH Keywords

central limit theoremfirst-passage timesgreedy algorithmlarge deviation principle

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05)

Recommendations

• scientific article; zbMATH DE number 1507217
• Random interval graphs
• On the interval number of random graphs
• Constructions of independent sets in random intersection graphs
• On the connectivity of a random interval graph

Cited in

(13)

• Random interval graphs
• On the stability of the independence number of a random subgraph
• Generalised online colouring problems in overlap graphs
• On threshold probability for the stability of independent sets in distance graphs
• Long-range last-passage percolation on the line
• Improved replica bounds for the independence ratio of random regular graphs
• Independence numbers of random subgraphs of a distance graph
• On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
• The Temp Secretary Problem
• scientific article; zbMATH DE number 1507217 (Why is no real title available?)
• On the $b$ -Independence Number of Sparse Random Graphs
• Increasing and other subsequence problems for random interval sequences
• An evolution of interval graphs

This page was built for publication: On the independence number of random interval graphs

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