The Phase Transition of Discrepancy in Random Hypergraphs

DOI10.1137/21M1451427MaRDI QIDQ6046817zbMATH OpenOpenAlexFDO

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

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

Beck-Fiala conjecture discrepancy partial colorings random hypergraphs

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

Abstract: Motivated by the Beck-Fiala conjecture, we study the discrepancy problem in two related models of random hypergraphs on

n

vertices and

m

edges. In the first (edge-independent) model, a random hypergraph

H_{1}

is constructed by fixing a parameter

p

and allowing each of the

n

vertices to join each of the

m

edges independently with probability

p

. In the parameter range in which

p n i g h t a r r o w i n f t y

and

p m i g h t a r r o w i n f t y

, we show that with high probability (w.h.p.)

H_{1}

has discrepancy at least

O m e g a (2^{- n / m} s q r t p n)

when

m = O (n)

, and at least

O m e g a (s q r t p n l o g g a m m a)

when

m g g n

, where

g a m m a = m i n m / n, p n

. In the second (edge-dependent) model,

d

is fixed and each vertex of

H_{2}

independently joins exactly

d

edges uniformly at random. We obtain analogous results for this model by generalizing the techniques used for the edge-independent model with

p = d / m

. Namely, for

d i g h t a r r o w i n f t y

and

d n / m i g h t a r r o w i n f t y

, we prove that w.h.p.

H_{2}

has discrepancy at least

O m e g a (2^{- n / m} s q r t d n / m)

when

m = O (n)

, and at least

O m e g a (s q r t (d n / m) l o g g a m m a)

when

m g g n

, where

g a m m a = m i n m / n, d n / m

. Furthermore, we obtain nearly matching asymptotic upper bounds on the discrepancy in both models (when

p = d / m

), in the dense regime of

m g g n

. Specifically, we apply the partial colouring lemma of Lovett and Meka to show that w.h.p.

H_{1}

and

H_{2}

each have discrepancy

O (s q r t d n / m l o g (m / n))

, provided

d i g h t a r r o w i n f t y

,

d n / m i g h t a r r o w i n f t y

and

m g g n

. This result is algorithmic, and together with the work of Bansal and Meka characterizes how the discrepancy of each random hypergraph model transitions from

T h e t a (s q r t d)

to

o (s q r t d)

as

m

varies from

m = T h e t a (n)

to

m g g n

.

Recommendations

Cites work

Cited in

(3)

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

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