How deep a hole is

Move a parity mismatch around a network without removing the global contradiction.

From John Cullen’s knotlab guide

Explore the idea

Move the mismatch. Keep the contradiction.

Each vertex asks its incident edge bits to sum to its fixed charge, modulo two. Only vertex 1 has charge 1. Flip a path of edges to move the one failed equation to another vertex.

Move the mismatch to

Teal edges carry 1; grey edges carry 0. Amber marks the vertex whose equation fails.

Vertex 1 fails. All other five vertices satisfy their equations.

The total charge is odd, but summing every edge equation counts each edge twice. No assignment can satisfy the whole cycle. This small example illustrates moving a local mismatch; the width theorem in the text treats larger graphs.

The intuition. Put a parity knot at every vertex of a graph, sharing the graph's edges as distinctions: each vertex asks its edges to sum to a charge. Such a network is impossible exactly when the total charge is odd. That is a hole, but every small window of the network looks perfectly consistent, since the odd unit of charge can be pushed anywhere by flipping edges along a path. So how much of the network must an observer hold at once to see the hole? The answer is a width of the graph: the charge has to be carried across the widest boundary of the best sweep.

These networks are Tseitin formulas, and "how much an observer must hold" becomes the degree of a refutation.

Graph terms. Three terms about graphs appear below. Lay a graph's vertices out in a row: each gap in the row is crossed by some edges, the layout's width is the most edges crossing one gap, and the cutwidth is the least width of any layout. The maximum degree is the most edges at one vertex. The ±1 encoding writes each bit as +1 or −1 instead of 0 or 1.

Reasoning mod 2 sees the hole at once. Summing every vertex's equation counts each edge twice, so a refutation of the size of one knot exists.
Every other field needs the toggle width. Proved (note): over every field of characteristic other than 2, the Nullstellensatz degree of the Tseitin formula, written clause by clause, equals the toggle width of the graph: the cheapest way to grow the empty vertex set into the whole graph by adding or removing one vertex at a time, where each step costs the edges it must keep track of. On graphs of maximum degree at most three this is exactly cutwidth + 1. In the ±1 encoding, with degree measured after reduction, it is exactly the cutwidth. The upper bound sweeps the charge across a layout, and the lower bound is a design whose values are signed sums over cuts. See notes/tseitin-nullstellensatz-degree.

Reading. A hidden bit has a depth: the width an observer must hold to carry it to where it shows. Holes made by loops of witnesses (lesson 4.5) are shallow, and local reasoning sees them. Holes made by charges are as deep as the graph's layout is wide, unless the reasoning computes in the charge's own group. Related results for other proof systems, with tree layouts in place of linear ones, are in the full record: see "Holes, depth and Tseitin proof complexity" in RESULTS.md.

PYTHONPATH=tools python3 -m knotlab depth