Isomorphism for random k-uniform hypergraphs

DOI10.1016/J.IPL.2020.106039MaRDI QIDQ2224850zbMATH OpenOpenAlexFDO

Authors Debsoumya Chakraborti, Simi Haber, Mihir Hasabnis, Alan Frieze

Publication date 4 February 2021

Published in Information Processing Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2002.06953

zbMATH Keywords

analysis of algorithmsisomorphismrandom hypergraph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25)

Abstract: We study the isomorphism problem for random hypergraphs. We show that it is solvable in polynomial time for the binomial random $k$-uniform hypergraph $H_{n,p;k}$, for a wide range of $p$. We also show that it is solvable w.h.p. for random $r$-regular, $k$-uniform hypergraphs $H_{n,r;k},r=O(1)$.

Recommendations

• Approximating Independent Set and Coloring in Random Uniform Hypergraphs
• On the chromatic number of a random hypergraph
• Ramsey Properties of Random k-Partite, k-Uniform Hypergraphs
• Recognizing random intersection graphs
• Isomorphy up to complementation

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Distinguishing Vertices of Random Graphs
• scientific article; zbMATH DE number 3575633 (Why is no real title available?)
• Improved random graph isomorphism
• Perfect Matchings in Random r-regular, s-uniform Hypergraphs
• Random Graph Isomorphism

This page was built for publication: Isomorphism for random \(k\)-uniform hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2224850)