Realizability of hypergraphs and high-dimensional contingency tables with random degrees and marginals
International Mathematics Research Notices · 24.08.2026 · 2026 (16)
DOI: 10.1093/imrn/rnag177 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Mathematics Research Notices, online erschienen am 20.08.2026. Verfasst von Nicholas Christo und 1 weiteren Autor:innen. Die Arbeit nennt 28 Literaturangaben. Gefördert von: NSF CAREER.
Abstract (Originalsprache)
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.
Förderung
- NSF CAREER
Zitieren
APA
Christo, N., & Michelen, M. (2026). Realizability of hypergraphs and high-dimensional contingency tables with random degrees and marginals. International Mathematics Research Notices, 2026(16). https://doi.org/10.1093/imrn/rnag177
Vancouver
Christo N, Michelen M. Realizability of hypergraphs and high-dimensional contingency tables with random degrees and marginals. International Mathematics Research Notices. 2026;2026(16). doi:10.1093/imrn/rnag177
BibTeX
@article{Christo2026,
author = {Christo, Nicholas and Michelen, Marcus},
title = {Realizability of hypergraphs and high-dimensional contingency tables with random degrees and marginals},
journal = {International Mathematics Research Notices},
year = {2026},
volume = {2026},
number = {16},
doi = {10.1093/imrn/rnag177}
}
EUVIMED