Realizability of hypergraphs and high-dimensional contingency tables with random degrees and marginals

Abstract A result of Deza, Levin, Meesum, and Onn shows that the problem of deciding if a given sequence of nonnegative integers is the degree sequence of a 3-uniform hypergraph is NP complete. We tackle this problem in the random case and show that a random integer partition can be realized as the degree sequence of a $3$-uniform hypergraph with high probability. These results are in stark contrast with the case of graphs, where a classical result of Erdős and Gallai provides an efficient algorithm for checking if a sequence is a degree sequence of a graph and a result of Pittel shows that with high probability a random partition is not the degree sequence of a graph. By the same method, we address analogous realizability problems about high-dimensional binary contingency tables. We prove that if $(\lambda ,\mu ,\nu )$ are three independent random partitions then with high probability one can construct a three-dimensional binary contingency table with marginals $(\lambda ,\mu ,\nu )$. Conversely, if one insists that the contingency table forms a pyramid shape, then we show that with high probability one cannot construct such a contingency table. These two results confirm two conjectures of Pak and Panova.