Tight Bounds for Anonymous Parity Certification

arXiv:2610.38829v1 [cs.DC] 28 Oct 2026

Tight Bounds for Anonymous Parity Certification Pedro Montealegre

Jorge Valenzuela

Universidad Adolfo Ibáñez Santiago, Chile p.montealegre@uai.cl

Universidad Adolfo Ibáñez Santiago, Chile jorg.valenzuela@alumnos.uai.cl

Abstract Local certification is the task of verifying graph properties using certificates assigned to the vertices of a network and checked using only local information. A central question in this area is to understand which properties admit constant-size certificates, independently of the network size. A fundamental test case is the parity of the network order. Bousquet, Feuilloley, Valenzuela, and Zeitoun (DISC 2026) showed that the complexity of certifying even order depends dramatically on the verification model. On arbitrary graphs, three bits per vertex suffice when unique identifiers are available and the verification radius is two. In contrast, in the anonymous radius-one model, they established an Ω(log log∗ n) lower bound and an O(log n) upper bound, leaving a substantial gap in our understanding of the problem. They also showed that constant-size certificates suffice in the anonymous radius-one model on graph classes of bounded expansion. In this paper, we settle the complexity of anonymous parity certification on general graphs and further investigate the role of graph sparsity. Our main contributions are: • We close the gap left by Bousquet et al., proving that the local complexity of certifying even order in the anonymous radius-one model is Θ(log log n). • We show that on graphs of degeneracy at most d, parity can be certified with O(log d) bits, while Ω(log log d) bits are necessary. In particular, every class of bounded degeneracy admits constant-size certificates, strictly generalizing the previous result for bounded-expansion classes. • We show that constant-size certification cannot be guaranteed on nowhere-dense classes, a broader notion of sparsity that includes bounded expansion. Specifically, we construct a fixed, subgraph-closed nowhere-dense class on which parity certification still requires Θ(log log n) bits. Together, our results provide a substantially more complete picture of anonymous parity certification on sparse graph classes, showing that its complexity depends not only on graph sparsity, but on the particular structural notion of sparsity under consideration. Keywords: Local certification, proof-labeling schemes, anonymous networks, certificate size, parity, lower bounds.

P. Montealegre and J. Valenzuela

1

Tight Bounds for Anonymous Parity Certification

Introduction

Local certification is a distributed mechanism for verifying graph properties. An all-powerful prover assigns a certificate to every vertex, and each vertex decides whether to accept by inspecting its local neighborhood and the certificates it contains. A scheme is correct if every graph satisfying the property has an assignment accepted everywhere, whereas on a graph violating it, every assignment is rejected by at least one vertex. The central resource is the maximum number of certificate bits per vertex; see [8, 12, 14, 18] for background. Recent research has increasingly focused on the constant-size regime: which properties can be certified with O(1) bits per vertex, independently of the size of the network? Such properties are sometimes regarded as “local” from the certification perspective, even when their definitions are global [1]. One of the most basic questions in this direction is whether the number of vertices is even. Let Even denote this property. Parity is inherently global: changing the number of vertices by one changes the answer, potentially far away from any given vertex. Yet it can be remarkably easy to certify. On cycles, even order is equivalent to bipartiteness and can be certified with one bit per vertex. On trees, constant-size certificates also suffice, by aggregating subtree sizes modulo two. The challenge is to understand whether such small local proofs are possible on arbitrary graphs. This question was recently investigated by Bousquet, Feuilloley, Valenzuela, and Zeitoun [2] (DISC 2026), who uncovered a striking dependence on the verification model and the underlying graph class. On general graphs, they showed that three bits suffice when vertices have unique identifiers and the verification radius is two. At the other extreme, they studied the anonymous radius-one model, which corresponds to the MULTISET model of local verification. In this model, a vertex sees only its own certificate and the multiset of its neighbors’ certificates, including multiplicities, but has no identifiers, port numbers, or knowledge of the graph order. They proved an Ω(log log∗ n) lower bound, against an O(log n) upper bound. They also established that, on every graph class of bounded expansion, constant-size certificates suffice even in this restricted anonymous model. Bounded expansion is a robust notion of structural sparsity that includes, for example, bounded-degree and planar graphs. Two natural questions remained. First, the gap between Ω(log log∗ n) and O(log n) left the actual complexity of anonymous parity certification on general graphs essentially undetermined. Second, the bounded-expansion result raised a structural question: how far can constant-size parity certification be extended beyond bounded expansion, and which weaker notions of sparsity, if any, still guarantee it? These are the questions we address here.

1.1

Our results

Our first contribution settles the open problem of [2] for anonymous networks with verification radius one. We establish matching upper and lower bounds on the size of the certificates. Theorem 1. There is an anonymous radius-one certification scheme for Even using O(log log n) bits per vertex. Our scheme shows that the order of the network need not be encoded explicitly to certify its parity, even in the anonymous radius-one model. The natural question is whether the doubly logarithmic dependence can be reduced further. We show that it cannot, already on connected bipartite graphs. Theorem 2. For every sufficiently large even n, there is a connected bipartite n-vertex graph Gn such that every accepting assignment of every correct anonymous radius-one verifier for 1

P. Montealegre and J. Valenzuela

Tight Bounds for Anonymous Parity Certification

Even has a certificate of length Ω(log log n). This remains true when correctness is required only on bipartite inputs. Together, Theorems 1 and 2 show that certifying Even on connected n-vertex graphs has local complexity Θ(log log n). Thus parity has genuinely intermediate complexity in this model: constant-size certificates do not suffice, but the Θ(log n) bits needed to explicitly represent the graph order are unnecessary. The lower bound holds even under a bipartite promise. Our second contribution strengthens the positive result of [2] by replacing bounded expansion with bounded degeneracy. Recall that a graph is d-degenerate if every nonempty subgraph has a vertex of degree at most d. This condition allows vertices of arbitrarily large degree but restricts the density of every subgraph. Crucially, every bounded-expansion class has bounded degeneracy, whereas the converse is false: for example, the class of one-subdivisions of complete graphs is 2-degenerate but does not have bounded expansion. Theorem 3. The verifier of Theorem 1 admits O(log d)-bit certificates on every connected even-order d-degenerate graph, for every integer d ≥ 2, and constant-size certificates when d = 1. It remains sound on arbitrary connected graphs and is not supplied with d. In particular, every graph class of bounded degeneracy admits constant-size certificates, strengthening the bounded-expansion result of [2]. The dependence on d, however, cannot be removed altogether. Our next result shows that the certificate size must grow with d, even on bipartite graphs and even when the verifier is only required to work under the d-degeneracy promise. Theorem 4. For every sufficiently large integer d, there is a connected bipartite graph of even order and degeneracy at most d on which every accepting assignment of every anonymous radius-one certification scheme for Even contains a certificate of length Ω(log log d). This holds even when correctness is required only on connected bipartite d-degenerate graphs. The two bounds leave a gap in the optimal dependence on the degeneracy parameter, between Ω(log log d) and O(log d). Our third contribution shows that the bounded-expansion theorem cannot be extended to all nowhere-dense classes. A graph class is nowhere dense if, for every fixed radius r, there is a clique that cannot occur as an r-shallow minor of any graph in the class. This is a broad notion of sparsity: every bounded-expansion class is nowhere dense, but the converse does not hold, and nowhere-dense classes may have unbounded degeneracy. Theorem 5. There exists a fixed, subgraph-closed nowhere-dense class of graphs on which certifying Even in the anonymous radius-one model has local complexity Θ(log log n). In fact, our construction gives a bipartite class whose girth grows with the graph order. A precise description of this class, together with a quantitative lower bound, is given in Section 6. Thus, the full difficulty of the unrestricted anonymous model persists even on graphs with arbitrarily large girth. Taken together, these results give a substantially sharper picture of parity certification on sparse graph classes. The constant-size result extends beyond bounded expansion to all classes of bounded degeneracy, but it fails already on a fixed nowhere-dense class. Hence the positive phenomenon discovered in [2] is not explained by sparsity in general: the particular structural restriction matters. What remains open is the exact quantitative cost of parity certification as a function of degeneracy.

2

P. Montealegre and J. Valenzuela

1.2

Tight Bounds for Anonymous Parity Certification

Proof ideas and techniques

Sharing contributions without identifying parents. Earlier anonymous schemes organize contributions by choosing a parent for each vertex. A color identifies that parent only if no other neighbor has the same color [2]. Enforcing this uniqueness can require many colors, making the parent descriptions expensive. Our approach allows a contribution to be shared among several neighbors. For example, two senders with the same two receivers can each send half a unit to each receiver. Each sender sends one unit in total, and each receiver receives one unit, even though neither sender distinguishes between the receivers. Fractions allow us to coordinate whole-number totals without making individual choices. The verifier checks that the amount sent minus the amount received is an odd integer at every vertex. Every payment appears once as an outgoing amount and once as an incoming amount, so these differences sum to zero. Since an odd number of odd integers cannot sum to zero, acceptance implies that the graph has even order. The main task is to arrange these payments using short descriptions. Our sharing lemma coordinates fractional payments so that receivers obtain integer totals, using colors and fractions that take O(log log n) bits to describe. The prover applies the lemma between successive distance layers, working toward a chosen root. At each step, a vertex chooses what to send according to the parity of what it has already received. On bounded-degeneracy graphs, the same construction uses constant-size descriptions. Changing parity without changing local views. A lower bound construction must change the number of vertices; changing edges alone cannot change parity. It must also leave every vertex with a local view that the verifier accepts. The earlier construction [2] achieves this using all nonempty subsets of a point set, resulting in exponentially many vertices. We obtain a smaller construction using intervals in an ordered point set. Each interval is represented by a vertex adjacent to the points it contains. The key is to find two collections of intervals that cover every point equally often, but whose numbers of intervals have different parities. If all their interval vertices carry the same certificate, we can copy one collection and delete the other. Every point loses and gains the same number of neighbors with that certificate. Retained interval vertices keep their views, and new copies imitate existing vertices. All checks still pass, although the graph order changes parity. Intervals provide a simple way to find such collections. When traversing a closed loop of interval endpoints, rightward and leftward steps cover every point equally often. If the loop has odd length, the two groups of steps have different parities. Thus a sound verifier must prevent an odd cycle whose intervals all carry the same certificate. A classical coloring bound [16] then forces a logarithmic number of distinct certificates. Because the construction has only polynomially many vertices, describing that many certificates requires Ω(log log n) bits. Preserving large girth through vertex splitting. For the nowhere-dense lower bound, we need a parity-changing operation that preserves large girth. Suppose three vertices carry the same certificate and one has a neighbor-certificate profile equal to the sum of the other two profiles. We can split that vertex into two, distributing its neighbors so that each replacement imitates one of the other vertices. Every old neighbor still sees one vertex with the original certificate. The order increases by one, and splitting cannot create a shorter cycle. To force such a triple, we return to intervals. Their color-count profiles satisfy an exact identity: the profile of a long interval is the sum of the profiles of its two pieces. For every coloring of the point set, a counting argument finds an ordered sequence whose interval profiles are all sufficiently likely under random subset sampling. Sampling supplies many representa-

3

P. Montealegre and J. Valenzuela

Tight Bounds for Anonymous Parity Certification

tives of each profile, allowing us to remove short cycles while keeping all these representatives available. Color each interval’s endpoint pair by its representative’s certificate. An elementary Ramsey bound gives a monochromatic triangle, and hence the three equally certified profiles needed for splitting.

1.3

Related work

Sublogarithmic certification. Bousquet, Feuilloley, and Zeitoun [1] identified a Θ(log log n) regime for an arithmetic property of anonymous path lengths, defined using products of consecutive primes, and proved a gap between constant and logarithmic complexity on anonymous cycles. Our result brings the same intermediate scale to a simple counting predicate on unrestricted connected graphs. Since parity has constant-size certificates on paths and cycles, its difficulty here comes from the richer range of possible topologies. A related result of Feuilloley, Sedláček, and Slávik [11] gives O(log log n)-bit certificates for at most one selected vertex when the minimum degree is at least α log2 n, for a sufficiently large constant α. Their scheme uses identifiers and radius two, highlighting the different assumptions under which sublogarithmic certification becomes possible. Structure and certificate size. Graph structure is a recurring theme in local certification, from certifying planarity [9] to logical metatheorems on tree-like graph classes [5, 10, 13]. On bounded-treewidth classes, these metatheorems progressed from O(log2 n)-bit certificates [13] to O(log n)-bit certificates for MSO2 properties [5]. For parity in the anonymous radius-one model, Bousquet et al. [2] obtained constant-size certificates on bounded-expansion classes using Hickingbotham’s conflict-free neighborhood colorings [17]. We extend this constantsize guarantee from bounded expansion to bounded degeneracy. However, replacing bounded expansion with nowhere denseness does not preserve the guarantee: on a fixed subgraphclosed nowhere-dense class, parity certification still has the Θ(log log n) complexity of general graphs. Combinatorial tools. Our construction draws on the theory of conflict-free and odd colorings [4, 6, 7, 20]. Conflict-free colors single out a neighbor, whereas odd colors need only occur an odd number of times in a neighborhood. Rational sharing adds another possibility: contributions can be distributed among indistinguishable neighbors while preserving integral totals. Conservation checks already appear in flow certification [18, 21]; the challenge here is to describe the transfers with short anonymous vertex certificates. The lower-bound techniques also have a broader reach. Chang, Lee, and Tsai [3] adapted the earlier parity construction to anonymous 2-vertex-connectivity, showing how neighborhood identities that preserve accepted local views can obstruct certification beyond counting predicates.

1.4

Discussion and open problems

We have determined the local complexity of Even in the anonymous radius-one model: Θ(log log n) bits are necessary and sufficient in the worst case. Parity thus gives an elementary global property whose optimal certificate size is unbounded but sublogarithmic. The two proofs explain this scale from complementary directions. Rational sharing coordinates parity contributions without selecting unique parents, while the interval construction quantifies how much ambiguity any sound verifier must eliminate. The same verifier admits constant-size certificates on every class of bounded degeneracy. These results settle the dependence on graph order and leave several questions about structure and the verification model. The Θ(log log n) bound also holds, with a smaller leading constant in the lower bound, on a fixed subgraph-closed nowhere-dense class. Thus nowhere denseness alone does not guarantee constant-size certificates, even though bounded degeneracy does.

4

P. Montealegre and J. Valenzuela

Tight Bounds for Anonymous Parity Certification

The dependence on degeneracy. Our structural bounds lie between Ω(log log d) and O(log(d+1)). They show that degeneracy alone controls certificate size, but do not determine the optimal dependence on this parameter. Open problem 1. What is the optimal local complexity of certifying Even on connected d-degenerate graphs, as a function of d? In particular, do O(log log(d + 2))-bit certificates suffice, independently of the graph order? Our lower-bound witnesses have order Θ(d2 ), so the general upper bound already gives O(log log d)-bit certificates on them. Consequently, they cannot establish a larger asymptotic lower bound in terms of d. An Ω(log d) lower bound would require witnesses whose order exceeds every fixed polynomial in d. Within our approach, improving the upper bound would require a more compact description of the sharing rules. Identifiers and verification radius. Bousquet et al. [2] gave three-bit certificates when identifiers and radius two are both available. Our tight bound establishes the cost of imposing anonymity and radius one together. The intermediate cases, already asked about in [2], remain unresolved. Open problem 2. What is the local complexity of certifying Even on arbitrary connected graphs (i) with identifiers and verification radius one, and (ii) anonymously with verification radius two? Do constant-size certificates suffice in either model? Both models inherit our O(log log n) upper bound. The lower-bound modification uses anonymity to copy certified vertices without introducing new identifiers into their local views, and radius one to hide changes in their neighbors’ other incident edges. Extending the obstruction to either intermediate model therefore requires an additional idea. Resolving these cases would separate the roles of identifiers and observation radius in the cost of certifying parity. Counting modulo other integers. Divisibility by a fixed integer, studied in [2], is a natural next setting in which to test the scope of our techniques. Open problem 3. For a fixed integer k ≥ 3, what is the optimal certificate size for verifying that the order of a connected graph is divisible by k in the anonymous radius-one model? Does the Θ(log log n) bound hold for every such k? The conservation principle extends directly: if every vertex has integer net outflow congruent to one modulo k, then summing the balances forces k | n. Constructing these balances with short anonymous labels, however, requires control of the residues modulo k, beyond the odd–even distinction used here. For the lower bound, the profile-splitting construction also gives an Ω(log log n) lower bound for divisibility by every fixed integer k ≥ 2, since it changes the order by exactly one. The remaining question is whether an O(log log n) upper bound holds for these moduli.

2

Model and definitions

2.1

Graphs and certification model

All graphs are finite, simple, and undirected; input graphs are connected. For G = (V, E), write n = |V |, NG (v) for the neighborhood of v, degG (v) = |NG (v)|, ∆(G) for the maximum degree, and G[X] for the subgraph induced by X ⊆ V . We omit the subscript G when clear. All logarithms are base two. Write Z and Q for the integers and rationals, and 1A for the indicator of a condition or the characteristic vector of a set. 5

P. Montealegre and J. Valenzuela

Tight Bounds for Anonymous Parity Certification

A graph is k-degenerate, for an integer k ≥ 0, if every nonempty subgraph has a vertex of degree at most k. Equivalently, there is an ordering in which each vertex has at most k later neighbors; the least such k is its degeneracy. Orienting edges from earlier to later in this ordering gives an acyclic orientation of maximum outdegree at most k. The girth of a graph is the length of its shortest cycle, with girth infinity for forests. For an integer ρ ≥ 0, a depth-ρ minor of G is obtained from a subgraph of G by contracting pairwise disjoint connected subgraphs of radius at most ρ, measured within each contracted subgraph. A graph class C is nowhere dense if, for every integer ρ ≥ 0, there is an integer t such that no graph in C contains Kt as a depth-ρ minor [19]. Certificates and local verification. We use the anonymous model with verification radius one of [2]. A certificate assignment on G is a map c : V → {0, 1}∗ , chosen by an external prover. The local view at a vertex v is
viewG,c (v) = c(v), {{c(u) : u ∈ N (v)}} , where double braces denote a multiset. A verification algorithm is a deterministic function that takes this view and outputs accept or reject. The same function is used at every vertex and on every input graph. A graph is globally accepted if all its vertices accept. Vertices have no identifiers, ports, graph order, neighbor degrees, or information about edges between neighbors or their other incident edges. There are no computational restrictions on the prover or the verification function. In particular, the prover may assign different certificates to structurally indistinguishable vertices. Certification schemes and local complexity. Let C be a graph class, let P be a graph property on C, and let s : N → N. A certification scheme for P on C with local complexity s consists of a verification algorithm satisfying the following two conditions: • Completeness. Every connected n-vertex graph G ∈ C satisfying P admits a certificate assignment c with |c(v)| ≤ s(n) for every vertex v, under which G is globally accepted. • Soundness. For every connected graph G ∈ C not satisfying P , and every certificate assignment c, at least one vertex rejects. The class C is a promise: the verification algorithm may depend on C and P , and no correctness requirement is imposed outside C. Unless a class is specified, C consists of all graphs. In this paper, P = Even: completeness concerns even-order graphs and soundness concerns oddorder graphs.

2.2

Rational transfers, encodings, and standard combinatorial facts

A transfer on an ordered edge (v, u) contributes to the outgoing total at v and the incoming total at u. The net outflow ∆(v) is outgoing minus incoming; an odd net outflow means ∆(v) ∈ 2Z + 1. All transfers used in the upper bounds are nonnegative rationals. We fix a self-delimiting encoding of nonnegative integers. For t ≥ 0, let ℓ be the binary length of t + 1 and encode t as 1ℓ 0 bin(t + 1), using 2ℓ + 1 = O(log(t + 2)) bits. Encode a nonnegative rational by its numerator and positive denominator in lowest terms, with zero represented by 0/1. If q ∈ [0, 2) has reduced denominator at most k, its numerator is less than 2k, so its encoding takes O(log(k + 1)) bits. We use the following standard facts. Lemma 6 (Hall [15]). Let B = (S ∪ R, EB ) be a finite bipartite graph, and write NB (T ) = S N (s) for T ⊆ S. If |NB (T )| ≥ |T | for every T ⊆ S, then B has a matching covering S. B s∈T Lemma 7 (Degeneracy bound, Szekeres and Wilf [22]). Every finite d-degenerate graph has a proper coloring with at most d + 1 colors. 6

P. Montealegre and J. Valenzuela

Tight Bounds for Anonymous Parity Certification

Lemma 8 (Bipartite covers, Harary, Hsu, and Miller [16]). If r bipartite subgraphs cover all edges of Kt , then r ≥ ⌈log t⌉. For a hypergraph H, write ∆(H) for the maximum number of hyperedges containing a vertex, and ε(H) for the minimum hyperedge size. A graph–hypergraph pair (F, H) has a common vertex set. Lemma 9 (Dai, Ouyang, and Pirot [6, Theorem 5]). There is a universal constant C ≥ 1 such that the following holds. Let (F, H) be a finite graph–hypergraph pair, with D = ∆(H) ≥ 2. If ε(H) > C log D, then its vertex set admits a coloring that is proper on F and has some color occurring an odd number of times in each hyperedge of H, using at most ∆(F ) + C log D colors.

3

Upper bound in general graphs

Earlier anonymous schemes encode parents through conflict-free colors: a vertex selects a color unique among its predecessors [2]. This can be expensive even on sparse graphs. If there are m receivers and one sender for every pair, all receivers need different colors. The resulting one-subdivision of Km has Θ(m2 ) vertices, so color names take Θ(log n) bits. Rational sharing avoids selecting a unique parent by allowing equal transfers to neighbors with the same color. We first construct transfers on a bipartite graph of senders and receivers, then apply this construction between consecutive BFS layers.

3.1

The sharing lemma

In a bipartite graph B = (S ∪ R, EB ), vertices of S are senders and vertices of R are receivers. A receiver coloring is odd at a sender if some color occurs an odd number of times among its neighbors. Each sender stores a base amount and a selected color; each receiver stores its own color. These labels determine the edge transfers, including when senders have identical neighborhoods. Lemma 10 (Sharing lemma). Let B = (S ∪ R, EB ) be a finite bipartite graph on n ≥ 2 vertices, with senders S and receivers R. Assume every sender has a neighbor. There are receiver colors γr ∈ Z2>0 , rational base amounts qs ∈ [0, 2), and selected colors as ∈ {0} ∪ Z2>0 such that the transfers f (s, r) = qs + 1γr =as (sr ∈ EB ) satisfy X

f (s, r) ∈ 2Z + 1 (s ∈ S),

r∈NB (s)

X

(1) f (s, r) ∈ Z

(r ∈ R).

s∈NB (r)

There are O(log2 (n + 2)) colors, each coordinate of a color is O(log(n + 2)), and every base amount has reduced denominator O(log(n + 2)). Each label γr , qs , or as therefore has an O(log log(n + 2))-bit encoding, with color coordinates encoded separately. The value as = 0 selects no color; equality of colors means equality in both coordinates, and no receiver color equals 0. Proof. Let C be the constant in Lemma 9. Take the least positive even integer b > C log(n+2), and put k = 2b − 1. Partition the senders into Ssmall = {s ∈ S : degB (s) ≤ k},

Slarge = {s ∈ S : degB (s) ≥ k + 1}. 7

P. Montealegre and J. Valenzuela

Tight Bounds for Anonymous Parity Certification

(a) Three unsatisfied senders

(b) Two become satisfied

qa = 1 sends 2

qb = 1 sends 2

qc = 0 sends 0

qa = 21 sends 1

qb = 32 sends 3

qc = 0 sends 0

a

b

c

a

b

c

u

v

u

v

receives 2

receives 2

receives 2

receives 2

Figure 1: A rational perturbation in the maximality argument. All three senders a, b, c have neighborhood {u, v}, so the unsatisfied set in (a) violates Hall’s condition. Its neighborhood vectors admit the dependence t = (−1, 1, 0); since every sender has degree two, g = 2. Adding t/g to the base amounts gives (b): each receiver’s incoming total is unchanged, but two senders become satisfied as their outgoing totals change from even to odd. Thus (a) cannot maximize the number of satisfied senders. We construct transfer rules for these two groups and then combine their receiver colorings. Case 1: senders with at most k neighbors. For each s ∈ Ssmall , write ds = degB (s). Choose rational base amounts qs such that X ds qs ∈ Z (s ∈ Ssmall ), qs ∈ Z (r ∈ R). s∈NB (r)∩Ssmall

Thus both outgoing and incoming base totals are integral. The zero assignment is feasible. Among feasible assignments, maximize the number of senders with odd outgoing base total. Call these senders satisfied, and the others unsatisfied. A maximum exists because this number is an integer between zero and |Ssmall |. We claim that the unsatisfied senders can be matched to distinct receivers. Otherwise Hall’s theorem gives a set T of unsatisfied senders with |NB (T )| < |T |. Their neighborhood vectors are supported on fewer coordinates than there are vectors, so they are linearly dependent over Q. Clearing denominators gives integers ts , not all zero, such that X ts 1NB (s) = 0. s∈T

Let g be the positive greatest common divisor of the nonzero integers P ds ts . Replace qs by qs + ts /g for s ∈ T . At a receiver r, the incoming total changes by g1 s∈T ∩NB (r) ts = 0. At sender s ∈ T , the outgoing total changes by the integer ds ts /g. These integers have greatest common divisor one, so at least one is odd. At least one previously even total becomes odd, and all previously satisfied senders are unchanged. This contradicts maximality. Hence there is a matching covering the unsatisfied senders; let ρ(s) ∈ NB (s) be the receiver matched to s. Figure 1 illustrates how a dependence preserves receiver totals while improving sender parities. Subtract an even integer from each qs to put it in [0, 2). All incoming and outgoing totals change by even integers, preserving integrality and parity. Since ds qs is integral, the reduced denominator of qs divides ds ≤ k, and its numerator is less than 2ds . Thus the base amount takes O(log(k + 1)) bits. To make a unit correction at each unsatisfied sender, form an auxiliary graph Ksmall on the receivers. For every such sender s, join ρ(s) to all other vertices of NB (s). For X ⊆ R, every edge of Ksmall [X] is contributed by a matched receiver in X. These receivers are distinct and each contributes at most k − 1 edges, so |E(Ksmall [X])| ≤ (k − 1)|X|. 8

P. Montealegre and J. Valenzuela

Tight Bounds for Anonymous Parity Certification

The graph Ksmall is therefore (2k − 2)-degenerate. Lemma 7 gives a proper coloring χ with 2k − 1 colors. Each matched receiver has a color unique among its sender’s neighbors. Select this color at an unsatisfied sender, adding exactly one to its outgoing total. Select no color at a satisfied sender. Every sender in this case now sends an odd integer total, and receiver totals remain integral. Case 2: senders with at least 2b neighbors. Let H be the hypergraph on R whose hyperedges are the distinct neighborhoods NB (s), for s ∈ Slarge . Set D = ∆(H), taking D = 0 if there are no hyperedges. A receiver belongs to at most one hyperedge per large sender, so D ≤ |Slarge | ≤ n. If D ≤ 1, the distinct neighborhoods are pairwise disjoint. Give one receiver in each such neighborhood color one and all remaining receivers color two. This is odd at every large sender; if there are no large senders, any coloring suffices. If D ≥ 2, apply Lemma 9 to the pair (F, H), where F = (R, ∅) is the edgeless graph on the receivers. The parameters in the lemma satisfy ∆(F ) = 0, ε(H) = min degB (s) ≥ 2b s∈Slarge

> C log(n + 2) > C log D, and the lemma supplies an odd coloring of H with at most C log D < b colors. Allowing unused colors, both cases therefore give a coloring h : R → {1, . . . , 2b} that is odd at every sender in Slarge : each sender’s neighborhood is a hyperedge, including when several senders have the same neighbors. Combining the receiver colorings. Give each receiver r ∈ R the ordered-pair color γr = (h(r), χ(r)). This is a common refinement of the two colorings: two receivers have the same color precisely when they agree in both coordinates. There are at most 2b(2k − 1) = O(log2 (n + 2)) color pairs. For a satisfied sender in Ssmall , retain qs and set as = 0. For an unsatisfied sender, retain qs and select the refined color of ρ(s). This receiver still has a color unique in NB (s), so all transfers from low-degree senders are unchanged. For a sender in Slarge , an odd h-color class in its neighborhood splits into refined color classes. At least one remains odd. Set qs = 0 and select that refined color as as . This sends an odd integer total and contributes only integers at receivers. The low-degree senders already gave integral receiver totals, proving (1). Every reduced denominator is at most k = O(log(n + 2)); its numerator is less than 2k because 0 ≤ qs < 2. The two color coordinates are at most 2b and 2k − 1, respectively, both O(log(n + 2)). Encoding the coordinates separately, and using a constant-size tag to distinguish a selected pair from 0, gives O(log log(n+2)) bits for each color label. The rational bounds give the same bound for each base amount.

3.2

The certification scheme

Theorem 1. There is an anonymous radius-one certification scheme for Even using O(log log n) bits per vertex. Proof. Certificate and verifier. A certificate is a four-tuple (λ, γ, q, a), where λ ∈ {0, 1, 2} is a layer label, γ ∈ Z2>0 is a color, q ∈ Q ∩ [0, 2) is a base amount, and a ∈ {0} ∪ Z2>0 is a selected color. Encode λ in two bits. Encode γ by concatenating the self-delimiting encodings of its two positive coordinates, using the integer encoding from the preliminaries. Record q by its numerator and positive denominator in lowest terms, using the same integer encoding. Encode a with a tag bit: 0 represents no selected color, and 1 is followed by the two encoded coordinates of the selected color. A certificate is malformed if its fields cannot be decoded, 9

P. Montealegre and J. Valenzuela

Tight Bounds for Anonymous Parity Certification

violate the stated ranges, record a fraction that is not in lowest terms, or leave unused trailing bits. Color equality is coordinatewise. Since no receiver color is 0, the selected color a = 0 always means that no extra unit is sent. For an arbitrary certificate assignment, call a neighbor u of v a predecessor when λu ≡ λv − 1 (mod 3), and a successor when λu ≡ λv + 1 (mod 3). Use subscripts to indicate the vertex supplying a field and write pv (u) = qv + 1γu =av . A vertex rejects if any certificate in its local view is malformed. Otherwise it checks X X ∆(v) := pv (u) − pu (v) ∈ 2Z + 1. (2) u∈N (v) λu ≡λv −1 (mod 3)

|

{z

sent to predecessors

u∈N (v) λu ≡λv +1 (mod 3)

}

|

{z

received from successors

}

The transfers are nonnegative rationals. The vertex computes its net outflow exactly and checks that it is an odd integer; a noninteger difference causes rejection. Both sums are computable from the local view: a neighbor’s fields determine its term, and repeated certificates contribute with their multiplicity. Three residues distinguish the two directions along consecutive layers; only these constant-size residues are stored, rather than full distances. Soundness. Each transfer is counted once positively at its sender and once negatively at its receiver; edges between equal residues are ignored. This holds for arbitrary certificate assignments, regardless of whether the residues describe actual layers. If every vertex accepts, conservation gives X 0= ∆(v) ≡ n (mod 2), v∈V

because each summand is an odd integer. Thus n is even. Completeness. Choose a root r in an even-order graph and let Li = {v : dist(r, v) = i}

(i ≥ 0),

L−1 = ∅,

be its BFS layers. Give each vertex its layer number modulo three. Every edge joins equal or consecutive layers, and every nonroot vertex has a neighbor in the preceding layer. Process Lh , Lh−1 , . . . , L1 , where h is the maximum distance from the root; P the root will be handled last. Once a vertex v ∈ Li has received an integer amount S(v) = w∈N (v)∩Li+1 pw (v) from the next layer, its outgoing total must have parity opposite to S(v). If S(v) is odd, set qv = av = 0: the vertex sends zero, so its net outflow is odd. Call vertices with even S(v) active, and let Si be the active vertices of Li . Form the bipartite graph Bi with parts Si and Li−1 , containing all edges of G between these parts. Its senders are the active vertices and its receivers are the vertices of the preceding layer. It has at most n vertices, and every sender has a receiver neighbor. If Si ̸= ∅, apply Lemma 10 to Bi : store its receiver colors on Li−1 and its base amounts and selected colors on Si . On an edge vu of Bi , its transfer f (v, u) is exactly the amount pv (u) computed by the verifier. Every active vertex sends an odd integer total, and every vertex of Li−1 receives an integer amount. This continues the induction, starting with zero incoming totals at the deepest layer. If Si = ∅, all transfers from that layer are zero and all vertices of the preceding layer may be given color (1, 1). Any color not assigned by this procedure may be set to (1, 1). The color of a vertex is chosen when the next layer is processed; its base amount and selected color are chosen when its own layer is processed. Every nonroot vertex now has an odd integer net outflow: active vertices send an odd total after receiving an even total, and inactive vertices send zero after receiving an odd total. Give the root q = P a = 0. All other checks already hold, so conservation forces its net outflow to be ∆(r) = − v̸=r ∆(v). This is an odd integer because n − 1 is odd. This gives an accepting assignment.

10

P. Montealegre and J. Valenzuela

Tight Bounds for Anonymous Parity Certification

q = 12 no selected color

L2

a

q=0 select γu

q = 32 no selected color 1 2

b

3 2

0

1 2

L1

γu = (1, 1) receives 3

c

1

3 2

u

v 0

γv = (1, 2) receives 2

1 r

L0

∆(a), ∆(b), ∆(c), ∆(u), ∆(v), ∆(r) = (1, 3, 1, −3, −1, −1)

Figure 2: Rational sharing on a six-vertex graph. In the first sharing step, the top vertices are senders and u, v are receivers; each sender is adjacent to both receivers. The orange edge adds one unit to the selected color; dashed edges carry zero. The integer receipts determine which receivers become active senders to the preceding layer. Every net outflow is odd, and their sum is zero. Certificate size. By the sharing lemma, each color, base amount, and selected color can be encoded in O(log log n) bits. The layer label takes a constant number of bits. A fixed selfdelimiting encoding preserves this asymptotic bound. Thus an anonymous radius-one verifier uses O(log log n) certificate bits. Figure 2 illustrates the construction, including fractional transfers and a unit correction.

4

Lower bound

The earlier lower bound [2] uses all nonempty subsets of an m-point set, giving exponentially many vertices, and a finite-unions argument. We use only intervals, giving quadratically many vertices. An odd cycle of interval endpoints yields a parity-changing modification that preserves local views, and a bipartite-cover count then gives the quantitative certificate bound.

4.1

The interval incidence construction

For m ≥ 1, take the ordered set of points P = {1, . . . , m}. The graph Hm has a point vertex xt for each t ∈ P and an interval vertex yij for every 0 ≤ i < j ≤ m, adjacent exactly to {xi+1 , . . . , xj }. The corresponding subset of P is the discrete interval (i, j] = {i + 1, . . . , j}. The endpoint indices 0, . . . , m specify the boundaries of these intervals; they do not add vertices to Hm . The graph Hm is the bipartite incidence graph of these intervals: the two parts consist of point
vertices and interval vertices. This graph is connected and bipartite, with Nm = m + m+1 = m(m+3) vertices. When m ≡ 1 (mod 4), its order is even. Indeed, 2 2 y0m is adjacent to every point vertex, and every other interval vertex has a nonempty set of point neighbors, proving connectedness. Fix a sufficiently large even n. Choose the largest m ≡ 1 (mod 4) with Nm ≤ n, and attach n − Nm leaves to the point vertex x1 . Call the resulting graph Gn . It is connected and √ bipartite of order n. Moreover Nm+4 − Nm = 4m + 14, so n = Nm + O(m) and m = Θ( n). These additional leaves give a graph for every sufficiently large even n. Consider any accepting certificate assignment on Gn . Introduce a separate complete graph Km+1 with vertex set {0, . . . , m}, and color its edge ij by the certificate of yij . This auxiliary graph is not part of the input graph Gn . Its vertices are the interval endpoints, whereas the 11

P. Montealegre and J. Valenzuela

Tight Bounds for Anonymous Parity Certification

two parts of Hm represent points and intervals. The input graph Gn remains bipartite even when the auxiliary graph contains odd cycles.

4.2

A modification preserving local views

The following lemma is the key local-view argument. A cycle of endpoints gives two collections of intervals that cover each point equally often, allowing additions and deletions of interval vertices to cancel at every point vertex. Lemma 11. For every certificate b, the subgraph of the auxiliary graph formed by the edges of color b is bipartite. Proof. Suppose that it contains a simple odd cycle t0 , t1 , . . . , tℓ = t0 . For its ath edge, let εa = 1 if ta > ta−1 and εa = −1 if ta < ta−1 , and write Ia = (min(ta−1 , ta ), max(ta−1 , ta )]. The interval vertices corresponding to these edges all have certificate b. For 0 ≤ t ≤ m, let pt = 1{1,...,t} ∈ Zm ; in particular, p0 = 0. These vectors record the points at most t. By the definition of Ia and εa it holds that εa 1Ia = pta − pta−1 . Consequently ℓ X

εa 1Ia = 0.

(3)

a=1

The differences sum to zero because each vector pta appears once with each sign as we go around the cycle. Call an interval positive if εa = 1 and negative if εa = −1. Equation (3) says that each point is covered equally often by positive and negative intervals, even though their total number is odd. Figure 3 gives a five-cycle example. Modify the graph and its certificate assignment as follows. For every εa = −1, delete the corresponding interval vertex. For every εa = 1, add one new copy of that interval vertex, with certificate b and the same point neighbors. Cycle edges are distinct, so the modifications are well defined. The resulting graph is still simple and bipartite: the copies are new vertices adjacent only to point vertices, even when their neighbor sets coincide with those of existing vertices. At each point vertex, the change in the number of neighbors with certificate b is zero by (3). All other neighbor-certificate multiplicities are unchanged. Its local view is therefore unchanged. Every retained interval vertex and every leaf added when constructing Gn keeps its original local view. Each copy has the same local view as the vertex it copies. All vertices therefore accept. P The order changes by a εa , which is odd because ℓ is odd. The modified graph thus has odd order. Some connected component has odd order and all its vertices still accept: taking a component changes no local view, and the verifier is not given the graph order. This contradicts soundness. There is therefore no odd cycle in the subgraph of color b, so it is bipartite.

4.3

Counting certificates

Theorem 2. For every sufficiently large even n, there is a connected bipartite n-vertex graph Gn such that every accepting assignment of every correct anonymous radius-one verifier for Even has a certificate of length Ω(log log n). This remains true when correctness is required only on bipartite inputs.

12

P. Montealegre and J. Valenzuela

(a) Auxiliary cycle −E

0

+A

2

1

−D

+B

4

+C

3

Tight Bounds for Anonymous Parity Certification

(b) Before x4

b C

x3

b D

x4 x3

b B x2 x1

A = (0, 1],

(c) After

b E

x2

b A

x1

B = (1, 3], C = (3, 4], D = (2, 4], 1A + 1B + 1C = 1D + 1E .

b C′ b C b B′ b B b A′ b A

E = (0, 2],

Figure 3: An odd cycle gives a parity-changing modification. All five interval vertices have certificate b. The traversal 0, 1, 3, 4, 2, 0 makes A, B, C positive and D, E negative. Delete D, E and add the dashed copies A′ , B ′ , C ′ . Each point vertex loses and gains one neighbor with certificate b, while the order increases by one. Unshown vertices and edges are unchanged. Proof. Let r be the number of distinct certificates on interval vertices. By the preceding argument, their endpoint color classes are bipartite subgraphs whose edge sets partition Km+1 . Lemma 8 therefore gives r ≥ ⌈log(m + 1)⌉. This invokes the classical counting bound; the local-view modification above is what makes it applicable to certificates. If all certificates in P √ the assignment have length at most s, then r ≤ sj=0 2j < 2s+1 . Since m = Θ( n), this yields s ≥ log log(m + 1) − 1 = Ω(log log n).

5

Bounds parameterized by degeneracy

We now prove bounds for certifying Even on d-degenerate graphs. In the general construction, the description of a transfer depends on the order of the bipartite graph used at each layer. We replace this dependence by degeneracy. The key is that every graph Bi between active vertices and their predecessors is a subgraph of the input graph. Its degeneracy is thus at most d, even though a sender may have arbitrarily many receiver neighbors. The certificate format, BFS induction, and conservation check remain unchanged. For the lower bound, we check that the interval modification preserves the promised class.

5.1

Sharing on a d-degenerate bipartite graph

The low-degree case of Lemma 10 already works with any prescribed degree bound. For senders of higher degree, degeneracy gives a receiver coloring with a unique color in each neighborhood, replacing the odd-coloring theorem used in the general proof. Lemma 12. Let d ≥ 1 be an integer and let B = (S ∪ R, EB ) be a finite d-degenerate bipartite graph, with senders S and receivers R. Assume every sender has a neighbor, and put Md = 2d2 +6d−1. There are receiver colors γr ∈ {1, . . . , Md }×{1}, base amounts qs ∈ Q∩[0, 2) with reduced denominator at most 2d, and selected colors as ∈ {0} ∪ ({1, . . . , Md } × {1}) such that f (s, r) = qs + 1γr =as (sr ∈ EB ) satisfies (1): every sender sends an odd integer total, and every receiver receives an integer total. Each label has an O(log(d + 1))-bit encoding. 13

P. Montealegre and J. Valenzuela

Tight Bounds for Anonymous Parity Certification

Proof. Partition the senders by degree: Ssmall = {s ∈ S : degB (s) ≤ 2d},

Slarge = {s ∈ S : degB (s) ≥ 2d + 1}.

Low-degree senders: reuse the rational construction. Apply the maximality and matching argument from Case 1 in the proof of Lemma 10, with degree bound 2d, to B[Ssmall ∪ R]. It gives rational base amounts qs ∈ [0, 2) with integer outgoing totals degB (s)qs and integer incoming totals at all receivers. The reduced denominator divides degB (s) and is therefore at most 2d. The unsatisfied senders, whose outgoing base totals are even, have a matching to distinct receivers ρ(s) ∈ NB (s). Keep the auxiliary graph Ksmall joining each matched receiver ρ(s) to the other neighbors of s, and postpone its coloring. The same counting argument gives |E(Ksmall [X])| ≤ (2d − 1)|X|

(X ⊆ R).

(4)

This part of the proof changes only the degree threshold. High-degree senders: use degeneracy. Orient the whole graph B in a degeneracy ordering, so every vertex has outdegree at most d. This is an auxiliary orientation for choosing the colors; transfers will still go from senders to receivers, regardless of these directions. For s ∈ Slarge , let Os = {r ∈ NB (s) : r → s}. Given B is d-degenerate, at most d edges leave s in the auxiliary orientation, so at most d of its receivers are outside Os . In particular, |NB (s) \ Os | ≤ d and since degB (s) ≥ 2d + 1, it follows that |Os | ≥ d + 1. Each receiver belongs to at most d of the neighborhoods Os , since each membership uses an edge leaving that receiver. These are the two consequences of degeneracy used in the construction: few exceptions at a sender, and bounded participation at a receiver. Figure 4 illustrates how the first bound ensures that a candidate color does not recur outside Os . For each s ∈ Slarge , arbitrarily choose d + 1 candidate receivers Ts ⊆ Os . Candidates may be shared by different senders. Form a graph Klarge on R by joining each candidate in Ts to every other receiver in Os , for every such s. For X ⊆ R, X |E(Klarge [X])| ≤ (d + 1) |Os ∩ X| s∈Slarge (5) ≤ d(d + 1)|X|. The first inequality bounds each sender’s contribution by d + 1 stars on Os ∩ X; counting an edge repeatedly only increases the bound. The second uses the participation bound at receivers. A common coloring and the transfers. Let K = Ksmall ∪ Klarge . The two edge bounds give |E(K[X])| ≤ (d2 + 3d − 1)|X| (X ⊆ R). Every nonempty induced subgraph has a vertex of degree at most 2d2 + 6d − 2. Lemma 7 therefore gives a proper coloring c : R → {1, . . . , Md }. Give each receiver the color γr = (c(r), 1) to use the same ordered-pair format as in Lemma 10. This receiver coloring is proper on K and uses at most Md color pairs. For each satisfied sender in Ssmall , set as = 0. For each unsatisfied one, select as = γρ(s) . The matched receiver has a color unique in NB (s), so this adds exactly one to the even outgoing base total. For a sender in Slarge , its d + 1 candidates have distinct colors, each occurring exactly once in Os . The at most d exceptional receivers in NB (s) \ Os can repeat at most d of those colors. Hence one candidate still has a color unique among all neighbors of s (see Figure 4). Set qs = 0 and select that color as as . This sender sends exactly one unit. 14

P. Montealegre and J. Valenzuela

Tight Bounds for Anonymous Parity Certification

(a) Auxiliary orientation

(b) A color survives the exceptions

Os r1 r2

e1 s

r3

NB (s) \ Os

Os at most d = 2 exceptions

r1

r2

e1

r3

w

e2

e2 Lines are edges of Klarge .

w Ts = {r1 , r2 , r3 }: d + 1 candidates

The color of r3 is unique in NB (s).

Figure 4: Ensuring a unique color when d = 2. In (a), the orientation has at most two edges leaving s; all other receivers lie in Os . The three blue candidates form Ts . In (b), each candidate is adjacent in Klarge to every other receiver of Os , so a proper coloring makes its color unique there. The two exceptional receivers can repeat at most two candidate colors; the double-circled candidate retains a color unique in the whole neighborhood. Arrows in (a) show only the auxiliary orientation, not the direction of transfers. All senders now have odd integer outgoing totals. Incoming totals remain integral because the low-degree base contributions were integral and all corrections are integers. There are O(d2 ) color pairs, whose first coordinates are at most Md and whose second coordinates equal one. Each base amount has denominator at most 2d and numerator less than 4d. Encoding the color coordinates separately, with a tag for the selected color, gives O(log(d + 1)) bits for each label.

5.2

The upper bound and certificate size

Theorem 3. The verifier of Theorem 1 admits O(log d)-bit certificates on every connected even-order d-degenerate graph, for every integer d ≥ 2, and constant-size certificates when d = 1. It remains sound on arbitrary connected graphs and is not supplied with d. Proof. Use exactly the certificate (λ, γ, q, a) and verifier of Theorem 1. In particular, d is not an input or a certificate field, and the verifier does not check degeneracy. For completeness, choose BFS layers in a connected even-order d-degenerate graph. Repeat the same induction from the deepest layer toward the root. At step i, form the bipartite graph Bi from the general construction: the active vertices of Li send to their neighbors in Li−1 . Since Bi is a subgraph of the input graph, it is d-degenerate. Apply Lemma 12 to Bi in place of Lemma 10. Active vertices send odd integer totals; inactive vertices, having received odd integer totals, send zero. Each vertex of the preceding layer receives an integer total. The same induction gives odd integer net outflow at every nonroot vertex, and conservation gives an odd integer net outflow at the root because the graph has even order. As before, each vertex gets its receiver color when the next layer is processed, and its base amount and selected color when its own layer is processed. The layer residue takes two bits. Each receiver color or selected color pair has first coordinate at most Md = O(d2 ) and second coordinate one; a selected color may also be 0. The rational numerator and denominator are O(d). The fixed encoding of the certificate therefore takes O(log(d + 1)) bits in total, including the tag bit for the selected color. Soundness is unchanged: transfers cancel globally for arbitrary certificates, without any degeneracy assumption. 15

P. Montealegre and J. Valenzuela

Tight Bounds for Anonymous Parity Certification

Both upper bounds use the same verifier and encoding. Consequently, on an n-vertex even-order graph of degeneracy at most d, this one verifier admits certificates of O(min{log log(n + 2), log(d + 1)}) bits. No scheme-selection field is needed: the prover may use either completeness construction, and neither n nor d is trusted input.

5.3

A lower bound within the degeneracy promise

The interval construction already has the appropriate degeneracy when its number of points is proportional to d. To obtain a lower bound under a class promise, we must also ensure that the modification used against soundness stays within that class. Theorem 4. For every sufficiently large integer d, there is a connected bipartite graph of even order and degeneracy at most d on which every accepting assignment of every anonymous radius-one certification scheme for Even contains a certificate of length Ω(log log d). This holds even when correctness is required only on connected bipartite d-degenerate graphs. Proof. For a sufficiently large integer d, let m = max{j ≤ d : j ≡ 1 (mod 4)}. Use the interval incidence graph Hm from Section 4; it is connected, bipartite and its order m(m + 3)/2 is even. Every interval vertex has degree at most m. Deleting all interval vertices first and then the independent point vertices gives an m-degeneracy ordering, so Hm is d-degenerate. Fix a verifier correct on connected bipartite d-degenerate graphs and any accepting assignment on Hm . As in the general lower bound, color edge ij of the auxiliary Km+1 by the certificate of yij . Each certificate class must be bipartite. Indeed, the argument in Lemma 11 turns an odd cycle of one color into interval deletions and copies that preserve every local view and change the parity of the order. The modified graph still has the same m point vertices, and every interval vertex still has degree at most m. The same deletion ordering proves that it remains m-degenerate. Every connected component is thus bipartite and d-degenerate. An odd-order component accepted everywhere would contradict soundness even within the promised class. If r distinct certificates occur on interval vertices, Lemma 8 gives r ≥ ⌈log(m + 1)⌉. If all certificates have length at most s, there are fewer than 2s+1 possible strings. Hence s ≥ log log(m + 1) − 1 = Ω(log log(d + 1)), where the asymptotic equality follows from d − 4 < m ≤ d. The argument applies to every accepting assignment and permits a different verifier for each fixed value of d. The witnesses have order Θ(d2 ) and actual degeneracy Θ(d). For t = (m + 1)/2, the first t point vertices and the prefix interval vertices y0j with t ≤ j ≤ m induce Kt,t . Thus their degeneracy is at least t and at most m. The lower bound therefore concerns the structural parameter itself, rather than an unnecessarily large upper estimate for it.

6

A lower bound on a nowhere-dense class

The bounded-degeneracy upper bound shows that many sparse classes admit constant-size certificates. We now show that the general Θ(log log n) bound remains tight on a fixed, subgraph-closed, bipartite nowhere-dense class. Theorem 5. There exists a fixed, subgraph-closed nowhere-dense class of graphs on which certifying Even in the anonymous radius-one model has local complexity Θ(log log n). 16

P. Montealegre and J. Valenzuela

Tight Bounds for Anonymous Parity Certification

We now give a more explicit version of Theorem 5, identifying a concrete nowhere-dense class and providing a quantitative lower bound. Lemma 13. Fix 0 < α < 1, and let 
α Cα = G : G is bipartite and girth(G) ≥ log(|V (G)| + 2) . Then Cα is subgraph-closed and nowhere dense. For every sufficiently large even n, there is a connected n-vertex graph G ∈ Cα such that, for every correct anonymous radius-one verifier for Even on Cα , every accepting assignment on G contains a certificate of length at least 1−α log log n − O(1). 3 Consequently, certifying Even on Cα has local complexity Θ(log log n). We return to the interval idea from Section 4, but use identities between color counts instead of identities between neighborhoods. This lets us change parity by splitting a single vertex, an operation that cannot create a shorter cycle. For a certificate assignment c using at most r distinct strings, identify these strings with [r] := {1, . . . , r} and define the profile
mc (v) = |{w ∈ N (v) : c(w) = a}| a∈[r] . Thus the local view at v is determined by c(v) and mc (v). The same formula defines mc (v) when c is defined only on a set containing N (v). These colorings need not be proper. Lemma 14. Let c be a certificate assignment on a bipartite graph G. Suppose that distinct vertices u, v, w have the same certificate and mc (v) = mc (u) + mc (w). There are a simple bipartite graph G′ of order |V (G)| + 1 and girth at least that of G, and a certificate assignment c′ on G′ , such that every local view in (G′ , c′ ) occurs in (G, c). Proof. Replace v by two vertices v1 , v2 , both carrying c(v). Partition its neighbors within each certificate class so that v1 has profile mc (u) and v2 has profile mc (w). This is possible by the assumed identity. The new vertices imitate u and w. Every retained vertex keeps its certificate and the number of its neighbors with each certificate, since any former neighbor of v is adjacent to exactly one replacement carrying c(v). Put v1 , v2 on the same side of the bipartition as v. Identifying them back into v maps any new cycle to a closed trail in G: no edge repeats, since each old edge was assigned to exactly one replacement. The trail contains a cycle of no greater length, so girth does not decrease. The order increases by one. For example, profiles (1, 1), (1, 2), and (2, 3) allow the last vertex to be split into two vertices imitating the first two, provided all three carry the same certificate. If splitting disconnects the graph, every component still retains all its local views. The next lemma supplies such a triple under every small certificate palette. Its property survives adding leaves at a vertex of P , because none of the old neighborhoods on the Y side changes. Lemma 15. There is an absolute constant C ≥ 1 such that, for all integers r ≥ 2 and g ≥ 4, there is a connected bipartite graph H = (P ∪ Y, E) of girth at least g and order at most 2 2Cgr log r such that every coloring c : V (H) → [r] has distinct vertices u, v, w ∈ Y with the same color and nonzero profiles satisfying mc (v) = mc (u) + mc (w). 17

P. Montealegre and J. Valenzuela

(a) Auxiliary triangle

Tight Bounds for Anonymous Parity Certification

(b) Before the split v

1

1

common certificate 1

:b

u

1 w

:a

j

(c) After the split v1 v2

i

1 x1

k v :a+b

a = (1, 1),

b = (1, 2),

2 x2

1 x3

2 x4

2 x5

a + b = (2, 3),

1 x1

2 x2

1 x3

2 x4

2 x5

|V (G′ )| = |V (G)| + 1.

Figure 5: A monochromatic triangle yields a split. The auxiliary edges ij, jk, ik in (a) have representatives u, w, v with certificate 1 and profiles a, b, a + b. Panels (b,c) show v’s actual neighborhood: v1 and v2 imitate u and w by receiving the two indicated groups. Every old neighbor still sees one vertex with certificate 1. Fills and numeric labels encode certificates. The templates are matched by color counts; their actual neighbors may differ. Unshown vertices and edges are unchanged. Here is the idea of the proof, deferred to Appendix A. An ordered sequence of points gives interval profiles satisfying the exact identity zik = zij + zjk for i < j < k. For each coloring of P , a counting argument finds a sequence whose interval profiles all have a reasonable probability of appearing in random subsets. Sampling supplies many vertices with each of these profiles, simultaneously for all colorings, so deleting one set vertex from each short cycle still leaves every profile available. Select a representative for each interval and color its endpoint pair by the representative’s certificate. A monochromatic triangle gives the required three equally certified vertices. No approximation of color frequencies is needed. Figure 5 illustrates how the triangle gives the split. Proof of Lemma 13. Taking a subgraph does not decrease girth or increase order, so Cα is subgraph-closed. A depth-ρ minor model of K3 yields a cycle of length at most 6ρ + 3: join the endpoints of its three connecting edges inside their branch sets by paths of length at most 2ρ each. These paths have disjoint interiors, since the branch sets are disjoint. For fixed ρ, sufficiently large members of Cα therefore exclude this minor. The remaining members have bounded order and exclude a sufficiently large complete minor. This proves nowhere denseness. Fix a sufficiently large even n, write L = log n, and choose j k 
α  g = log(n + 3) , r = L(1−α)/3 . Then g ≥ 4 and r ≥ 2. Since g = O(Lα ), Lemma 15 gives a graph H with   log |V (H)| = O(gr2 log r) = O L(2+α)/3 log L = o(L). √ Here the last equality uses α < 1. Thus |V (H)| ≤ n for large n. Add leaves at one vertex of P until the order is exactly n. The resulting connected graph Gn lies in Cα and retains the lemma’s profile property. Suppose an accepting assignment c on Gn uses at most r distinct certificates. Its restriction to H gives equally certified vertices u, v, w ∈ Y with mc (v) = mc (u) + mc (w). These are also their profiles in Gn , since adding leaves at P did not change their neighborhoods. Lemma 14 produces an accepted bipartite graph of odd order n + 1 and girth at least g. It has an odd-order component F . This component is a connected accepted no-instance in the same 18

P. Montealegre and J. Valenzuela

Tight Bounds for Anonymous Parity Certification

promised class, since girth(F ) ≥ g ≥ log(|V (F )| + 2)

α

.

This contradicts soundness on Cα . Every accepting assignment thus uses more than r distinct strings. If their lengths are at most s, then r + 1 ≤ 2s+1 − 1. Since r + 1 > L(1−α)/3 , s ≥ log(r + 1) − 1 ≥

1−α log log n − 1. 3

The upper bound follows from Theorem 1. Together with Theorem 1, Lemma 13 implies Theorem 5.

AI disclosure The writing of this paper and the derivation of its results were assisted by AI agents. We used Claude Code (Anthropic) with the model Claude Opus 5.5, and Codex (OpenAI) with the model GPT-6.1 Sol. The authors reviewed all text and results and take full responsibility for them.

References [1] Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun. Complexity landscape for local certification. In 39th International Symposium on Distributed Computing (DISC 2025), volume 356 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi: 10.4230/ LIPIcs.DISC.2025.18. [2] Nicolas Bousquet, Laurent Feuilloley, Jorge Valenzuela, and Sébastien Zeitoun. The local complexity of certifying parity, 2026. DISC 2026; full version. [3] Yi-Jun Chang, Yi-Xuan Lee, and Meng-Tsung Tsai. Local certification of vertex and edge connectivity, 2026. URL https://arxiv.org/abs/2607.13677. [4] Panagiotis Cheilaris, Balázs Keszegh, and Dömötör Pálvölgyi. Unique-maximum and conflict-free coloring for hypergraphs and tree graphs. SIAM Journal on Discrete Mathematics, 27(4):1775–1787, 2013. doi: 10.1137/120880471. [5] Linda Cook, Eun Jung Kim, and Tomáš Masařı́k. A tight meta-theorem for LOCAL certification of MSO2 properties within bounded treewidth graphs. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC 2025), pages 110–120. ACM, 2025. doi: 10.1145/3732772.3733562. [6] Tianjiao Dai, Qiancheng Ouyang, and François Pirot. New bounds for odd colourings of graphs. The Electronic Journal of Combinatorics, 31(4):P4.57, 2024. doi: 10.37236/ 12110. [7] Guy Even, Zvi Lotker, Dana Ron, and Shakhar Smorodinsky. Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM Journal on Computing, 33(1):94–136, 2003. doi: 10.1137/S0097539702431840. [8] Laurent Feuilloley. Introduction to local certification. Discrete Mathematics & Theoretical Computer Science, 23(3), 2021. doi: 10.46298/dmtcs.6280. 19

P. Montealegre and J. Valenzuela

Tight Bounds for Anonymous Parity Certification

[9] Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, and Ioan Todinca. Compact distributed certification of planar graphs. Algorithmica, 83 (7):2215–2244, 2021. doi: 10.1007/s00453-021-00823-w. [10] Laurent Feuilloley, Nicolas Bousquet, and Théo Pierron. What can be certified compactly? compact local certification of MSO properties in tree-like graphs. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC 2022), pages 131–140. ACM, 2022. doi: 10.1145/3519270.3538416. [11] Laurent Feuilloley, Josef Erik Sedláček, and Martin Slávik. Proving there is a leader without naming it, 2025. URL https://arxiv.org/abs/2511.15491. [12] Pierre Fraigniaud, Amos Korman, and David Peleg. Towards a complexity theory for local distributed computing. Journal of the ACM, 60(5):35:1–35:26, 2013. doi: 10.1145/ 2499228. [13] Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. A metatheorem for distributed certification. Algorithmica, 86(2):585–612, 2024. doi: 10.1007/ s00453-023-01185-1. [14] Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing. Theory of Computing, 12(19):1–33, 2016. doi: 10.4086/toc.2016.v012a019. URL https: //theoryofcomputing.org/articles/v012a019/. [15] Philip Hall. On representatives of subsets. Journal of the London Mathematical Society, s1-10(1):26–30, 1935. doi: 10.1112/jlms/s1-10.37.26. [16] Frank Harary, Derbiau Hsu, and Zevi Miller. The biparticity of a graph. Journal of Graph Theory, 1(2):131–133, 1977. doi: 10.1002/jgt.3190010208. [17] Robert Hickingbotham. Odd colourings, conflict-free colourings and strong colouring numbers. Australasian Journal of Combinatorics, 87(1):160–164, 2023. URL https: //ajc.maths.uq.edu.au/pdf/87/ajc_v87_p160.pdf. [18] Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. Distributed Computing, 22(4):215–233, 2010. doi: 10.1007/s00446-010-0095-3. [19] Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms, volume 28 of Algorithms and Combinatorics. Springer, 2012. doi: 10.1007/ 978-3-642-27875-4. [20] János Pach and Gábor Tardos. Conflict-free colourings of graphs and hypergraphs. Combinatorics, Probability and Computing, 18(5):819–834, 2009. doi: 10.1017/ S0963548309990290. [21] Boaz Patt-Shamir and Mor Perry. Proof-labeling schemes: Broadcast, unicast and in between. Theoretical Computer Science, 923:179–195, 2022. doi: 10.1016/j.tcs.2022.05. 006. [22] George Szekeres and Herbert S. Wilf. An inequality for the chromatic number of a graph. Journal of Combinatorial Theory, 4(1):1–3, 1968. doi: 10.1016/S0021-9800(68)80081-X.

20

P. Montealegre and J. Valenzuela

A

Tight Bounds for Anonymous Parity Certification

Proof of Lemma 15

Proof. We need three equally colored vertices whose profiles satisfy an additive identity. Intervals provide the identity; a monochromatic triangle will provide the equal colors. The random construction only has to realize enough interval profiles to make this argument survive the removal of short cycles. Throughout the proof, ln denotes the natural logarithm. Put   D = 3r!, η = (D + 1)−(r+3) , Λ = 16η −1 ln(2rD) , N = (16ΛD3 )g . Let P be a fixed set of N points. Every coloring has a sequence of likely interval profiles. Fix c : P → [r]. For 1 ≤ j ≤ D, let qj (z) be the probability that a uniform j-element subset of P has profile z. There are at most (D + 1)r possible profiles, since each coordinate is an integer between 0 and D. Consequently, a random j-subset has a profile z with qj (z) < η with probability at most (D + 1)r η. Now choose a uniform ordered sequence x1 , . . . , xD of distinct points. For each interval (i, j] of positions, its points form a uniform (j − i)-subset of P . A union bound over fewer than D2 intervals gives
Pr some interval has a profile of probability < η ≤ D2 (D + 1)r η =

D2 < 1. (D + 1)3

P Thus we can fix a sequence for which every interval profile zij = i<k≤j ec(xk ) , with 0 ≤ i < j ≤ D, has probability at least η under sampling a subset of its own size. Here ea is the ath unit vector. These nonzero profiles satisfy zik = zij + zjk

(i < j < k).

(6)

Fix one such sequence for each coloring of P , before making the random graph. The sequence may depend on the coloring; the graph will work for all these choices simultaneously. Realize the profiles, then remove short cycles. For every 1 ≤ j ≤ D, independently sample ΛN uniform j-element subsets of P . Represent each sample by a new vertex adjacent to its elements. Repeated subsets give distinct vertices, so this incidence graph is simple and bipartite. Fix a coloring of P and one interval profile from its fixed sequence. The number X of samples realizing that profile is binomial, with mean µ ≥ ΛN η ≥ 16N ln(2rD). Exponential Markov gives the elementary tail estimate Pr(X < N ) ≤ 2N E[2−X ] ≤ exp(N ln 2 − µ/2) ≤ (2rD)−2N . Indeed, for a binomial variable with M trials and success probability q, E[2−X ] = (1−q/2)M ≤ e−M q/2 . There are rN colorings and fewer than D2 fixed interval targets per coloring. Hence 1 Pr(some target has fewer than N copies) ≤ rN D2 (2rD)−2N ≤ (4r)−N < . 4 Let Z count cycles of length less than g. A cycle of length 2ℓ uses ℓ distinct points and ℓ distinct set vertices. There are at most N ℓ (DΛN )ℓ ordered choices. A sampled set contains two specified distinct points with probability at most 2D2 /N 2 , and different set vertices were sampled independently. Therefore X g N EZ ≤ (2ΛD3 )ℓ ≤ g(2ΛD3 )g = g N ≤ . 8 8 2≤ℓ<g/2

21

P. Montealegre and J. Valenzuela

Tight Bounds for Anonymous Parity Certification

By Markov, Z ≤ N/2 with probability at least 3/4. Some realization therefore has both properties. Delete one set vertex from each short cycle. At most N/2 vertices are deleted, leaving at least N/2 copies of every fixed interval target for every coloring of P . All surviving set vertices keep their neighborhoods. Every component contains a point. Connect the components along a tree by adding paths of length two between points in different components, with fresh internal vertices on the set side. The added edges are bridges. Thus girth is at least g, and the surviving original set vertices still keep their profiles. The final graph is connected and has at most (DΛ + 2)N vertices. A monochromatic triangle gives the split. Every edge coloring of K3r! with r colors has a monochromatic triangle; this follows by induction on r. It is immediate for r = 1. For r ≥ 2, some vertex has at least 3(r − 1)! neighbors joined to it in one color. Either that color occurs on an edge between those neighbors, completing a triangle, or their complete graph uses at most r − 1 colors and induction applies. Take any coloring of the whole constructed graph with at most r colors, and use the sequence fixed for its restriction to P . For every pair 0 ≤ i < j ≤ D, choose a surviving original set vertex yij of profile zij . The representatives can be chosen distinct: fewer than D2 are needed, while every target has at least N/2 > D2 available vertices. Color edge ij of the complete graph on {0, . . . , D} by c(yij ). The preceding Ramsey bound gives a monochromatic triangle i < j < k. Its three representatives have the same color, and (6) gives mc (yik ) = mc (yij ) + mc (yjk ). This is the required triple. Finally, log D = O(r log r),

log Λ = O(r2 log r), 2

log N = O(gr2 log r).

The order bound (DΛ+2)N is therefore at most 2Cgr log r for an absolute constant C ≥ 1.

22

Related documents

• Tight Bounds for Anonymous Parity Certification#1489899
• The impossibility of local skepticism#750548
• Varieties of Grounding Skepticism#73512
• Localizing the Gardam unit: the support geometry of units in F_2[P] and its non-unique-product relatives#1011293
• 47 U.S.C. § 342 — Process for issuing qualified carrier certification#597999