\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<k$.  

Note that in any edge exchange that replaces a set $F_1$ of edges with a set $F_2$ of nonedges,
$$\sum_{e\in F_1}\sum_{v\in e}wt(v)=\sum_{v\in V}(\textrm{deg}_{F_1}(v))wt(v)=\sum_{v\in V}(\textrm{deg}_{F_2}(v))wt(v)=\sum_{e\in F_2}\sum_{v\in e}wt(v).$$
Since edges of $F_1$ have nonnegative weight and nonedges of $F_2$ have nonpositive weight, we conclude that the edges of $F_1$ must have zero weight and thus correspond to rows of $A$, and the nonedges of $F_2$ have zero weight and correspond to columns of $A$.
But no proper subset of edges corresponding to rows can be swapped for a proper subset of nonedges corresponding to columns, because this does not maintain the degree of every vertex. 
\end{proof}

This result immediately suggests the following problem:
\begin{question}\label{MinFam}
Determine the smallest cardinality of a collection $\mathcal{Q}$ such that $G(\mathcal{S}_k(\pi), \mathcal{Q})$ is connected for every $k$-graphic sequence $\pi$. 
\end{question}
Results for graphs suggest several different possible approaches.
Is there a finite collection that works?
Would it be sufficient to add all possible $k$-switches?
Or would it suffice to add just the $k$-switch suggested by Proposition \ref{prop:MultiEx} to $\mathcal{E}_{k-1}$? 


\subsection{Applications}
\subsubsection{Obtaining a ``good'' realization}
One consequence of the Havel-Hakimi characterization of 2-graphic sequences is that any graphic sequence has a realization in which a specified vertex $v$ is adjacent to vertices whose degrees are the highest-degree vertices in the graph. 
This elementary fact has been proved in several places, for instance \cite{FHM}.
Motivated by this, we prove the following.  

\begin{theorem}\label{HighDeg}
Let $\pi=(d_1, \ldots, d_n)$ be a nonincreasing $k$-graphic sequence, and let $H$ be a $k$-realization of $\pi$ on vertices $\{v_1, \ldots, v_n\}$ such that $d(v_i)=d_i$ for each $i, 1\leq i \leq n$. Let $i < j$ and suppose there is an edge $e$ in $H$ such that $v_j$ is in $e$ but $v_i$ is not in $e$. Then there is a realization $H'$ of $\pi$ such that $e-v_j+v_i$ is an edge in $H'$.
\end{theorem}
\begin{proof}
If $e-v_j+v_i$ is already an edge in $H$, we are done. So we can assume this edge does not exist. Since $d_i \geq d_j$, there is an edge $f$ such that $v_i$ is in $f$ but $v_j$ is not. Additionally, some such $f$ has the property that $f-v_i+v_j$ is not an edge in $H$. Perform the exchange $\swap{e}{f}{v_j}{v_i}$. This does not create any multi-edges, so we have the desired realization. 
\end{proof}

An immediate corollary of this result is that for any vertex $v$ of positive degree, there is a $k$-realization of $\pi$ such that $v$ is in an edge with the $k-1$ remaining vertices of highest degree.
Thus, there is always a realization of $\pi$ in which the $k$ vertices of highest degree are in a single edge. 
If we could prove the existence of a $k$-realization in which the link of a vertex contains only the highest degree vertices, then we would be able to obtain a Havel-Hakimi-type characterization of $k$-graphic sequences. 

\subsubsection{Packing $k$-graphic sequences}
Two $n$-vertex graphs $G_1$ and $G_2$ {\it pack} if they can be expressed as edge-disjoint subgraphs of the complete graph $K_n$. 
Kostochka, Stocker, and Hamburger \cite{KSH}, and Pil\'{s}niak and Wo\'{z}niak \cite{PW07, PW11} recently studied packing of hypergraphs.
Busch et al. \cite{BFHJKW} extended the idea of graph packing to graphic sequences.
We utilize edge exchanges to examine related questions for hypergraphic sequences. 

Let $\pi_1$ and $\pi_2$ be $k$-graphic sequences with $\pi_1 = (d_1^{(1)}, \dots, d_n^{(1)})$ and $\pi_2 = (d_1^{(2)}, \dots, d_n^{(2)})$. 
We say that $\pi_1$ and $\pi_2$ {\it pack} if there exist edge-disjoint $k$-graphs $G_1$ and $G_2$ on vertex set $\{v_1, \ldots, v_n\}$ such that $d_{G_1}(v_i)=d_i^{(1)}$ and $d_{G_2}(v_i)=d_i^{(2)}$ for all $i$. 
When we discuss packing of graphic sequences, the sequences need not be nonincreasing; however, no reordering of the indices is allowed. 

D\"{u}rr, Gui\~{n}ez, and Matamala \cite{DGM} showed that the problem of packing two graphic sequences is NP-complete, and we show that the same conclusion holds when considering $k$-graphic sequences for $k\geq 3$. 

\begin{theorem}\label{PackingNP}
The degree-sequence packing problem for $k$-graphs is NP-complete for all $k \geq 2$.
\end{theorem}
\begin{proof}
The degree-sequence packing problem for $k\geq 2$ is in NP since the certificate giving realizations that pack can easily be checked in polynomial time.  
NP-hardness for $k=2$ is shown in \cite{DGM}.  
For $k\geq 3$ we show that any instance of the degree-sequence packing problem for 2-graphs can be reduced to an instance of the degree-sequence packing problem for $k$-graphs.  
Given 2-graphic sequences $\pi_1$ and $\pi_2$, add $k-2$ new entries to each sequence to create sequences $\pi_1^k$ and $\pi_2^k$, with each new entry of $\pi_i^k$ equal to $\frac{1}{2}\sigma(\pi_i)$.
Then, any $k$-realization of $\pi_i^k$ has the same number of edges as a 2-realization of $\pi_i$, and each of the $k-2$ vertices associated with the new entries must appear in every edge. 
 Hence there is a one-to-one correspondence between 2-realizations of the original sequences and $k$-realizations of the new sequences. 
\end{proof}

Given the computational complexity of the overarching problem, it is natural to seek sufficient conditions that ensure a pair of $k$-graphic sequences pack.
Busch et al.\ showed that if $\pi_1$ and $\pi_2$ are graphic sequences and $\Delta \le \sqrt{2\delta n}-(\delta-1)$, where $\Delta$ and $\delta$ are the largest and smallest entries in $\pi_1+\pi_2$, then $\pi_1$ and $\pi_2$ pack.  
We prove a similar result for $k$-graphic sequences when $k \geq 3$.

For a vertex $v$ in a $k$-graph $H$, we define the neighborhood of $v$, $N_H(v)$, to be the set of vertices that are in at least one edge with $v$. Similarly, for a set $S=\{v_1, \ldots, v_m\}$ of vertices in $H$, the neighborhood of $S$ is $N_H(S)= \cup_{i=1}^m N_H(v_i)$. When $H$ is understood, we write $N(v)$. Also, let $H[S]$ denote the subgraph of $H$ induced by the vertices in $S$.




\begin{theorem}\label{packing}
Fix an integer $k\geq 2$.  There exist constants $c_1, c_2$ (depending only on $k$) such that if $\pi_1$ and $\pi_2$ are $k$-graphic sequences each with length $n$ that satisfy
\begin{equation}\label{eq:thmbound}
n > 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}