Discrepancy of random graphs and hypergraphs

DOI10.1002/RSA.20522MaRDI QIDQ3192376zbMATH OpenOpenAlexFDO

Authors Jie Ma, Humberto Naves, Benny Sudakov

Publication date 12 October 2015

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

discrepancysimilarity of graphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Answering in a strong form a question posed by Bollob'as and Scott, in this paper we determine the discrepancy between two random k-uniform hypergraphs, up to a constant factor depending solely on k.

Recommendations

• Discrepancy in graphs and hypergraphs
• Quasi-random hypergraphs revisited
• On small \(n\)-uniform hypergraphs with positive discrepancy
• scientific article; zbMATH DE number 1512675
• The smallest n-uniform hypergraph with positive discrepancy

Cites work

• Cutting a graph into two dissimilar halves
• Imbalances in k‐colorations
• Intersections of graphs
• Quasi-random graphs
• Self-similarity of graphs

Cited in

(6)

• The smallest n-uniform hypergraph with positive discrepancy
• Random hypergraph irregularity
• Discrepancy properties for random regular digraphs
• scientific article; zbMATH DE number 1506506 (Why is no real title available?)
• Discrepancy in graphs and hypergraphs
• The Phase Transition of Discrepancy in Random Hypergraphs

This page was built for publication: Discrepancy of random graphs and hypergraphs

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