\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{amsmath,amsthm,amssymb,amsfonts}
\usepackage{graphicx}
\usepackage[ragged, flushmargin, bottom]{footmisc}
%theorems
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{question}[theorem]{Problem}
%\numberwithin{equation}{section}
\newcommand{\swap}[4]{#1 \overset{#3}{\underset{#4}{\rightleftharpoons}} #2}
\newcommand{\ceil}[1]{ \left \lceil #1 \right \rceil }
\newcommand{\CL}[1]{\left\lceil#1\right\rceil}
\newcommand{\FL}[1]{\left\lfloor#1\right\rfloor}
\title{New Results on Degree Sequences of Uniform Hypergraphs}
\author{Sarah Behrens$^{1,4,5}$\and Catherine Erbes$^{2,4,6}$\and Michael Ferrara$^{2,4,7}$\and Stephen G. Hartke$^{1,4,5}$\and Benjamin Reiniger$^{3,4}$\and Hannah Spinoza$^{3,4}$\and Charles Tomlinson$^{1,4}$}
\date{\dateline{??}{??}\\
\small Mathematics Subject Classifications: 05C07, 05C65}
\begin{document}
\footnotetext[1]{Department of Mathematics, University of Nebraska-Lincoln, {\tt s-sbehren7@math.unl.edu, hartke@math.unl.edu, ctomlinson@math.unl.edu}}
\footnotetext[2]{Department of Mathematical and Statistical Sciences, University of Colorado Denver, {\tt catherine.erbes@ucdenver.edu, michael.ferrara@ucdenver.edu}}
\footnotetext[3]{Department of Mathematics, University of Illinois Urbana-Champaign, {\tt hkolb2@illinois.edu, reinige1@illinois.edu}}
\footnotetext[4]{Research supported in part by NSF grant DMS 08-38434, ``EMSW21-MCTP: Research Experience for Graduate Students".}
\footnotetext[5]{Research supported in part by National Science Foundation Grant DMS-0914815.}
\footnotetext[6]{Research supported in part by UCD GK12 project, National Science Foundation Grant DGE-0742434.}
\footnotetext[7]{Research supported in part by Simons Foundation Collaboration Grant \#206692.}
\maketitle
\begin{abstract}
A sequence of nonnegative integers is $k$-graphic if it is the degree sequence of a $k$-uniform hypergraph.
The only known characterization of $k$-graphic sequences is due to Dewdney in 1975.
As this characterization does not yield an efficient algorithm, it is a fundamental open question to determine a more practical characterization.
While several necessary conditions appear in the literature, there are few conditions that imply a sequence is $k$-graphic.
In light of this, we present sharp sufficient conditions for $k$-graphicality based on a sequence's length and degree sum.
Kocay and Li gave a family of edge exchanges (an extension of 2-switches) that could be used to transform one realization of a 3-graphic sequence into any other realization.
We extend their result to $k$-graphic sequences for all $k \geq 3$.
Finally we give several applications of edge exchanges in hypergraphs, including generalizing a result of Busch et al. on packing graphic sequences.
{\bf Keywords:} degree sequence, hypergraph, edge exchange, packing
\end{abstract}
\section{Introduction}
A hypergraph $H$ is {\it $k$-uniform}, or is a {\it $k$-graph}, if every edge contains $k$ vertices.
A $k$-uniform hypergraph is {\it simple} if there are no repeated edges.
Thus, a simple 2-uniform hypergraph is a simple graph.
For a vertex $v$ in a $k$-graph $H$, the {\it degree of $v$}, denoted $d_H(v)$ (or simply $d(v)$ when $H$ is understood) is the number of edges of $H$ that contain $v$.
As with 2-graphs, the list of degrees of vertices in a $k$-graph $H$ is called the {\it degree sequence} of $H$.
Let $\pi = (d_1, \ldots, d_n)$ be a nonincreasing sequence of nonnegative integers. We let $\sigma(\pi)$ denote the sum $\sum_{i=1}^n d_i$, and when it is convenient, we write $\pi = (d_1^{m_1}, \ldots, d_n^{m_n})$, where exponents denote multiplicity.
If $\pi$ is the degree sequence of a simple $k$-graph $H$, we say $\pi$ is {\it $k$-graphic}, and that $H$ is a {\it $k$-realization} of $\pi$. When $k=2$, we will simply say that $\pi$ is {\it graphic} and that $H$ is a {\it realization} of $\pi$.
Our work in this area is motivated by the following fundamental problems:
\begin{question}\label{Char}
Determine an efficient characterization of $k$-graphic sequences for all $k \geq 3$.
\end{question}
\begin{question}\label{Real}
Investigate the properties of the family of $k$-realizations of a given sequence.
\end{question}
We will present results relating to each of these problems. Our results are motivated by similar work on graphic sequences.
When $k=2$, there are many characterizations of graphic sequences, including those of Havel \cite{Hav} and Hakimi \cite{Hak}, and Erd\H{o}s and Gallai \cite{ErdGal}.
Sierksma and Hoogeveen \cite{SH} list seven criteria and give a unifying proof.
For $k \geq 3$, Problem \ref{Char} appears to be much less tractable.
The following theorem from \cite{Dew} is the only currently known characterization of $k$-graphic sequences for $k \geq 3$.
\begin{theorem}[Dewdney 1975]\label{theorem:Dewdney}
Let $\pi = (d_1, \ldots, d_n)$ be a nonincreasing sequence of nonnegative integers. $\pi$ is $k$-graphic if and only if there exists a nonincreasing sequence $\pi' = (d_2', \ldots, d_n')$ of nonnegative integers such that
\begin{enumerate}
\item $\pi'$ is $(k-1)$-graphic,
\item $\sum_{i=2}^n d_i' = (k-1)d_1$, and
\item $\pi'' = (d_2 -d_2', d_3 -d_3', \ldots, d_n-d_n')$ is $k$-graphic.
\end{enumerate}
\end{theorem}
Dewdney's characterization hinges on a relatively simple, yet quite useful, idea that we will utilize in the sequel. Given a vertex $v$ in a hypergraph $H$, let $H_v$ denote the subgraph of $H$ with vertex set $V(H)$ and edge set consisting of the edges of $H$ that contain $v$. The {\it link} of $v$, $L_H(v)$, is then the hypergraph obtained by deleting $v$ from each edge in $H_v$. Thus, if $H$ is $k$-uniform, then $L_H(v)$ is a $(k-1)$-uniform hypergraph, and if $H$ is a graph, then each vertex in $N_H(v)$ gives rise to a 1-edge in $L_H(v)$.
Suppose that $\pi'=(x_1,\dots,x_n)$ is a $(k-1)$-graphic sequence and $\pi''=(y_1,\dots,y_n)$ is a $k$-graphic sequence.
It follows that the sequence
$$\pi=\left(\frac{\sigma(\pi')}{k-1},x_1+y_1,\dots,x_n+y_n\right)$$ is also $k$-graphic. To see this, let $H_1$ be a $(k-1)$-realization of $\pi'$ and $H_2$ be a $k$-realization of $\pi''$, both with vertex set $\{v_1,\dots,v_n\}$. Add a new vertex $v_0$ to each edge in $H_1$ to obtain the $k$-graph $H_1'$. Then $H=H_1'+H_2$ is a realization of $\pi$ as desired; furthermore, $\pi'$ is the degree sequence of $L_H(v_0)$.
Considering this process in reverse, a sequence $\pi=(d_1,\dots,d_n)$ is $k$-graphic if for some index $i$ there is a $(k-1)$-graphic sequence $\pi'=(x_1,\dots, x_{i-1},0,x_{i+1},\dots,x_n)$ such that $$\pi''=(d_1-x_1,\dots,d_{i-1}-x_{i-1},0,d_{i+1}-x_{i+1},\dots,d_n-x_n)$$ is $k$-graphic. Here, as above, we would be able to construct a realization $H$ of $\pi$ in which $\pi'$ is the degree sequence of the link $L_H(v_i)$. Again, note that the $i$'th term of each sequence is 0, corresponding to the vertex $v_i$ that does not appear in the $(k-1)$-realization of $\pi$ or the $k$-realization of $\pi'$.
This is the crucial idea of the Havel-Hakimi algorithm, wherein it is proved that it is sufficient to select $\pi'=(0,1^{d_1},0^{n-d_1-1})$ (which is trivially $1$-graphic) and therefore one must only determine the graphicality of the residual sequence $(0,d_2-1,\dots,d_{d_1+1}-1,d_{d_1+2},\dots,d_n)$. In Theorem \ref{theorem:Dewdney}, however, there is no standard form of the ``link sequence" that is sufficient to determine if $\pi$ is $k$-graphic. Were one able to similarly demonstrate that it suffices to check only one $(k-1)$-graphic $\pi'$, or even a small number, then this would represent significant progress towards Problem \ref{Char}.
In addition to Theorem \ref{theorem:Dewdney}, several other authors have studied Problem \ref{Char}. Bhave, Bam and Deshpande \cite{BBD} gave an Erd\H{o}s-Gallai-type characterization of degree sequences of loopless linear hypergraphs. While interesting in its own right, their result does not directly generalize to Problem \ref{Char}. Colbourn, Kocay and Stinson \cite{CKS} proved that several related problems dealing with 3-graphic sequences are NP-complete. Additionally, several necessary conditions for a sequence to be $3$-graphic have been found (see Achuthan, Achuthan, and Simanihuruk \cite{AAS}, Billington \cite{Bill88}, and Choudum \cite{Choudum} for some).
Unfortunately, Achuthan et al.~\cite{AAS} showed that the necessary conditions of \cite{AAS}, \cite{Bill88}, and \cite{Choudum} are not sufficient. In fact, surprisingly few sufficient conditions for a sequence to be $k$-graphic exist, despite the apparent interest in the general characterization problem. Inspired by sufficient conditions for 2-graphic sequences given by Yin and Li \cite{YinLi}, Aigner and Triesch \cite{AigTriesch}, and Barrus, Hartke, Jao and West \cite{BHJW}, we present in Section \ref{SCSection} some general sufficient conditions for $k$-graphicality when $k\ge 3$.
A useful tool for studying graphic sequences is the edge exchange, or 2-switch, where two edges in a graph are replaced with two nonedges while maintaining the degree of each vertex. In particular, this is a key tool in the standard proof of the Havel-Hakimi characterization of graphic sequences \cite[p.~45--46]{West}. It is our hope that a better understanding of edge exchanges may lead to an efficient Havel-Hakimi-type characterization of $k$-graphic sequences. Additionally, edge exchanges have proved vital in approaching a number of problems for graphs in the vein of Problem \ref{Real} (cf. \cite{BHK, BFHJKW, Chen, FLMW12}).
In Section~\ref{EESection}, we give a small collection of elementary edge exchanges that can be applied to transform any realization of a $k$-graphic sequence into any other realization. This extends a result of Kocay and Li on $3$-graphic sequences. As an application of these edge exchanges, we prove a result about packing of $k$-graphic sequences.
Busch et al.~\cite{BFHJKW} proved that graphic sequences pack under certain degree and length conditions.
We extend their result to $k$-graphic sequences.
\section{Sufficient conditions on length}\label{SCSection}
\subsection{Results}
In this section, we give a new sufficient condition for a sequence to be $k$-graphic, and we give several corollaries that are inspired by previous results on graphic sequences.
We say that a nonincreasing sequence is \textit{near-regular} if the difference between the first and last terms of the sequence is at most 1.
The main result of this section shows that if the beginning of a sequence is near-regular, which will be made more precise later, then the sequence is $k$-graphic.
For graphs, this is a simple consequence of the Erd\H{o}s-Gallai inequalities (see for example Lemma 2.1 of \cite{YinLi}), but for $k\geq3$ the situation is more complex.
We will state our theorems here, discuss their sharpness in Section \ref{SCSharp}, and present the proofs in Section \ref{SCProofs}.
\begin{theorem}\label{thm:NR}
Let $\pi$ be a nonincreasing sequence with maximum entry $\Delta$ and $t$ entries that are at least $\Delta-1$. If $k$ divides
$\sigma(\pi)$ and
\begin{equation}\label{ellform}
\binom{t-1}{k-1}\geq \Delta,
\end{equation}
then $\pi$ is $k$-graphic.
\end{theorem}
This result, combined with a variety of classical and new ideas, yields three immediate corollaries.
While poset methods had earlier been used for degree sequences, Aigner and Triesch \cite{AigTriesch} systematized this approach.
Bauer et al.~\cite{BBHKS} also used posets to study degree sequences, but with a different order relation.
Using the same poset as Aigner and Triesch, we show that with a large enough degree sum, the near-regular condition is unnecessary.
\begin{corollary}\label{cor:MinSum}
Let $\pi$ be a nonincreasing sequence with maximum term $\Delta$, and let $p$ be the minimum integer such that $\Delta \leq \binom{p-1}{k-1}$.
If $k$ divides $\sigma(\pi)$ and $\sigma(\pi) \geq (\Delta-1)p+1$, then $\pi$ is $k$-graphic.
\end{corollary}
\noindent This lower bound on the sum of the sequence immediately gives the following sufficient condition on the length of a sequence, analogous to the result of Zverovich and Zverovich~\cite{ZZ} for graphs.
\begin{corollary}\label{cor:MinLength}
Let $\pi$ be a nonincreasing sequence with maximum term $\Delta$ and minimum term $\delta$, and let $p$ be the minimum integer such that $\Delta \leq \binom{p-1}{k-1}$.
If $k$ divides $\sigma(\pi)$ and $\pi$ has length at least $\frac{(\Delta-1)p-\Delta+\delta+1}{\delta}$, then $\pi$ is $k$-graphic.
\end{corollary}
\noindent Finally, if we know a little bit more about the sequence, we can refine the length condition.
A sequence is \textit{gap-free} if it has entries with all values between the largest entry $\Delta$ and the smallest entry $\delta$.
The graphicality of gap-free sequences was studied by Barrus, Hartke, Jao, and West \cite{BHJW}.
\begin{corollary}\label{cor:GapFree}
Let $\pi$ be a gap-free sequence with maximum term $\Delta$ and minimum term $\delta =1$, and let $p$ be the minimum integer such that $\Delta \leq \binom{p-1}{k-1}$. If $\sigma(\pi)$ is divisible by $k$ and $\pi$ has length at least $(\Delta-1)(p-\Delta/2)+1$, then $\pi$ is $k$-graphic.
\end{corollary}
The following lemma gives a simple necessary condition for a sequence to be $k$-graphic, and additionally gives information about the $k$-realizations of a sequence.
This is used to show the sharpness of Corollaries \ref{cor:MinSum} and \ref{cor:MinLength}, and also in Section \ref{EESection}.
\begin{lemma}\label{initialcliquelem}
If $\pi = (d_1, \ldots, d_n)$ is a $k$-graphic sequence, then
\[
\sum_{i=1}^t d_i \le k\binom{t}{k} + (k-1)\sum_{j=t+1}^n d_j
\]
for $k \le t \le n$. If equality holds, then the $t$ vertices of highest degree in any $k$-realization of $\pi$ form a clique, and any edge not contained in the clique contains exactly one vertex outside the clique.
\end{lemma}
\subsection{Sharpness}\label{SCSharp}
Theorem \ref{thm:NR} is sharp, as can by seen by examination of the sequence $(\Delta^M)$, for any $\Delta$.
For Corollary \ref{cor:MinSum}, consider the sequence
\[ \pi_j = \left( \left(\binom{j-1}{k-1}-(k-1)\right)^{j-1}, \binom{j-1}{k-1}-k-j+1\right),\] where $j \geq k+2$.
The maximum term $\Delta_j$ of $\pi_j$ satisfies $\binom{j-2}{k-1}< \Delta_j \leq \binom{j-1}{k-1}$, so in the terminology of Corollary \ref{cor:MinSum}, $p = j$.
We also have $\sigma(\pi_j)=(\Delta_j-1)j$, and $k$ divides $\sigma(\pi_j)$.
However, $\pi_j$ is not $k$-graphic, for the inequality in Lemma \ref{initialcliquelem} does not hold for $\pi_j$ when $t = j-1$.
To see that Corollary \ref{cor:MinSum} is also sharp when $p = k+1$, consider the sequence $\pi = (k, (k-1)^k)$.
This is realized by a complete $k$-graph on $k+1$ vertices with one edge removed, and has degree sum $\sigma(\pi) = k^2$.
Subtracting one from each of the last $k$ terms yields the sequence $\pi' = (k, (k-2)^k)$, with degree sum $k^2-k$.
This is not $k$-graphic: suppose $H$ is a $k$-realization of $\pi'$. Let $S$ be the set of vertices of degree $k-2$ in $H$, and let $v$ be the vertex of degree $k$.
Every edge containing $v$ must also contain a $(k-1)$-subset of $S$. There are exactly $k$ of these.
However, this means each vertex in $S$ must have degree $k-1$.
Corollary \ref{cor:MinLength} is best possible up to a factor depending only on $k$. To see this, first note that $\binom{p-2}{k-1}< \Delta$, so $p<(k-1)e\Delta^{1/(k-1)}+2$. Then the minimum length required by the corollary is bounded above by
\[
\frac{1}{\delta}\left((\Delta-1)((k-1)e\Delta^{1/(k-1)}+2) -\Delta+\delta+1\right)
\]
which, when $\Delta > \delta$, is at most
\[
\frac{\Delta^{1+1/(k-1)}}{\delta}\left(e(k-1)(1-\frac{1}{\Delta})+\frac{2}{\Delta^{1/(k-1)}}\right).
\]
Now, as $\Delta$ becomes large, this quantity is bounded above by
\[
\frac{C\Delta^{1+1/(k-1)}}{\delta},
\]
where $C$ depends only on $k$.
Thus, a weaker but simpler form of Corollary \ref{cor:MinLength} is: If $\pi$ is a nonincreasing sequence with maximum term $\Delta$ and minimum term $\delta$ such that $\delta \neq \Delta$, $k$ divides $\sigma(\pi)$, and the length of $\pi$ is at least $\frac{C\Delta^{1+1/(k-1)}}{\delta}$, then $\pi$ is $k$-graphic.
%For fixed $k$ and $\delta$, the bound given by Corollary \ref{cor:MinLength} is asymptotically correct as a function of $\Delta$.
Now, consider the sequence $\pi =(\Delta^{M}, \delta^m)$, where $\delta<\Delta$ and $M=c_1\Delta^{1/(k-1)}$ for some $c_1 < k/e^2$.
By Lemma \ref{initialcliquelem}, if $\pi$ has length less than $\ceil{ \frac{ M\Delta - k\binom{M}{k} }{(k-1)\delta} }+M$, then it is not $k$-graphic.
%Corollary \ref{cor:MinLength} is best possible up to a factor depending only on $k$. Consider the sequence $\pi =(\Delta^{M}, \delta^m)$, where $\Delta$ and $\delta$ are fixed, and $M=c_1\Delta^{1/(k-1)}$ for some $c_1 < k/e$.
%By Lemma \ref{initialcliquelem}, if $\pi$ is $k$-graphic, then $m$ must be at least $\ceil{ \frac{ M\Delta - k\binom{M}{k} }{(k-1)\delta} }$.
A lower bound on this expression is:
\begin{align*}
\frac{M\Delta - k\binom{M}{k}}{(k-1)\delta} + M &\geq \frac{M\Delta - k\left(\frac{Me}{k}\right)^k }{(k-1)\delta} + M \\
&= \frac{ c_1\Delta^{1+1/(k-1)} - k \left(\frac{c_1 e\Delta^{1/(k-1)} }{k}\right)^k }{(k-1)\delta} + c_1\Delta^{1/(k-1)} \\
&= \frac{\Delta^{1+1/(k-1)} }{\delta} \left( \frac{ c_1 -k \left(\frac{c_1 e}{k}\right)^k }{(k-1)} \right) + c_1\Delta^{1/(k-1)}\\
& =c_2 \frac{\Delta^{1+1/(k-1)}}{\delta} + c_1 \Delta^{1/(k-1)},
\end{align*}
where $c_2= \frac{ c_1 -k \left(\frac{c_1 e}{k}\right)^k }{(k-1)}$.
Thus, if the length of $\pi$ is less than $c_2 \frac{\Delta^{1+1/(k-1)}}{\delta}$, $\pi$ is not $k$-graphic.
Comparing this to the result in the previous paragraph establishes our claim.
%Using the observation that $\Delta \leq \binom{p-1}{k-1}\leq \left(\frac{(p-1)e}{k-1}\right)^{k-1}$, which gives a lower bound on $p$ in terms of $\Delta$ and $k$, the minimum length condition of Corollary \ref{cor:MinLength} can be expressed as
%\[
%\left(\frac{k-1}{e}\right)\frac{\Delta^{1+1/(k-1)}}{\delta}-\frac{k-1}{e\delta}\Delta^{1/(k-1)}+1,
%\]
%so this establishes the claim.
\subsection{Proofs}\label{SCProofs}
\begin{proof}[Proof of Theorem \ref{thm:NR}]
We will show that $\pi$ is $k$-graphic by constructing an appropriate $(k-1)$-graphic link sequence and $k$-graphic residual sequence, as described in the introduction following Theorem~\ref{theorem:Dewdney}.
First, note that if $\Delta =1$, then $\pi = (1^{mk},
0^{n-mk})$ for some integer $m$. This sequence is realized by a set
of $m$ disjoint edges and $n-mk$ isolated vertices. Thus, we can
assume that $\Delta >1$, and in particular, $t > k$.
When $k=2$, the result follows from the Erd\H{o}s-Gallai inequalities, so we assume $k \geq 3$.
Consider the least $k$ for which the theorem does not hold.
Among all nonincreasing sequences that do not satisfy the theorem for this $k$, consider those that have the smallest maximum term, and let $\pi = (d_0, \ldots, d_{n-1})$ be one such sequence that minimizes the multiplicity of the largest term, $\Delta$.
Let
\[ c=\max \left\{ i\in\mathbb{Z} : \sum_{j=1}^{n-1} \max\{0, d_j-i\} \geq (k-1)\Delta \right\}. \]
Note that $c \leq \Delta-1$, and we further claim that $c \geq 0$.
Indeed, if $\Delta \geq k$, then $\sum_{j=1}^{n-1}d_j \geq (t-1)(\Delta-1)\geq k(\Delta-1)\geq (k-1)\Delta$.
If $\Delta < k$, then since $t > k$ there are $k$ terms in the set $\{d_2, \ldots, d_t\}$ that are at least $\Delta-1$. Their sum is at least $k(\Delta-1)$.
Let $A=\sigma(\pi)-\Delta-k(\Delta-1)$. Since $k$ divides $\sigma(\pi)$, $k$ must also divide $A+\Delta$, so $A \geq k-\Delta$. Then $\sum_{i=1}^{n-1}d_j=A+k(\Delta-1) \geq k-\Delta +k(\Delta-1)=(k-1)\Delta$. Thus, $c\geq 0 $.
Define the sequence $L'=(l_1', \ldots, l_{n-1}')$ by $l_j'= \max\{0,d_j-c\}$, and let $s=\sigma(L')-(k-1)\Delta$.
Create the link sequence $L$ by subtracting 1 from each of the first $s$ terms of $L'$.
That is, $L=(l_1, \ldots, l_{n-1})$, where
\[
l_i =
\begin{cases}
l_i'-1 & \text{ if } 1\le i \le s, \\
l_i' & \text{ if } i > s.
\end{cases}
\]
Finally, let $R=(r_1, \ldots, r_{n-1})$ be the residual sequence, given by $r_j = d_j - l_j$ for $j=1, \ldots, n-1$.
It suffices to show that $L$ is $(k-1)$-graphic and $R$ is $k$-graphic, as adding a new vertex $v_0$ to each edge of a $(k-1)$-realization of $L$ and then combining the resulting $k$-graph with a $k$-realization of $R$ gives a $k$-realization of $\pi$.
Let $m$ be the number of nonzero entries of $L'$. First suppose $m
\geq t-1$. Since $(d_0, \ldots, d_{t-1})$ is near-regular, the
construction of $L'$ implies that $(l_1', \dotsc, l_{t-1}')$ is
near-regular, and so $(l_1, \dotsc, l_{t-1})$ is near-regular.
Let $\Delta_L$ be the largest term in $(l_1, \ldots, l_{t-1})$.
We now bound $\Delta_L$ in order to show that $L$
meets the conditions of the theorem and thus is $(k-1)$-graphic by
the minimality of $\pi$. Since $\sigma(L)=(k-1)\Delta$ and $m \geq t-1$, we have
\[
\Delta_L = \CL{\frac{\sum_{i=1}^{t-1}l_i}{t-1}} \le
\CL{\frac{(k-1)\Delta}{t-1}} \le
\CL{\frac{k-1}{t-1}\binom{t-1}{k-1}} = \CL{\binom{t-2}{k-2}}=
\binom{t-2}{k-2}.
\]
Therefore, $L$ satisfies the conditions of the theorem,
and by the minimality of $\pi$, it is $(k-1)$-graphic.
If $m < t-1$, then we must have $c = \Delta -1$, which means $L'=(1^m,
0^{n-1-m})$ and $L=(1^{(k-1)\Delta}, 0^{n-1-(k-1)\Delta})$.
This sequence has a $(k-1)$-realization consisting of $\Delta$ disjoint edges and
$n-1-(k-1)\Delta$ isolated vertices.
Now we turn our attention to $R$.
Since $r_i = d_i - l_i$ and $l_i= d_i-c$ or $l_i=d_i-c-1$ for $i \leq m$, we see that $r_i = c$ or $r_i=c+1$ for $i \leq m$.
Thus, $R=((c+1)^s, c^{m-s}, d_{m+1}, \ldots, d_{n-1})$. Note that $\sigma(R)= s+mc+\sum_{i=m+1}^{n-1}d_i =\sum_{i=1}^{n-1}d_i-(k-1)\Delta=\sigma(\pi)-k\Delta$, so $k$ divides $\sigma(R)$.
If $\Delta_R \leq \binom{m-1}{k-1}$, then the minimality of $\pi$ implies that $R$ is $k$-graphic, so showing this inequality is our goal.
Note that $c+1 \leq \Delta$. Suppose first that $c+1< \Delta$.
If $m > t -1$, then
\[
c+1 < \Delta \leq \binom{t-1}{k-1} \leq \binom{m-1}{k-1}
\]
and we have our result. Since $c<\Delta-1$, we have $m \ge t-1$, and so we may assume that $m = t-1$.
In this case,
\[
L=\left( \CL{\frac{k-1}{t-1}\Delta}^s,
\FL{\frac{k-1}{t-1}\Delta}^{m-s}, 0^{n-1-m}\right).
\]
Hence
\begin{align*}
\Delta_R \leq \Delta-\FL{\frac{k-1}{t-1}\Delta} & < \Delta -\frac{k-1}{t-1}\Delta +1\\
& =\left(1-\frac{k-1}{t-1}\right)\Delta +1 \\
& \leq \frac{t-k}{t-1}\binom{t-1}{k-1} + 1 = \binom{t-2}{k-1}+1,
\end{align*}
so $\Delta_R \leq \binom{t-2}{k-1}=\binom{m-1}{k-1}$.
Thus, $R$ is $k$-graphic.
If $c+1=\Delta$, then $m \leq t-1$.
In this case, any terms of $\pi$ that are equal to $\Delta-1$ become
0 in $L'$. So $\pi =(\Delta^{m+1},
(\Delta-1)^{t-1-m}, d_{t}, \ldots, d_{n-1})$, and if $m=t-1$, there
are no terms in $\pi$ equal to $\Delta-1$. Then, $R=(\Delta^s,
(\Delta-1)^{t-1-s},d_{t}, \ldots, d_n)$, and we need to show that
$\Delta \leq \binom{t-2}{k-1}$. Since $L'=(1^m, 0^{n-1-m})$ and
$L=(1^{(k-1)\Delta}, 0^{n-1-(k-1)\Delta})$, we have $(k-1)\Delta
\leq m \leq t-1$.
Thus, $(k-1)\Delta \leq t-1$, so $\Delta \leq
\frac{t-1}{k-1}$.
When $t >k+1$, we have $\frac{t-1}{k-1} \leq
\binom{t-2}{k-1}$. If $t =k+1$, then $\Delta \leq \frac{k}{k-1}$,
and since $\Delta$ is an integer, $\Delta \leq 1=\binom{t-2}{k-1}$.
Thus, $\Delta \leq \binom{t-2}{k-1}$, and by the minimality of
$\pi$, $R$ is $k$-graphic.
\end{proof}
To prove the first corollary, we require some additional terminology. The \textit{dominance order}, $\preceq$, is defined on the set $D(n,\sigma)$ of nonnegative nonincreasing sequences with length $n$ and sum $\sigma$. For two elements $\pi=(d_1, \ldots, d_n)$ and $\pi'=(d_1', \ldots, d_n')$ of $D(n,\sigma)$, we say $\pi \preceq \pi'$ if $\sum_{i=1}^m d_i \leq \sum_{i=1}^m d_i'$ for all $1 \leq m \leq n$. In this poset the set of $k$-graphic sequences forms an ideal (a downward-closed set) (see \cite{AigTriesch} for $k=2$ and \cite{DR} or \cite{KR} for $k \geq 3$).
We are now prepared to give our proofs.
\begin{proof}[Proof of Corollary \ref{cor:MinSum}]
Suppose $\sigma(\pi)=m\geq (\Delta-1)p+1$. Then there is a sequence $\pi'$ that has the same sum and maximum degree such that $\pi \preceq \pi'$ in the dominance order, but the first $p$ terms of $\pi'$ form a near-regular sequence.
By Theorem \ref{thm:NR}, $\pi'$ is $k$-graphic, and since $k$-graphic sequences form an ideal, $\pi$ is also $k$-graphic.
\end{proof}
\begin{proof}[Proof of Corollary \ref{cor:GapFree}]
A gap-free sequence of length $n$ with minimum term 1 has degree sum at least $\sum_{i=1}^{\Delta} i + (n-\Delta) = \binom{\Delta+1}{2} + (n-\Delta)$. Using this sum in Corollary \ref{cor:MinSum} and solving for $n$ yields the result.
\end{proof}
\begin{proof}[Proof of Lemma \ref{initialcliquelem}]
Choose a set $S$ of $t$ vertices in a $k$-realization $H$ of $\pi$. The subgraph induced by $S$ has degree sum at most $k \binom{t}{k}$. A vertex $w$ in $V(H) \setminus S$ contributes at most $(k-1) d_H(w)$ to the degree sum of vertices in $S$. Thus, $\displaystyle \sum_{i=1}^t d_i \le k\binom{t}{k} + (k-1)\sum_{j=t+1}^n d_j$. If equality holds, each vertex $w$ outside $S$ contributes exactly $(k-1) d_H(w)$ to $\sum_{i=1}^t d_i$. Thus, every edge containing $w$ consists of $w$ as the only vertex outside $S$ and $k-1$ vertices from $S$. Any edge whose vertex set is not contained in $S$ thus consists of only one vertex outside $S$, as claimed.
\end{proof}
\section{Edge exchanges}\label{EESection}
\subsection{Edge exchanges in graphs and hypergraphs}
An edge exchange is any operation that deletes a set of edges in a $k$-realization of $\pi$ and replaces them with another set of edges, while preserving the original vertex degrees. When $i$ edges are exchanged, we call this an \textit{$i$-switch}. The 2-switch operation has been used to prove many results about graphic sequences; for examples see \cite{BHK,BFHJKW, Chen, FLMW12}.
For completeness, we now formally define edge exchanges in hypergraphs. Let $F_1$ and $F_2$ be $k$-graphs on the same vertex set $S$ such that for every $x \in S$, $d_{F_1}(x)=d_{F_2}(x)$. Let $H$ be a $k$-multihypergraph containing a subgraph $F_1'$ on vertex set $T$ such that $F_1' \cong F_1$ via the isomorphism $\phi:T \rightarrow S$.
The {\it edge exchange} $\epsilon(F_1, F_2)$ applied to $H$ replaces the edges of $F_1'$ with the edges of a subgraph $F_2'$ that is isomorphic to $F_2$ by the same map $\phi$.
Define $\mathcal{M}_k(\pi)$ to be the set of $k$-uniform multihypergraphs that realize a sequence $\pi$, and $\mathcal{S}_k(\pi) \subseteq \mathcal{M}_k(\pi)$ be the set of simple $k$-realizations of $\pi$. Let $\mathcal{F} \subseteq \mathcal{M}_k(\pi)$ and $\mathcal{Q}$ be a collection of edge exchanges such that $\epsilon(F_1,F_2)\in{\mathcal Q}$ if and only if $\epsilon(F_2,F_1)\in{\mathcal Q}$. Then $G(\mathcal{F}, \mathcal{Q})$ is the graph whose vertices are the elements of $\mathcal{F}$, with an edge between vertices $H_1$ and $H_2$ if and only if $H_1$ can be obtained from $H_2$ by an edge exchange in $\mathcal{Q}$. Note that the symmetry condition imposed on ${\mathcal Q}$ permits us to define $G({\mathcal F}, {\mathcal Q})$ as an undirected graph.
\subsection{Navigating the space of $k$-realizations}
\begin{figure}[b]
\begin{center}
\includegraphics[width=5in,clip=true,trim=0 1.5in 0 1.5in]{FigEE.pdf}
\end{center}
\caption{\label{fig:swap}The operation $\swap{e}{e'}{u}{v}$.}
\end{figure}
Let $e$ and $e'$ be distinct edges in a $k$-graph $G$, and choose vertices $u\in e\setminus e'$ and $v \in e'\setminus e$. The operation $\swap{e}{e'}{u}{v}$ deletes the edges $e$ and $e'$ and adds the edges $e-u+v$ and $e'-v+u$ (where $e-u+v$ denotes the set $e-\{u\}\cup \{v\}$); see Figure~\ref{fig:swap}. Denote this family of edge exchanges by $\mathcal{Q}^*_k$.
Petersen \cite{Pet} showed that given any pair of realizations of a graphic sequence, one can be obtained from the other by a sequence of 2-switches. This result simply says that $G(\mathcal{S}_2(\pi), \mathcal{Q}^*_2)$ is connected. Kocay and Li \cite{KocayLi} proved a similar result for 3-graphs, namely that any pair of 3-graphs with the same degree sequence can be transformed into each other using edge exchanges from ${\mathcal Q}^*_3$. However, unlike in the graph case, intermediate hypergraphs obtained while applying edge exchanges from ${\mathcal Q}^*_3$ may have multiple edges. In other words, $G(\mathcal{M}_3(\pi), \mathcal{Q}^*_3)$ is connected.
We extend Kocay and Li's result to arbitrary $k \geq 3$.
\begin{theorem}\label{ConnSpace}
If $\pi$ is any sequence of nonnegative integers with a $k$-multihypergraph realization, then $G(\mathcal{M}_k(\pi), \mathcal{Q}^*_k)$ is connected.
\end{theorem}
\begin{proof}
%For any $H_1$ and $H_2$ in $G(\mathcal{M}_k(\pi), \mathcal{Q}^*_k)$, let $H_1\bigtriangleup H_2$ be the $k$-multigraph whose edge set is the symmetric difference of $E(H_1)$ and $E(H_2)$.
Suppose there exists a sequence $\pi$ with a $k$-multihypergraph realization for which $G(\mathcal{M}_k(\pi), \mathcal{Q}^*_k)$ is not connected.
For two $k$-multihypergraphs $H$ and $F$ in $G(\mathcal{M}_k(\pi), \mathcal{Q}^*_k)$, let $R(H,F)$ be the subgraph of $H$ with $E(R(H,F))=E(H)\setminus E(F)$ and $B(H, F)$ be the subgraph of $F$ with $E(B(H,F))=E(F)\setminus E(H)$.
Since $G(\mathcal{M}_k(\pi), \mathcal{Q}^*_k)$ is not connected, there are two $k$-multihypergraphs realizing $\pi$ that are in different components of this graph.
%For any such pair $H_1$ and $H_2$, let $R(H_1, H_2)$ be the subgraph of $H_1$ with $E(R(H_1,H_2))=E(H_1)\setminus E(H_2)$ and $B(H_1, H_2)$ be the subgraph of $H_2$ with $E(B(H_1,H_2))=E(H_2)\setminus E(H_1)$.
%choose two multihypergraphs $H_1$ and $H_2$ such that $|E(H_1) \bigtriangleup E(H_2)|$ is minimized.
%Let $R$ be the subgraph of $H_1$ such that $E(R)=E(H_1)\setminus E(H_2)$ and let $B$ be the subgraph of $H_2$ such that $E(B)=E(H_2)\setminus E(H_1)$.
%Subject to $|E(R\bigtriangleup B)|$ being minimized, choose edges $e_r \in E(R)$ and $e_b \in E(B)$ such that $e_r \neq e_b$ and $|e_r \cap e_b|$ is maximized.
%Among all $R$ and $B$ generated by pairs $H_1$ and $H_2$ that achieve the minimum value of $|E(H_1)\bigtriangleup E(H_2)|$,
Now, among all such pairs of $k$-multihypergraphs, choose the pair $H_1$ and $H_2$ that minimize $|E(H_1)\bigtriangleup E(H_2)|$, and subject to this, that maximize $|e_r \cap e_b|$ for edges $e_r\in E(R(H_1, H_2))$ and $e_b \in E(B(H_1,H_2))$.
Let $i = |e_r \cap e_b|$, and let $R=R(H_1,H_2)$ and $B=B(H_1,H_2)$.
We refer to the edges of $R$ as \emph{red} and the edges of $B$ as \emph{blue}.
Since $e_r \neq e_b$, there are vertices $u\in e_r\setminus e_b$ and $v\in e_b\setminus e_r$.
As $H_1$ and $H_2$ are realizations of $\pi$, $d_{H_1}(x)=d_{H_2}(x)$ for any vertex $x$.
Note, if we let $d_P(x)$ equal the number of edges incident to $x$ that appear in both $H_1$ and $H_2$, then $d_R(x)=d_{H_1}(x)-d_P(x)$ and $d_B(x)=d_{H_2}(x)-d_P(x)$.
Thus $d_R(x)=d_B(x)$, and we may assume without loss of generality that $d_B(u)\geq d_B(v)$;
otherwise $d_R(v)\geq d_R(u)$, and the roles of $u$ and $v$, and red and blue, may be switched in the remainder of the proof.
We claim that $u$ must be in some blue edge $e'$ such that $v \notin e'$ and such that $ e' + v - u$ is not a blue edge.
Note that $e'_b = e_b + u - v$ is not a blue edge, for otherwise $e_r$ and $e'_b$ are red and blue edges, respectively, and intersect in $i+1$ vertices.
Since $d_B(u)\geq d_B(v)$ and $v \in e_b$ while $u \notin e_b$, we know $u$ is in at least one blue edge that does not contain $v$.
If $e+v-u$ is a blue edge for every blue edge $e$ containing $u$ but not $v$, then $d_B(u)$ is less than $d_B(v)$, a contradiction.
Thus the edge $e'$ exists.
Now we apply $\swap{e'}{e_b}{u}{v}$ to $H_2$ to obtain the $k$-multihypergraph $H_2'$. Let $B'$ be the subgraph of $H_2'$ such that $E(B')=E(H_2')\setminus E(H_1)$.
Note that $H_2$ and $H_2'$ are adjacent in $G(\mathcal{M}_k(\pi), \mathcal{Q}^*_k)$, so $H_1$ and $H_2'$ must be in different components.
However, there is a red edge $e_r\in E(R)$ and a blue edge $e'_b\in E(B')$ that intersect in $i+1$ places.
If $i+1 < k$, this contradicts our choice of $H_1$ and $H_2$ maximizing edge intersections.
If $i+1=k$, then $e'_b = e_r$ and $|E(H_1)\bigtriangleup E(H_2')| < |E(H_1) \bigtriangleup E(H_2)|$, again contradicting our choice of $H_1$ and $H_2$.
\end{proof}
We have shown that for a $k$-graphic sequence $\pi$, there is a path between simple $k$-realizations of $\pi$ in $G(\mathcal{M}_k(\pi), \mathcal{Q}^*_k)$.
This path may go through multihypergraph realizations, unlike in the result of Petersen.
In the proof of Theorem \ref{ConnSpace}, we argue that $e_b+u-v$ and $e'+v-u$ are not blue edges, but either edge may still be an edge of $H_2$. Hence performing the edge exchange may in fact result in duplicating an edge of $H_2$.
It is unknown whether $G(\mathcal{S}_k(\pi),\mathcal{Q})$ is connected for some small collection $\mathcal{Q}$ of edge exchanges.
For a positive integer $i$, let $\mathcal{E}_i$ be the collection containing all $j$-switches for $j \leq i$.
Gabelman \cite{Gabelman} gave an example of a 3-graphic sequence $\pi$ whose simple realizations cannot be transformed into each other using only 2-switches, without creating multiple edges.
That is, $G(\mathcal{S}_3(\pi), \mathcal{E}_2)$ is not connected.
We extend his example to $k \geq 3$, which shows we cannot replace $\mathcal{M}_k$ with $\mathcal{S}_k$ in Theorem \ref{ConnSpace}.
\begin{proposition}\label{prop:MultiEx}
For each $k \geq 3$ there is a $k$-graphic sequence $\pi$ such that $G(\mathcal{S}_k(\pi), \mathcal{E}_{k-1})$ is not connected.
\end{proposition}
\begin{proof}
Consider the following matrix $A$ of real numbers:
\[ A=\left[\begin{matrix}
x_{1,1} & x_{1,2} & \dotso & x_{1,k-1} & -y_1 \\
x_{2,1} & x_{2,2} & \dotso & x_{2,k-1} & -y_2 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
x_{k-1,1} & x_{k-1,2} & \dotso & x_{k-1,k-1} & -y_{k-1} \\
-z_1& -z_2 & \dotso & -z_{k-1}& w
\end{matrix}\right] \]
where
\[
y_j=\sum_{i=1}^{k-1} x_{j,i},\qquad z_j=\sum_{i=1}^{k-1} x_{i,j},\qquad\text{ and }\qquad w=\sum_{i,j} x_{i,j}.
\]
We choose the terms $x_{i,j}$ so that if a set of $k$ entries of the matrix sums to zero, then those entries must be from a single row or column.
This can be done by choosing the $x_{i,j}$'s to be linearly independent over $\mathbb{Q}$, or by choosing them to be powers of some sufficiently small $\epsilon$.
We form a hypergraph $H$ on a set $V$ of $k^2$ vertices as follows: weight each vertex with a different entry of the matrix.
The edges of $H$ are the $k$-sets whose total weight is positive, and the $k$-sets corresponding to the rows of $A$. By construction of the matrix $A$, the only $k$-sets that have zero weight correspond to rows and columns. Thus the only $k$-sets that are non-edges either have negative weight or correspond to columns.
The degree sequence of $H$ is not uniquely realizable, as the $k$-switch that adds the $k$-sets corresponding to columns of $A$ to the edge set while removing the edges corresponding to rows gives another realization.
However, we show that we cannot apply an $i$-switch to $H$ for any $i c_1 \frac{\Delta^{k/(k-1)} }{\delta} + c_2 \Delta,
\end{equation}
where $\Delta$ and $\delta$ are the maximum and minimum entries of $\pi_1+\pi_2$, then $\pi_1$ and $\pi_2$ pack.
\end{theorem}
\begin{proof}
Among all $k$-realizations of $\pi_1$ and $\pi_2$, let $H_1$ and $H_2$ be $k$-realizations such that the number of double edges in $H_1 \cup H_2$ is minimized.
We may assume that $H_1 \cup H_2$ has at least one multiple edge, lest $H_1$ and $H_2$ give rise to a packing.
Let $H=H_1 \cup H_2$, $e=\{v_1,\dotsc,v_k\}$ be a double edge in $H$, and $I=V(H)\setminus \bigcup_{i=1}^k N_H(v_i)$.
Taking $c_2>k^2-k$, inequality \eqref{eq:thmbound} implies that $I \neq\emptyset$. Let $Q=N_H(I)$.
If there is some edge $f$ that contains more than one vertex of $I$, say $i_1$ and $i_2$, then the 2-switch $\swap{e}{f}{v_1}{i_1}$ reduces the number of double edges, contradicting the choice of $H_1$ and $H_2$. Hence, each edge including a vertex of $I$ consists of that vertex and $k-1$ vertices of $Q$.
Let $Q_i=N_{H_i}(I)$ for $i\in\{1,2\}$. Suppose $Q_1$ is not a clique in $H$.
That is, let $A=\{y_1, \ldots, y_k\}$ be a set of vertices in $Q_1$ that is not an edge in $H$.
Since each $y_j$ is in $Q_1$, for each $j$ with $ 1 \le j \le k$ there is an edge $f_j \in H_1$ that contains both $y_j$ and some vertex of $I$.
Let $\mathcal{E} = \{f_1, \ldots, f_k\}$ be a set of such edges in $H_1$, where it is possible that some $f_j$'s are equal.
Now we can repeatedly perform 2-switches of the form $\swap{e}{f_j}{v_j}{y_j}$ until one copy of $e$ is replaced by the new edge $\{y_1, \ldots, y_k\}$, in the following way.
First, do the exchange $S_1 = \swap{e}{f_1}{v_1}{y_1}$ to obtain edges $e_1 = e-v_1+y_1$ and $f_1'= f_1-y_1+v_1$.
The edge $e_1$ may already exist in $H$, but it will be removed in the next step.
The edge $f_1'$ cannot exist in $H$, as it contains both a vertex of $e$ and a vertex of $I$.
Having performed edge exchanges $S_1$ through $S_j$, the next exchange is $S_{j+1} = \swap{e_{j+1}}{f_{j+1}}{v_{j+1}}{y_{j+1}}$, unless $f_{j+1} = f_p$ for some $p \leq j$.
In that case, $f_{j+1}=f_p$ is no longer an edge, but has been transformed into the edge $f_p'=f_p-y_p+v_p$.
Then $S_{j+1}= \swap{e_{j+1}}{f_p'}{v_{j+1}}{y_{j+1}}$, and the new edges created in this exchange are $e_{j+1}= e_j-v_j+y_j$ and $f_j'=f_p'-y_j+v_j$.
After the $k^{\text{th}}$ iteration of this process, we have created the edge consisting of the vertices in $A$, and removed one of the copies of $e$, while no new double edges have been created.
Since this contradicts our choice of $H_1$ and $H_2$, the vertices of $A$ must already form an edge, so $Q_1$ is a clique.
The same argument shows that $Q_2$ is a clique.
Let $v_i\in e$ and $x\in Q$, and suppose that $e-v_i+x$ is not an edge in $H$.
Let $f$ be an edge containing $x$ and a vertex of $I$.
Then the switch $\swap{e}{f}{v_i}{x}$ reduces the number of double edges in $H$.
Hence every vertex of $Q$ is in an edge with each of the $(k-1)$-subsets of $e$.
Let $q = |Q|$ and $r = |E(H[Q])| $.
Since $Q_1$ and $Q_2$ are cliques, $r \geq 2\binom{q/2}{k}$.
Counting the degrees of vertices in $Q$, we have
\begin{align*}
\Delta q &\geq k q + (k-1)\delta |I| + k r\\
&\geq kq + (k-1)\delta |I| + 2k\binom{q/2}{k}.
\end{align*}
Rearranging gives
\begin{equation}\label{Iupper}
|I| \leq \frac{(\Delta-k)q - 2k\binom{q/2}{k} }{(k-1)\delta}.
\end{equation}
By the principle of inclusion-exclusion, we also know that
\begin{align}\label{inclexcl}
|I| &= n - \left| \bigcup_{i=1}^{k} N_H(v_i) \right| \\
&= n + \sum_{s=1}^k (-1)^s \sum_{\substack{B\subseteq e\\ |B|=s}} \left| \bigcap_{v\in B} N_H(v) \right|. \notag
\end{align}
For any subset $B$ of $e$, we have that all of $Q$ and $e\setminus B$ are in the common neighborhood of $B$ in $H$; thus
\[ q+k-|B| \leq \left| \bigcap_{v\in B} N_H(v) \right|. \]
On the other hand, the size of this common neighborhood is maximized when all vertices in $B$ have the same neighborhood; hence
\[ \left| \bigcap_{v\in B} N_H(v) \right| \leq (k-1)(\Delta-2)+k-|B|. \]
Using these inequalities in (\ref{inclexcl}), we have
\begin{align*}
|I| &\geq n - \sum_{s\text{ odd}} \binom{k}{s} \left( (k-1)(\Delta-2) + k-s\right) + \sum_{s\text{ even}} \binom{k}{s} (q+k-s) \\
&= n + \sum_{s=1}^k (-1)^s (k-s) \binom{k}{s} - (k-1)(\Delta-2)\sum_{s\text{ odd}} \binom{k}{s} + q \sum_{s\text{ even}} \binom{k}{s}.
\end{align*}
Applying the binomial theorem, this becomes
\begin{align}\label{Ilower}
|I| &\geq n - k - (\Delta-2)(k-1)\left(2^{k-1}\right) + q\left(2^{k-1}-1\right) \\
&= n - \Delta(k-1)\left(2^{k-1}\right) + q\left( 2^{k-1} - 1\right) + (k-1)\left( 2^k - 1 \right) - 1. \notag
\end{align}
Combining equations (\ref{Iupper}) and (\ref{Ilower}) yields
\begin{gather}
(k-1)\delta \Big( n - \Delta(k-1)\left(2^{k-1}\right) + (k-1)\left(2^k-1\right) - 1 \Big) \notag \\
\leq (\Delta-k) q - (k-1)\delta\left(2^{k-1}-1\right) q - 2k\binom{q/2}{k} \label{lastinequality} \\
\leq \Delta q - 2k \frac{ q^k}{(2k)^k}.\notag
\end{gather}
Without loss of generality, suppose $|Q_1| \ge |Q_2|$, and let $q_1= |Q_1|$. Since $Q_1$ is a clique, $\binom{q_1-1}{k-1} \le \Delta$, so $q_1 \leq c'\Delta^{1/(k-1)}$ for some constant $c'$ depending only on $k$.
Then, since $Q=Q_1 \cup Q_2$, we have $q\leq 2q_1 \leq 2c'\Delta^{1/(k-1)}=c\Delta^{1/(1-k)}$.
Inequality \eqref{lastinequality} now becomes
\begin{align*}
n \leq \left( c - \frac{c^k}{(2k)^{k-1}} \right) \frac{\Delta^{k/(k-1)}}{\delta} + \left( (k-1)2^{k-1} \right) \Delta.
\end{align*}
This establishes the theorem, with $c_1 =\left( c - \frac{c^k}{(2k)^{k-1}} \right)$ and $c_2 = \left( (k-1)2^{k-1} \right)$.
\end{proof}
When $\delta=o\left(\Delta^{1/(k-1)}\right)$, the bound in Theorem \ref{packing} reduces to
\[
n > c \frac{\Delta^{k/(k-1)} }{\delta}
\]
for $c = c_1+c_2$.
We show that for $\delta$ in this range, Theorem \ref{packing} is best possible up to the choice of $c$.
Fix $k$ and $\delta$ and choose an integer $x\gg\delta$ such that $ \frac{x-k}{\delta (k-1)}$ is an integer.
Form a complete $k$-graph on $x$ vertices; set aside $k$ of these vertices to form the set $B$, and let $T$ be the set of remaining vertices.
Add an independent set $I$ of order
\[
\frac{(x-k)}{ \rho (k-1)\delta} \binom{x-1}{k-1} ,
\]
where $\rho >1$ is chosen such that $\frac{1}{\rho}\binom{x-1}{k-1}$ is an integer.
Partition $T$ into sets $T_1, \ldots, T_r$, each of size $\delta (k-1)$, where $r = \frac{x-k}{\delta (k-1)}$, and partition $I$ into sets $I_1, \ldots, I_r$ of size $\frac{1}{\rho}\binom{x-1}{k-1}$.
For each vertex $v \in I_j$, create edges $e_1, \ldots, e_{\delta}$, where each edge consists of $v$ and $k-1$ distinct vertices of $T_j$.
Thus, $N(v)=T_j$ and each vertex in $T_j$ is in exactly one edge with each vertex of $I_j$.
Finally, add an independent set of size $x-k+|I|$.
We now have a $k$-graph $H$ where each vertex in $T$ has degree
\[
\binom{x-1}{k-1} + \frac{1}{\rho}\binom{x-1}{k-1}
= \left( 1 + \frac{1}{\rho} \right) \binom{x-1}{k-1},\]
each vertex in $B$ has degree $\binom{x-1}{k-1}$, and each vertex in $I$ has degree $\delta$.
Consider two orderings of the degree sequence of $H$:
\begin{align*}
\pi_1 &= \left( \binom{x-1}{k-1}^k, \left(\left(1+\frac{1}{\rho}\right)\binom{x-1}{k-1}\right)^{x-k}, 0^{x-k}, \delta^{|I|}, 0^{|I|}\right) \\
\pi_2 &= \left( \binom{x-1}{k-1}^k, 0^{x-k}, \left(\left(1+\frac{1}{\rho}\right)\binom{x-1}{k-1}\right)^{x-k}, 0^{|I|}, \delta^{|I|}\right).
\end{align*}
Note that $n$, the length of sequences $\pi_1$ and $\pi_2$, is
\begin{align*}
n &= 2x -k+ 2|I| \\
&= 2x-k + \frac{2(x-k)}{ \rho (k-1)\delta} \binom{x-1}{k-1} \\
& = \Theta(x^k/\delta).
\end{align*}
In $\pi_1+\pi_2$ the minimum degree is $\delta$ and the maximum degree is $\Delta = 2\binom{x-1}{k-1} = \Theta(x^{k-1})$.
Hence $\Delta = \Theta((\delta n)^{(k-1)/k})$.
In any realization of $\pi_1$, Lemma \ref{initialcliquelem} implies that the vertices of degree greater than $\delta$ must form a clique. Since the $k$ vertices of $B$ must be in this clique, those vertices must form an edge in any realization of $\pi_1$. The same argument applies to $\pi_2$, hence the sequences do not pack.
%\section*{Acknowledgements}
\bibliographystyle{abbrv}
%\bibliography{HypergraphicSequences}
\begin{thebibliography}{10}
\bibitem{AAS}
N.~Achuthan, N.~Achuthan, and M.~Simanihuruk.
\newblock On {$3$}-uniform hypergraphic sequences.
\newblock {\em J. Combin. Math. Combin. Comput.}, 14:3--13, 1993.
\bibitem{AigTriesch}
M.~Aigner and E.~Triesch.
\newblock Realizability and uniqueness in graphs.
\newblock {\em Discrete Math.}, 136(1-3):3--20, 1994.
\newblock Trends in discrete mathematics.
\bibitem{BHJW}
M.~Barrus, S.~Hartke, K.~Jao, and D.~West.
\newblock Length thresholds for graphic lists given fixed largest and smallest
entries and bounded gaps.
\newblock {\em Discrete Math.}, 312(9):1494--1501, 2012.
\bibitem{BHK}
M.~Barrus, S.~Hartke, and M.~Kumbhat.
\newblock Graph classes characterized both by forbidden subgraphs and degree
sequences.
\newblock {\em J. Graph Theory}, 57(2):131--148, 2008.
\bibitem{BBHKS}
D.~Bauer, H.~Broersma, J.~van~den Heuvel, N.~Kahl, and E.~Schmeichel.
\newblock Toughness and vertex degrees.
\newblock {\em J. Graph Theory}, 2012.
\newblock doi: 10.1002/jgt.21639.
\bibitem{BBD}
N.~Bhave, B.~Bam, and C.~Deshpande.
\newblock A characterization of degree sequences of linear hypergraphs.
\newblock {\em J. Indian Math. Soc. (N.S.)}, 75(1-4):151--160 (2009), 2008.
\bibitem{Bill88}
D.~Billington.
\newblock Conditions for degree sequences to be realizable by 3-uniform
hypergraphs.
\newblock {\em J. Combin. Math. Combin. Comput.}, 3:71--91, 1988.
\bibitem{BFHJKW}
A.~Busch, M.~Ferrara, S.~Hartke, M.~Jacobson, H.~Kaul, and D.~West.
\newblock Packing of graphic {$n$}-tuples.
\newblock {\em J. Graph Theory}, 70(1):29--39, 2012.
\bibitem{Chen}
Y.~C. Chen.
\newblock A short proof of {K}undu's {$k$}-factor theorem.
\newblock {\em Discrete Math.}, 71(2):177--179, 1988.
\bibitem{Choudum}
S.~Choudum.
\newblock On graphic and {$3$}-hypergraphic sequences.
\newblock {\em Discrete Math.}, 87(1):91--95, 1991.
\bibitem{CKS}
C.~Colbourn, W.~Kocay, and D.~Stinson.
\newblock Some {NP}-complete problems for hypergraph degree sequences.
\newblock {\em Discrete Appl. Math.}, 14(3):239--254, 1986.
\bibitem{Dew}
A.~Dewdney.
\newblock Degree sequences in complexes and hypergraphs.
\newblock {\em Proc. Amer. Math. Soc.}, 53(2):535--540, 1975.
\bibitem{DGM}
C.~D{\"u}rr, F.~Gui{\~n}ez, and M.~Matamala.
\newblock Reconstructing 3-colored grids from horizontal and vertical
projections is {NP}-hard.
\newblock In {\em Algorithms---{ESA} 2009}, volume 5757 of {\em Lecture Notes
in Comput. Sci.}, pages 776--787. Springer, Berlin, 2009.
\bibitem{DR}
A.~Duval and V.~Reiner.
\newblock Shifted simplicial complexes are {L}aplacian integral.
\newblock {\em Trans. Amer. Math. Soc.}, 354(11):4313--4344 (electronic), 2002.
\bibitem{ErdGal}
P.~Erd\H{o}s and T.~Gallai.
\newblock Graphs with prescribed degrees of vertices (hungarian).
\newblock {\em Mat. Lapok}, 11:264--274, 1960.
\bibitem{FLMW12}
M.~Ferrara, T.~LeSaulnier, C.~Moffatt, and P.~Wenger.
\newblock On the sum necessary to ensure a degree sequence is potentially
{$H$}-graphic.
\newblock {\em Arxiv preprint arXiv:1203.4611}, 2012.
\bibitem{FHM}
D.~Fulkerson, A.~Hoffman, and M.~McAndrew.
\newblock Some properties of graphs with multiple edges.
\newblock {\em Canad. J. Math.}, 17:166--177, 1965.
\bibitem{Gabelman}
I.~Gabelman.
\newblock {\em The functional behavior of majority (threshold) elements}.
\newblock PhD thesis, Syracuse U, 1961.
\bibitem{Hak}
S.~Hakimi.
\newblock On realizability of a set of integers as degrees of the vertices of a
linear graph. {I}.
\newblock {\em J. Soc. Indust. Appl. Math.}, 10:496--506, 1962.
\bibitem{Hav}
V.~Havel.
\newblock A remark on the existence of finite graphs (czech).
\newblock {\em \v Casopis P\v est. Mat.}, 80:477--480, 1955.
\bibitem{SH}
H.~Hoogeveen and G.~Sierksma.
\newblock Seven criteria for integer sequences being graphic.
\newblock {\em J. Graph Theory}, 15:223--231, 1991.
\bibitem{KR}
C.~Klivans and V.~Reiner.
\newblock Shifted set families, degree sequences, and plethysm.
\newblock {\em Electron. J. Combin.}, 15(1):Research Paper 14, 35, 2008.
\bibitem{KocayLi}
W.~Kocay and P.~C. Li.
\newblock On 3-hypergraphs with equal degree sequences.
\newblock {\em Ars Combin.}, 82:145--157, 2007.
\bibitem{KSH}
A.~Kostochka, C.~Stocker, and P.~Hamburger.
\newblock A hypergraph version of a graph packing theorem by bollob{\'a}s and
eldridge.
\newblock {\em J. Graph Theory}, 2012.
\newblock doi: 10.1002/jgt.21706.
\bibitem{Pet} J.~Petersen. Die Theorie der regularen Graphen, {\it Acta Math.} {\bf15} (1891),193-220.
\bibitem{PW07}
M.~Pil{\'s}niak and M.~Wo{\'z}niak.
\newblock A note on packing of two copies of a hypergraph.
\newblock {\em Discuss. Math. Graph Theory}, 27(1):45--49, 2007.
\bibitem{PW11}
M.~Pil{\'s}niak and M.~Wo{\'z}niak.
\newblock On packing of two copies of a hypergraph.
\newblock {\em Discrete Math. Theor. Comput. Sci.}, 13(3):67--74, 2011.
\bibitem{West}
D.~West.
\newblock {\em Introduction to Graph Theory}.
\newblock Prentice Hall, Inc., Upper Saddle River, NJ, second edition, 2001.
\bibitem{YinLi}
J.-H. Yin and J.-S. Li.
\newblock Two sufficient conditions for a graphic sequence to have a
realization with prescribed clique size.
\newblock {\em Disc. Math.}, 301:218--227, 2005.
\bibitem{ZZ}
I.~Zverovich and V.~Zverovich.
\newblock Contributions to the theory of graphic sequences.
\newblock {\em Discrete Math.}, 105(1-3):293--303, 1992.
\end{thebibliography}
\end{document}