PaperlayerView exact revision on arXiv

Source-linked AI summary

Property B for random non-uniform hypergraphs

Grzegorz Ryn, Jakub Kozik

arXiv:2610.07379v1cs.DMmath.COmath.PR

TL;DR

The paper asks how allowing multiple edge sizes changes the existence of proper 2-colorings and the ability to find them efficiently. It analyzes weighted density bounds and extends AKKT to non-uniform instances, finding that separated sizes can permit successful coloring at arbitrarily large normalized density.

  • Problem

    For random hypergraphs with multiple edge sizes, it is unclear whether existential 2-colorability and efficient coloring respond to non-uniformity in the same way.

    Source: §1 · p. 1, §6 · p. 12

  • Method

    The paper weights k-edges by 2^-k for existential bounds and k2^-k for algorithmic analysis, and extends AKKT to non-uniform instances.

    Source: §1 · p. 1, §1.3 · p. 3

  • Results

    Existential bounds approach the uniform-model constant ln 2 as the minimum edge size grows, while sufficiently separated sizes allow AKKT to succeed at arbitrarily large normalized density.

    Source: §1 · pp. 1–2, §1.3 · p. 3

  • Takeaways & Limitations

    Normalized density alone cannot characterize AKKT success, because edge-size timing during execution also matters.

    Source: §1 · p. 2, §1.3 · p. 3

    The results take the density profile to be fixed and finitely supported as n grows, keeping the largest permitted edge size bounded.

    Source: §1.2 · p. 3

Abstract

from arXiv · show

We show that, in random hypergraphs with several permitted edge sizes, non-uniformity affects existential and algorithmic bounds for 2-colorability (Property B) in fundamentally different ways. Assigning weight $2^{-k}$ to each $k$-edge, we obtain upper and lower bounds in terms of the total edge weight that asymptotically match the uniform bounds as the minimum permitted edge size grows, regardless of how edges are distributed among sizes. We also extend the best-known algorithm for 2-coloring random uniform hypergraphs to the non-uniform setting. With weight $\frac{k}{2^k}$ assigned to each $k$-edge, we construct non-uniform instances whose expected total edge weight per vertex is arbitrarily large, yet the algorithm finds a proper coloring asymptotically almost surely. In the uniform setting, the algorithm fails with high probability once this quantity exceeds a constant. Our construction uses sufficiently separated edge sizes, so that edges of different sizes become relevant at well-separated stages of the execution and their effects are essentially independent.

1 Introduction

This paper studies how allowing multiple edge sizes changes random hypergraph 2-colorability, separating the existential question from the task of finding a coloring efficiently. It uses edge-size-dependent weights to show that existential bounds remain governed by normalized density, while AKKT success depends on how edge sizes interact over the algorithm’s execution.

1 Introduction

  • Property B means that a vertex 2-coloring gives every edge both colors; equivalently, it is a family of not-all-equal Boolean constraints.The paper frames random instances as typical behavior under density regimes, rather than as worst-case hypergraphs.Source: §1 · p. 1, §1.1 · p. 2

1.1 Property B and the uniform benchmark

  • Uniform random hypergraphs have near-matching existential bounds, while the best-known AKKT guarantee is smaller by a factor of order k.The paper studies whether these two aspects respond differently when several edge sizes are allowed.Source: §1 · p. 1, §1.1 · pp. 2–3

1 Introduction

  • The paper uses separate edge weights for the existential and algorithmic settings: 2^-k and k2^-k, respectively, to define normalized density.The existential weight reflects the expected number of monochromatic edges under a uniformly random coloring.Source: §1 · p. 1

1.3 Main results

  • Existential bounds depend on normalized density, with each permitted size contributing additively, and approach the uniform-model constant ln 2 as the minimum size grows.The lower bound uses a sharp-threshold upgrade after the second-moment argument gives only probability bounded away from zero.Source: §1 · p. 1, §1.3 · p. 3

1.2 Random non-uniform models

  • The non-uniform models assign each permitted edge size its own parameter, while the density profile remains fixed and finitely supported as n grows.Consequently, the largest permitted edge size stays bounded, and each edge remains a local constraint.Source: §1.2 · p. 3

1.3 Main results

  • AKKT succeeds when the expected number of newly created near-monochromatic configurations stays below 1 by a constant margin in every round.The relevant expectation varies over the execution, unlike the single instance-wide quantity used for existential bounds.Source: §1.3 · p. 3
  • Sufficiently separated edge sizes can yield arbitrarily large normalized density while AKKT still succeeds asymptotically almost surely.Different sizes become relevant in separate execution windows, so they need not obstruct the algorithm simultaneously.Source: §1 · p. 2, §1.3 · pp. 3–4

2 Random non-uniform hypergraphs

The section establishes random hypergraph models and a density-profile parametrization, then explains which model supports the existential and algorithmic analyses.

2 Random non-uniform hypergraphs

  • All permitted edge sizes in the random models considered are at least 3.Source: §2 · p. 4

2.1 Fixed-edge and independent-edge models

  • The fixed-edge model selects specified numbers of distinct edges uniformly by arity, independently across arities; the independent-edge model includes each potential edge independently with size-dependent probability.Source: §2.1 · p. 4

2.2 Density profiles

  • A fixed, finitely supported sequence of nonnegative coefficients specifies arity contributions to normalized density and remains fixed as n grows.Source: §2.2 · p. 4

2.3 Transfer between the two models

  • Fixed edge counts suit existential moment calculations, while independent edges suit exposing instances during algorithmic execution.Source: §2.3 · p. 4

3 Additivity in the existential problem

The existential bounds extend to non-uniform hypergraphs by adding contributions from each permitted edge size under a weighted density profile. The upper and lower bounds share this profile-based approach, with a sharp-threshold argument upgrading the lower-bound result to an asymptotically almost sure statement.

3.1 First-moment upper bound

  • The non-uniform first-moment upper bound holds under a condition that depends on the density profile through a single quantity, not on how edges are distributed among arities.This extends the uniform upper-bound condition to the non-uniform setting.Source: §3.1 · p. 5

3.2 Second-moment lower bound

  • For sufficiently large minimum edge size, the second-moment method gives a non-uniform lower bound under the stated profile condition.The condition requires the weighted profile sum in the lemma to remain below its specified threshold.Source: §3.2 · p. 5

3.3 Sharp-threshold upgrade

  • A sharp-threshold upgrade makes the non-uniform lower bound asymptotically almost sure for each fixed density profile.The proof embeds the independent-edge model into the random CSP model and follows Friedgut’s argument to rule out a coarse threshold.Source: §3.3 · p. 6
  • In the uniform specialization, the lower bound recovers leading-order asymptotics but not the sharper lower-order terms of or [12].The latter terms were obtained by Coja-Oghlan and Zdeborová [12] through analysis of the condensation transition.Source: §3.3 · p. 6

4 Algorithmic 2-coloring

AKKT extends to non-uniform instances without modification, and its success is controlled by the expected number of new 3-tails created in each round. The analysis uses dynamic exposure and bounds on active tails to establish an explicit sufficient condition in terms of the density profile.

4.1 The algorithm and its success condition

  • AKKT extends to non-uniform instances without modification, coloring two vertices per round while focusing on 2-tails and 3-tails to avoid failure.The algorithm declares failure if a 1-tail or a monochromatic edge appears.Source: §4 · p. 6, §4.1 · p. 6
  • If the minimum edge size is at least 5 and each round creates an expected number of new 3-tails bounded below 1 by a constant margin, AKKT succeeds a.a.s.The expected new 3-tail count is the central quantity in the success analysis.Source: §4.1 · pp. 6–7

4.2 Dynamic exposure and new 3-tails

  • Dynamic exposure reveals edges as they become 3-tails, while an auxiliary 3-uniform hypergraph records their uncolored vertices.The analysis delays each edge’s exposure until a triple is at risk of becoming a 3-tail.Source: §4.2 · p. 7

4.3 Active 3-tails

  • With high probability, positive intervals have length and tail counts at most ln2 n, no new active edges appear in the final rounds, and active tails have no complex intersections.Any two tails have at most one common vertex, and each active tail intersects at most one other active tail.Source: §4.3 · pp. 8–9

4.4 An explicit sufficient condition

  • Theorem 4.6 expresses an explicit sufficient success condition through the density profile and the asymptotic expected number of new 3-tails per round.The theorem’s maximized expression uses x, the fraction of vertices already colored.Source: §4.4 · p. 9

5 Benefits of non-uniformity

The section contrasts a uniform baseline with a construction showing that AKKT can succeed on non-uniform instances of arbitrarily large normalized density. Widely separated edge sizes keep their contributions from obstructing the algorithm simultaneously.

5 Benefits of non-uniformity

  • The section argues that AKKT’s success condition cannot be expressed through normalized density alone.Figure 2 plots total expected new 3-tail counts for non-uniform distributions, with each arity’s contribution peaking just below 1 in the examples described.Source: §5 · p. 10, Figure 2 · p. 11, §5.2 · p. 11

5.1 The uniform baseline

  • In the uniform baseline, the largest λ allowed by the success condition approaches 0.1395 as k→∞.λ≤0.13 suffices for k≥24, and λ≤0.074 suffices for k≥5.Source: §5.1 · p. 10

5.2 Arbitrarily large normalized density

  • For every c > 0, a non-uniform density profile exists with normalized density above c on which AKKT succeeds a.a.s.This yields an unbounded algorithmic advantage over uniform instances, where AKKT is known to fail at sufficiently large normalized density.Source: §5.2 · p. 10
  • As k increases, a single arity’s expected new 3-tail count peaks later and over a shorter interval; far-apart arities are therefore unlikely to peak together.Figure 1 illustrates the contribution from a single arity during execution.Source: §5.2 · pp. 10–11, Figure 1 · p. 10
  • Choosing sufficiently separated arities makes their critical intervals disjoint, so each execution stage has at most one arity with a substantial contribution.Outside its critical interval, an arity’s contribution is bounded by Ck^-3; the combined remaining contribution can be made arbitrarily small.Source: §5.2 · p. 11
  • Assigning each selected arity a peak contribution below 1−2ε keeps the total expected count of new 3-tails below 1−ε, yielding a.a.s. success.The construction can use arbitrarily many selected arities.Source: §5.2 · p. 11

6 Consequences of non-uniformity and open questions

The section contrasts the density-based existential bounds with AKKT’s dependence on how constraints are distributed through execution. It leaves open whether that contrast is fundamental and identifies related threshold and algorithm questions.

6 Consequences of non-uniformity and open questions

  • Existential bounds depend on expected monochromatic-edge count, whereas AKKT’s success depends on how constraint is distributed over execution.The authors ask whether this difference is fundamental or specific to AKKT.Source: §6 · p. 12
  • For random k-graphs in the stated edge-density range, proper colorings are shattered a.a.s. into small regions separated by large Hamming distances [13].The passage notes that similar behavior often coincides with failure of the best-known polynomial-time algorithms and has been proved a barrier for certain algorithm classes.Source: §6 · p. 12
  • An algorithm for random k-SAT reaches the leading-order shattering threshold [18], prompting the question of whether an analogous 2-coloring algorithm would extend to non-uniform instances.The authors ask whether its success would depend on a weighted normalized density or the full density profile, as for AKKT.Source: §6 · p. 12
  • For each k≥3, a sharp threshold sequence r_col(k,n) exists, but whether a universal limiting r_col(k) exists remains open.Coja-Oghlan and Zdeborová conjecture r_col(k)=ln 2/4+o(1) as k→∞ [12]; for non-uniform hypergraphs, the section asks whether a single suitably weighted quantity characterizes the threshold.Source: §6 · p. 12

AI statement

The authors describe the role of generative AI in preparing the paper and the development of an appendix proof. They say the paper’s motivation, proof strategies, and most computations came from the authors.

AI statement

  • The paper’s motivation, proof strategies, and most computations came directly from the authors.Appendix A was the only part whose development was partially AI-assisted.Source: AI statement · p. 12
  • Generative AI was used during finalization for proofreading, proof checking, and finding and correcting mistakes.Some AI-generated suggestions led to minor computational simplifications without changing the proof strategies.Source: AI statement · p. 12
  • An indirect AI suggestion prompted a renewed examination of the authors’ original sharp-threshold proof idea, which they found worked and used to simplify the appendix proof.The authors describe the resulting proof’s classification as AI-generated or not as ambiguous.Source: AI statement · p. 12

A Sharp thresholds

The appendix embeds a non-uniform random hypergraph model in a random CSP model and uses sharp-threshold tools to transfer a colorability conclusion. It also relates the independent-edge and fixed-edge models.

A Sharp thresholds

  • A hypergraph property is monotone if preserved by edge addition and symmetric if invariant under vertex permutations.The appendix also introduces the sharp-threshold-profile definition and the random CSP model used for the embedding.Source: A Sharp thresholds · pp. 13–14
  • The appendix embeds the independent-edge hypergraph model in a random CSP by representing each permitted k-edge as a constraint requiring its first k variables not all be equal.The constraint imposes no restriction on the remaining variables.Source: A Sharp thresholds · p. 14
  • In the embedded model, each potential permitted k-edge appears independently with probability (1+o(1))P_n(k).The coupling bounds the probability that the two hypergraphs differ, and any hypergraph property, including 2-colorability, then has probabilities differing by o(1).Source: A Sharp thresholds · pp. 14–15
  • The appendix applies Friedgut’s proof to rule out a coarse threshold in the non-uniform model, stating that the argument extends without substantive changes.The embedding supplies the consequence of Hatami and Molloy’s result used in this argument.Source: A Sharp thresholds · p. 15
  • Conditional on the number of edges of each size, the independent-edge model is the corresponding fixed-edge model; concentration and monotonicity transfer sharpness between them.The passage says the edge counts are Θ(n) with o(n) deviations a.a.s., and the colorability probabilities are bracketed by independent-edge models with counts a fixed proportion above and below.Source: A Sharp thresholds · p. 15
  • The appendix concludes that a suitable choice of ε in the lemma gives a.a.s. 2-colorability and proves Theorem 3.3.Source: A Sharp thresholds · p. 15

A.2 Note on sharp thresholds in non-uniform random structures

The embedding approach extends uniform-structure tools to non-uniform hypergraphs, but requires edge counts of the same asymptotic order. The authors also present a Friedgut-based approach for broader non-uniform distributions.

A.2 Note on sharp thresholds in non-uniform random structures

  • The embedding enables the use of tools for uniform structures, but depends on all edge counts having the same asymptotic order in n.Without that condition, the authors say a distribution Q independent of n cannot be constructed.Source: §A.2 · p. 15
  • The authors present a separate Friedgut-strategy approach that applies to broader non-uniform distributions without requiring edge counts to share an asymptotic order.Its proofs are available in a technical note.Source: §A.2 · p. 15

B.1 Non-uniform upper bound for 2-colorability

The section proves an upper bound for 2-colorability in a non-uniform random hypergraph model. Under the theorem’s conditions, the expected number of proper 2-colorings is o(1), so the sampled hypergraph is non-2-colorable asymptotically almost surely.

B.1 Non-uniform upper bound for 2-colorability

  • The calculations assume 4 divides n, since floors and ceilings change only lower-order terms.Source: §B.1 · p. 16
  • The proof simplifies sampling with replacement; with O(n) edges and arities at least 3, repeated edges occur with probability o(1).The authors say this does not affect the asymptotic statements.Source: §B.1 · p. 16
  • Under the theorem’s conditions, the expected number of proper 2-colorings is o(1), implying non-2-colorability asymptotically almost surely.The theorem assumes M(k) ≥ λ_k·2^k·n for every k, alongside an additional condition not specified in the supplied passage.Source: §B.1 · pp. 16–17

B.2 Non-uniform lower bound for 2-colorability

The lower-bound proof uses a second-moment argument on equitable colorings. It bounds overlap contributions in an initial interval and a middle interval, where strict concavity controls the latter.

B.2 Non-uniform lower bound for 2-colorability

  • For every ε > 0, the lemma’s stated regime requires λ_k(1 − 2^(−k)) < (1 − ε) ln 2 / 2 and min{k: λ_k > 0} ≥ k0.Source: §B.2 · p. 17
  • The proof counts equitable proper colorings and applies the second-moment method to show positive probability of 2-colorability.It assumes exactly M_k = λ_k·2^k·n edges of each size for the computation.Source: §B.2 · pp. 17–18, §B.2.2 · p. 22
  • The overlap analysis splits the sum into initial and middle intervals, then combines their bounds to complete the second-moment proof.Source: §B.2.1 · p. 19, §B.2.2 · p. 22

B.2.1 Initial interval.

  • In the initial overlap interval, the contribution is o(1) when the expected number of proper equitable colorings is exponentially large.The proof establishes that exponential growth in this regime.Source: §B.2.1 · p. 19

B.2.2 Middle interval.

  • For the middle interval, the proof uses Stirling approximations and bounds the sum through functions whose exponent is uniformly strictly concave.For sufficiently large k0, F''(x) ≤ −c on [2δ_I, 1/2].Source: §B.2.2 · pp. 20–21
Loading 2610.07379v1…