ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Can we find examples on a slice? For all indicator functions f on the slice with Ef “ 1{2, does there exist a sub-balanced slice of dimension log˚ n (or growing) on which Ef ą 0.51?} Jacques Verstraete Let G be a graph of edge-density p P r0, 1s. The positive discrepancy of a graph G is defined by ! ˆ ˙ ) |X| disc pGq “ max epXq ´ p : X Ď V pGq 2 and the negative discrepancy is ! ˆ|X|˙ ) disc´ pGq “ max p ´ epXq : X Ď V pGq . 2 The discrepancy of G is maxtdisc pGq, disc´ pGqu. Erdős, Goldreich, Pach and Spencer [2] proved that there exists an absolute constant c ą 0 such that if G is an n-vertex graph of density p satisfying pp1 ´ pq ě 1{n, then a discpGq ě c pp1 ´ pqn3{2 . This is tight as shown by considering the random graph Gn,p . Bollobás and Scott [1] proved further that for some absolute constant b ą 0, disc pGq ¨ disc´ pGq ě bpp1 ´ pqn3 . We propose the following conjecture: Conjecture 8. For all \varepsilon ą 0, there exists a constant a “ ap\varepsilonq ą 0 such that for any n-vertex graph G of density p satisfying |p ´ pi ´ 1q\{i| ą \varepsilon for every i P Z , a disc` pGq ě a pp1 ´ pqn3{2 . Complete n-vertex balanced multipartite graphs with i parts have density about pi ´ 1q{i, but their positive discrepancy is Opnq, which explains why we require separation between p and these densities in the conjecture. In particular, the conjecture could be extended to say that if p0 ă}

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.