On Concentration of the Independence Number for RandomGraphs

<p dir="ltr">This thesis is organized into three chapters. In the first chapter, we consider the biclique partition number of a graph <i>G = (V, E)</i>, denoted <i>bp(G)</i>, which is the minimum number of pairwise edge disjoint complete bipartite subgraphs of <i>G</i> so that each edge of <i>G</i> belongs to exactly one of them. It can be quickly shown that <i>bp(G) ≤ n − α(G)</i>, where <i>α(G)</i> is the maximum size of an independent set of <i>G</i>. Erdős conjectured in the 80's that for almost every graph <i>G </i>equality holds; i.e., if <i>G = G</i>_<em>n</em>_,1/2 then <i>bp(G) = n − α(G)</i> with high probability. Alon showed that this is false. We show that the conjecture of Erdős is true if we instead take <i>G = G</i>_<em>n,p</em>, where p is constant and less than a certain threshold value p0 ≈ 0.312. This verifies a conjecture of Chung and Peng for these values of p. We also show that if <i>p0</i> < <i>p </i>< 1/2 then <i>bp(G</i>_<em>n,p</em><i>)</i> = n − (1 + Θ(1))α(<i>G</i>_<em>n,p</em>) with high probability.</p><p dir="ltr">In the second chapter, we show that independence number of <i>α(G</i>_<em>n,p</em><i>)</i> is concentrated on two values if <i>n</i>^{<em>−2/3+ε</em>} < p ≤ 1. This result is roughly best possible as an argument of Sah and Sawhney shows that the independence number is not, in general, concentrated on two values for <i>p = o ((log(n)/n)</i>^<em>2/3</em><i>)</i>.</p><p dir="ltr">The third chapter is a follow-up of the second: we show that the independence number of <i>G</i>_<em>n,m</em> is concentrated on two values for <i>n</i>^{<em>5/4+ε</em>} < m ≤ (ⁿ ₂ ), which in turn establishes a distinction between <i>G</i>_<em>n,m</em> and <i>G</i>_<em>n,p</em> with <i>p = m/(</i>^<em>n</em><i> </i>_<em>2</em><i> )</i> in the regime <i>n</i>^{<em>5/4+ε</em>} < m < <i>n</i>^<em>4/3</em>. In this regime the independence number of <i>G</i>_<em>n,m</em> is concentrated on two values while the independence number of <i>G</i>_<em>n,p</em> is not; indeed, for p in this regime variations in <i>α(G</i>_<em>n,p</em>) are determined by variations in the number of edges in <i>G</i>_<em>n,p</em>.</p>