EUVIMEDEUVIMED entdecken
Crossref

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

Nicholas Christo, Marcus Michelen

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →