The Phase Transition of Discrepancy in Random Hypergraphs

DOI10.1137/21m1451427arXiv2102.07342OpenAlexW3129315305MaRDI QIDQ6046817

Unnamed Author, Calum MacRury, Xavier Pérez-Giménez, Tomáš Masařík

Publication date: 6 September 2023

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

discrepancyrandom hypergraphsBeck-Fiala conjecturepartial colorings

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Hypergraphs (05C65) Randomized algorithms (68W20)

Related Items (1)

Critical window of the symmetric perceptron

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improvement of convergence rate estimates in the Lyapunov theorem
• ``Integer-making theorems
• Deterministic discrepancy minimization via the multiplicative weight update method
• A panorama of discrepancy theory
• Introduction to Random Graphs
• Collision-Free Hashing from Lattice Problems
• Constructive Discrepancy Minimization by Walking on the Edges
• An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound
• On the discrepancy of random matrices with many columns
• On the discrepancy of random low degree set systems
• On the Beck‐Fiala conjecture for random set systems
• A Fourier-Analytic Approach for the Discrepancy of Random Set Systems
• An Improvement of the Beck–Fiala Theorem
• An Approximation to the Probability Integral
• Geometric discrepancy. An illustrated guide
• The discrepancy of random rectangular matrices

This page was built for publication: The Phase Transition of Discrepancy in Random Hypergraphs