\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}