The t-stability number of a random graph

MaRDI QIDQ976708zbMATHFDO

Authors Nikolaos Fountoulakis, Ross J. Kang, Colin McDiarmid

Publication date 16 June 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex degrees (05C07) Asymptotic enumeration (05A16)

Abstract: Given a graph G = (V,E), a vertex subset S is called t-stable (or t-dependent) if the subgraph G[S] induced on S has maximum degree at most t. The t-stability number of G is the maximum order of a t-stable set in G. We investigate the typical values that this parameter takes on a random graph on n vertices and edge probability equal to p. For any fixed 0 < p < 1 and fixed non-negative integer t, we show that, with probability tending to 1 as n grows, the t-stability number takes on at most two values which we identify as functions of t, p and n. The main tool we use is an asymptotic expression for the expected number of t-stable sets of order k. We derive this expression by performing a precise count of the number of graphs on k vertices that have maximum degree at most k. Using the above results, we also obtain asymptotic bounds on the t-improper chromatic number of a random graph (this is the generalisation of the chromatic number, where we partition of the vertex set of the graph into t-stable sets).

Recommendations

• Asymptotics of the independence number of a random subgraph of the graph \(G(n,r,<s)\)
• Asymptotics of the independence number of a random subgraph of the graph \(G(n, r, < s)\)
• Largest sparse subgraphs of random graphs
• Largest sparse subgraphs of random graphs
• On the stability of some Erdős-Ko-Rado type results

Cited in

(9)

• Largest sparse subgraphs of random graphs
• Largest sparse subgraphs of random graphs
• Sharp concentration of the equitable chromatic number of dense random graphs
• On two limit values of the chromatic number of a random hypergraph
• Maximum weight t-sparse set problem on vector-weighted graphs
• Non-concentration of the chromatic number of a random graph
• Induced forests and trees in Erdős-Rényi random graph
• How does the chromatic number of a random graph vary?
• Co-2-plex vertex partitions

This page was built for publication: The \(t\)-stability number of a random graph

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