Making integer multisets graphic

Question

Let $M=(X,f)$ be a multiset, where $X$ is the underlying set of elements and $f:X\rightarrow\mathbb{N}$ is the multiplicity function. For every $k\in\mathbb{N}$ put $k\cdot M:=(X,k\cdot f)$. It is easy to see that for every multiset $M$ of non--negative integers there exists a number $k\in\mathbb{N}$ such that $k\cdot M$ is graphic (i.e. it's the degree multiset of some simple undirected graph). For example, if $M=(X,f)$, where $X=\{a_{1},\dots,a_{n}\}\subset\mathbb{N}$, then one can put $k:=2\cdot\prod_{i}a_{i}$. In this case $k\cdot a_{i}$ is even and $a_{i}\leq k-1$ for all $1\leq i\leq n$, which implies that there exists $a_{i}$-regular graph with $k$ vertices.

Denote as $k(M)$ the minimal number $k\in\mathbb{N}$ such that $k\cdot M$ is graphic. Thus, $k(M)\geq 1$ and $k(M)=1$ if and only if $M$ is graphic. The question is

Can we find a good upper bound or the exact value for $k(M)$?

Answer 1

I will think of $X$ as the set of allowed degree values, with largest value being $b$, and the total number of elements of $M$ to be $m$. If $m=1$ with nonnegative value $b$ as the sole member, then you will need $k$ to be $b+1$, as that many vertices are needed for a graph with vertex of degree $b$. In general, an optimal value for $k$ will be less than $b$, and characterizing those $M$ which need an optimal $k\geq b$ might be a good exercise which I do not do here. The construction I describe below will work for $b$ sufficiently large (likely $b \gt 1$); I leave the details of small $b$ to others.

Let there be a set of $n$ vertices and $k$ a positive integer with $n \geq 2k+1$. Arrange them in a circle, and consider $n$ subsets of adjacent $k+1$ vertices. (If we were to label them from $0$ to $n-1$, the "smaller" difference modulo $n$ of any two labels from this subset should be at most $k$.) The graph $W_{n,2k}$ given by the $n$ vertices and the set of edges being all two element subsets of any of the $n$ subsets is a regular graph of degree $d=2k$. If $n$ is even, there is a matching of vertices that form edges outside of $W_{n,2k}$ which gives a regular graph of degree $d=2k+1$. If $n$ is odd and $2k + 1 \lt n$, there is a partial matching which gives a graph that is almost regular of degree $d=2k+1$, with one vertex of degree $2k$. We will collect all these graphs and graph fragments and call them $F_{n,d}$, where a graph fragment is like a graph but may have one or more "dangling" edges. Except for this minor detail of sometimes leaving an edge dangling, the $F_{n,d}$ would look like regular graphs of degree $d$ on $n$ edges.

Let us consider a second construction of a certain "bipartite" portion of a graph. Arrange $n$ red points in a circle, and arrange $n$ blue points in a circle corresponding to the red points. I will be constructing a drum graph. Given $k\leq n$, for each red point connect it (add an edge) to $k$ blue points which are the point "below" that red point and the next $k-1$ blue points in a clockwise orientation. This will produce a regular bipartite graph of degree $k$ on $2n$ vertices, which I call $D_{2n,k}$. Notice we can later add edges between red vertices or between blue vertices.

I use these to inspire a suboptimal construction for $M$ in which $k \leq b+2$; later I will show how to improve it to reduce $k$. Consider a set of vertices containing the same number of elements as elements of $M$. Turn this into a graph fragment by associating $d$ edges for the element corresponding to (the image under $f$ of) $d \in X$. I will call this a column, and for the moment I will in the construction insist that no two elements in a column are joined by an edge.

I start by applying the fragment construction $F_{k,d}$ in parallel. This means for each vertex I construct a (disjoint) graph fragment using $F_{k,d}$. I now have $km$ many vertices. If I chose $k$ large enough, I could finish off the construction by choosing $k=2b$. We can do better though.

Suppose we choose $k = \lceil (b+1)/2 \rceil$. For many of the vertices the $F_{k,d}$ construction will result in graph fragments with many edges left over. In particular, if we try $F_{k, b}$ for this choice, we have $k$ vertices of degree $k-1$ instead of $k$ vertices of degree $b$. No problem: we now apply the $D_{2k,b+1-k}$ construction, and duplicate this fragment and use the drum construction to pair things up. Thus for each vertex coming from an element of $M$, I have a combination of a red $F_{k,d}$, a blue $F_{k,d}$ and the bipartite portion $D_{2k,d+1-k}$ and thus handle that degree. (When $F_{k,d}$ is a graph and not a fragment, we duplicate it but the $D$ portion will have no edges.) Thus we can create a graph for $M$ with $k \leq b+2$.

Note in the above we only connected edges between vertices associated with exactly one element of $M$: we never added an edge between vertices at two different "levels" of a column or even different levels between two columns. If $M$ has more than one element, you can reduce the value of $k$ needed by connecting column elements to one another to reduce the value of $b$ and thus of $k$ needed. Further, after doing the $F_{k,d'}$ construction ($d'$ is now the number of dangling edges for each vertex in the column), you can connect the various $F_{k,d'}$ together. If you still have an edge left over, duplicate the whole fragment and join edges together. Because $M$ has more than one element, each maximal degree element can be connected to something (assuming $b$ large enough), and this means that the required $k$ is reduced to a value usually much less than $b$.

Gerhard "Who Was That Masked Person?" Paseman, 2015.10.30

Answer 2

THIS VERSION was corrected according to Sergiy's comments.

Let $B$ be some multisubset of $M$. If $M$ is graphical then $$\sum_{d\in M-B} \min(d,|B|) \ge \sum_{d\in B}d - |B|\,(|B|-1),\quad\quad\quad(*)$$ since otherwise $M-B$ can't supply enough edges to match the number of edges that $B$ must shoot towards $M-B$ even if $B$ is a clique. Apart from trivial conditions (being nonnegative and having even sum), a sequence is graphical iff $(*)$ holds for all $B$.

Now replicate each degree $k$ times. For the multisubset $kB$ to satisfy $(*)$ we need $$k\sum_{d\in M-B} \min(d,k\,|B|) \ge k\sum_{d\in B}d - k\,|B|\,(k\,|B|-1),$$ which is true if $k$ is large enough, say for $k\ge k(B)$. I claim that the answer is the maximum of $k(B)$ over all $B$, with 1 added if necessary to make the sum even.

Unfortunately the "min" in the inequality makes it hard to write an explicit expression for $k(B)$.

An issue to settle is that we have only tested subsets of the form $kB$ after the replication. However it is known that you don't need to test all $B$ for $(*)$ to be sufficient, but you only need the cases where $B$ contains all the degrees with the $t$ largest values for each $t$ (at most $n-1$ inequalities). You never need to put the same value both in $B$ and $M-B$. Therefore, multisets of the form $kB$ are sufficient after the replication, which is enough to prove my claim.

Answer 3

I think I am close to an optimal value of k. I will sketch a partial construction, and let others finish it.

First a reduction. We assume $m \gt 1$. Much of this hinges on the maximal degree. If there is a way to construct a graph fragment from M such that no vertex has more than $b$ edges dangling, then we can use the constructions in the other answer with the proviso that no additional edges are added in a single column. So we assume this has been done in a fashion that reduces the value of $b$ significantly. So while I will be really working with a reduced multiset $M'$ derived from $M$, I will call it $M$, and let $b$ be the maximum value for this derived multiset. Also, I am changing notation to let k be the number of additional copies of the column, so the value of k in the problem and the other answer will actually equal $k+1$ in this posting.

So we take the new column (graph fragment) which I will call $M$ also, and add $k$ more copies of $M$. To avoid parity issues with dangling edges, k will be chosen so that the number of dangling edges is even, perhaps at a slight cost of optimality.

Focusing on a top level (copies of a vertex with maximal number of dangling edges), we can connect each of these vertices together leaving b-k dangling edges at each vertex. For each of the $m-1$ remaining vertices in a column, $k$ of its dangling edges can be devoted to connecting up to dangling edges from the top level. Of course, some vertices will have fewer than $k$ edges available. Let us say that the total number of available edges is $(m-1)k - D$, where $D$ represents the sum of the differences of the vertices with fewer than $k$ dangling edges from having $k$ dangling edges. Then we want $k $big enough so that $(k+1)(b-k)$ is at most $((m-1)k - D)(k+1)$, or $mk$ is at least $b +D$.

Suppose we have $mk + 1 \gt b+D$. We hook up the top level to all available edges ( remembering not to connect two vertices in the same column). Now we look at the next level, and connect all vertices at that level. We have wired up all vertices at the top level, reduced the degrees at other levels to $0$ or at least $k$ less, and reduced the next level by at least $k$.

We aren't done, but we can proceed recursively now, either by bumping up $k$ to take care of the lower levels, or by considering the whole fragment and duplicating it, wiring up available edges, and making a larger graph fragment. In any case, the lower bound $mk + 1 \gt b+ D$ is established, and may be used recursively.

Edit 2015.11.06 It turns out the case $m=2$ is instructive. Let $ b \geq c$ be the degrees, and suppose first $b \geq 2c$. Then add $b-c$ copies and hook the top level vertices to one another, leaving $c$ dangles at each of these. Since $b-c \geq c$, we can hook up the top level to the bottom level. If now $2c \geq b$, add $\lceil b/2 \rceil$ copies, hook the top level to one another, hook the bottom level to one another, but leave enough dangles to hook the top level to the bottom. In both cases, less than $b$ additional copies are needed. For $ m \gt 2$, one can mimic the $m=2$ case somewhat. End Edit 2015.11.06

Gerhard "Should Be A Linear Bound" Paseman, 2015.11.03