**Originator: Michael Ferrara**
(presented by Mike Ferrara - REGS 2012)

**Background and Definitions:** We will call $n$-tuples of integers
*sequences*. All sequences considered here are nonincreasing.
A nonnegative integer sequence $\pi$ is $k$-*graphic* if it is the
sequence of vertex degrees of a $k$-uniform hypergraph $H$. In this case, we
say that $H$ *$k$-realizes* $\pi$ or is a *$k$-realization* of
$\pi$. (A *hypergraph* $H$ consists of a set $V(H)$ of vertices and a set
$E(H)$ of subsets of $V(H)$ called *edges*. A hypergraph is
*$k$-uniform* if every edge has size $k$. The *degree* of a vertex
in a hypergraph is the number of edges containing it.)

**Problem 1:** Find a good characterization of the nonnegative integer
sequences that are $k$-graphic.

**Comments:** In general it is not known whether this problem is
polynomial or NP-complete. Dewdney [D] (1975) gave a Havel-Hakimi type
characterization containing an existence clause that precludes conversion into
an efficient algorithm.

A graph is just a $2$-uniform hypergraph. A *$2$-switch* in a graph
yields a graph with the same degree sequence by replacing one $2$-edge
matching on four vertices with another consisting of edges that were absent.
Given realizations $G_1$ and $G_2$ of a 2-graphic sequence, Fulkerson, Hoffman
and McAndrew [FHM] proved that it is possible to transform $G_1$ into $G_2$ via
2-switches. Kocay and Li [KL] give a related set of operations on five or six
vertices that can be used to transform one 3-realization of a 3-graphic
sequence into another.

**Problem 2:** For $k\ge 4$, determine whether there exists a function
$f(k)$ and a set of operations, each on at most $f(k)$ vertices, that can be
used to transform one $k$-realization of a $k$-graphic sequence into
another.

**Definition:**
Given a $k$-uniform hypergraph $H$, a $k$-graphic sequence $\pi$ is
*potentially $H$-graphic* if there is some $k$-realization of $\pi$
that contains $H$ as a subgraph.

**Problem 3:** Given a $k$-uniform hypergraph $H$ and a positive integer
$n$, find the least integer $\sigma_k(H,n)$ such that every $n$-term
$k$-graphic sequence with sum at least $\sigma_k(H,n)$ is potentially
$H$-graphic.

**Comment:**
For $k=2$, this problem was posed by Erdős, Jacobson, and Lehel [EJL].
There are many results on it for specific choices of $H$ (See [FS] for
references). Ferrara, LeSaulnier, Moffatt, and Wenger [FLMW] have determined
the asymptotic value of $\sigma_2(H,n)$ for arbitrary $H$.

**References:**

[D] A.K. Dewdney, Degree seqences in complexes and hypergraphs,
*Proc. Amer. Math. Soc.* **53** (1975), 535-540.

[EJL] P. Erdős, M. Jacobson and J. Lehel, Graphs Realizing the Same Degree
Sequence and their Respective Clique Numbers,
*Graph Theory, Combinatorics and Applications* (eds. Alavi, Chartrand, Oellerman and Schwenk), Vol. I, 1991, 439-449.

[FLMW] M. Ferrara, T. LeSaulnier, C. Moffatt and P. Wenger,
On
the sum necessary to ensure a degree sequence is potentially $H$-graphic,
submitted.

[FS] M. Ferrara and J. Schmitt, A General Lower Bound for Potentially
*H*-Graphic Sequences, *SIAM J. Discrete Math.* **23** (2009),
517-526.

[FHM] D. Fulkerson, A. Hoffman, and M. McAndrew, Some properties of graphs with
multiple edges. *Canad. J. Math.* **17** (1965) 166-177.

[KL] W.L.Kocay, P.C. Li, On 3-Hypergraphs with Equal Degree Sequences,
*Ars Comb.* **82** (2007), 145-157.