Isomorphisms between random graphs

DOI10.1016/J.JCTB.2023.01.001OpenAlexW3189350985MaRDI QIDQ2692783FDOQ2692783

Sourav Chatterjee, Persi Diaconis

Publication date: 23 March 2023

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

concentration inequalityrandom graphgraph isomorphism

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The random graph
• Cliques in random graphs
• Asymptotically optimal induced universal graphs
• Subgraph isomorphism, matching relational structures and maximal cliques
• Non-concentration of the chromatic number of a random graph
• Self-similarity of graphs
• Complexity and randomness in the Heisenberg groups (and beyond)
• When Subgraph Isomorphism is Really Hard, and Why This Matters for Graph Databases

Cited In (2)

• An algorithm for optimal isomorphism between two random graphs
• Isomorphisms between random graphs

This page was built for publication: Isomorphisms between random graphs

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