Separating Non-redundancy and Chain Length

1 Introduction

• NRD and CL also arise in bounds for CSP learning, streaming-space decidability, and kernelization, while sparsifier size can be governed by either parameter depending on the setting.The cited work connects learning-query lower bounds to NRD and upper bounds to CL; kernelization results bound instance size by O(NRD(R,n)).Source: §1 · pp. 2–3

1.2 Our Work

• Earlier results left open whether the parameters are always asymptotically equal; techniques bounding non-redundancy often also bound chain-length.For relations whose two parameters had been established, the paper reports NRD(R,n) = Θ(CL(R,n)).Source: §1.2 · p. 3
• CL(R,n) ≥ Ω(n^3) while NRD(R,n) ≤ n^3 / 2^Ω(log*(n)) for an explicit relation of arity 4 over a 3-element domain.This gives the paper's first example of a super-constant multiplicative separation between the parameters.Source: §1.2 · p. 3
• The relation's non-redundancy is bounded through the extremal quantity f(3)(n,6,3), for which Fox's bound yields the theorem's upper bound.The paper notes that the best lower bound it cites for this quantity leaves open the possibility of a substantially larger separation.Source: §1.2 · p. 4
• The construction orders constraints lexicographically across three variable groups and uses a 3-symbol domain to build a chain of length Ω(n^2) for a conditional predicate.Its witnesses make the current constraint unsatisfied while earlier constraints are satisfied; the construction also ensures earlier constraints receive assignments from P when the current one receives 000.Source: §1.2 · pp. 4–5
• A transfer to a standard arity-4 relation preserves the separation, multiplying non-redundancy by at most O(n) and chain-length by at least Ω(n).The transfer increases the relation's arity.Source: §1.2 · p. 5

2.1 CSPs, NRD, and CL

• NRD(R, n) is the maximum number of constraints in an instance where each constraint has an assignment violating it while satisfying all the others.Chain length instead orders the constraints and requires a witness for each constraint that satisfies the preceding ones.Source: §2.1 · pp. 6–7
• For P ⊊ Q, a conditional constraint is weakly satisfied when its tuple lies in Q and strongly satisfied when it lies in P.Conditional non-redundancy witnesses weak satisfaction of every constraint and strong satisfaction of all but the selected one; chain-length witnesses use the ordered-prefix condition.Source: §2.1 · p. 7

2.2 Extremal Combinatorics

• The paper defines f(3)(n, 6, 3) as the maximum edges in an n-vertex 3-uniform hypergraph with no six vertices containing three edges.The stated bound is f(3)(n, 6, 3) ≤ n^2 2^Ω(log*(n)).Source: §2.2 · p. 7

3 The Separating (Conditional) Predicate

• The conditional predicate uses a 3-symbol domain, with P containing six tuples and Q adding the tuple 000.The section presents P | Q as the conditional predicate whose chain length and non-redundancy are asymptotically distinct.Source: §3 · p. 8

3.1 Lower Bounding Chain-Length

• A lexicographically ordered family of constraints on (x, y, x+y) yields CL(P | Q, n) ≥ Ω(n^2).For each constraint, the witness assigns 000 to that constraint and a tuple in P to every preceding one.Source: §3.1 · pp. 8–9

3.2 Upper Bounding Non-Redundancy

• The conditional non-redundancy bound is NRD(P | Q, n) ≤ 27f(3)(n, 6, 3), based on excluding three hyperedges contained in six vertices.The proof extracts a 3-partite hypergraph with at least one twenty-seventh of the constraints, then bounds its size.Source: §3.2 · pp. 9–10

3.3 Unconditional separation

• The conditional separation is translated into an unconditional predicate with only a constant-factor change in the separation.The authors state this translation as the route from the conditional construction to the theorem on the unconditional relation.Source: §3.3 · p. 11

3.3.1 Proof of Eq. (2)

• A quadratic polynomial has zero set Q × {0, 1} under the map σ, supporting an O(n^2) non-redundancy bound for Q × {0, +}.The proof combines that bound with NRD(R, n) ≤ O(n · f(3)(n, 6, 3)) + NRD(Q × {0, +}, n).Source: §3.3.1 · pp. 11–12

3.3.2 Proof of Eq. (3)

• CL(R, n) ≥ Ω(n^3), while NRD(R, n) ≤ O(n · f(3)(n, 6, 3)) + O(n^2), with n · f(3)(n, 6, 3) = n^{3−o(1)}.The cubic chain is constructed from a conditional chain on half the variables; the non-redundancy bound combines the extremal term with an O(n^2) term.Source: §3.3.1 · pp. 11–12, §3.3.2 · p. 12
• The cubic chain for R is built by extending a conditional chain with variables that encode the order of its constraints.The construction gives CL(R, n) ≥ mn/2 = Ω(n^3).Source: §3.3.2 · p. 12

• The paper gives the first CSP predicate with a super-constant multiplicative separation between non-redundancy and chain length.Source: §4 · p. 13
• The authors conjecture that some predicates have polynomial separation between chain length and non-redundancy.They note a similar prediction in.Source: §4 · p. 13
• One possible route is to exploit asymmetric hypergraph Turán structure to build an unexpectedly long chain, though novel extremal-combinatorics techniques may be needed.The authors cite a dearth of known bounds for degenerate hypergraph Turán problems as the obstacle.Source: §4 · p. 13