Hypergraphic Sequences (2012)

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.