2
$\begingroup$

Let $\mathbf{d}=(d_1,\dots, d_n)$ be a given degree sequence with $3\leq d_i\leq \Delta$ for every $i$, where $\Delta$ is constant. Let $G(n,\mathbf{d})$ denote the random graph uniformly distributed over the set of all graphs with degree sequence $\mathbf{d}$ . Let $\mathbf{d}'=(d_1',\dots,d_n')$ be another degree sequence with $d_i'\leq d_i$ for every $i$. I am interested in the question of when $G(n,\mathbf{d})$ contains a subgraph with degree sequence $\mathbf{d'}$. As a concrete example, take the random graph with degree sequence $(6,\dots,6,4,\dots,4)$, each value appearing $\frac{n}{2}$ times. Does it contain a subgraph with degree sequence $(3,\dots,3,2,\dots,2)$?

In the case of regular graphs this is not a problem; a random $d$-regular graph contains a $d'$-regular subgraph (for $d'\leq d$) with high probability. However, extending results from random regular graphs to graphs with given degree sequences is generally hard. So I wonder if anything is known.

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .