The t-stability number of a random graph

MaRDI QIDQ976708zbMATH OpenFDO

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, https://eudml.org/doc/233549, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r59.html

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

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

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).

Review text

Summary: Given a graph \(G = (V, E)\), a vertex subset \(S \subseteq V\) 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 \(\alpha t(G)\) of \(G\) is the maximum order of a \(t\)-stable set in \(G\). The theme of this paper is 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 \rightarrow \infty \), 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 \(t\).

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

(11)

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

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)