# Level-Cycle Support Findings

This is the corrected version of the boundary-overlap test.

The key modeling change is that a tested cycle must appear in the
level-cycle/seam role: as a bounded face cycle inside the parent
tire's inner outerplanar graph `O`, not as an arbitrary `B_out` or as
the outer-face boundary of `O`.

Executable:

```bash
python3 papers/nested_tire_decompositions_of_plane_triangulations/experiments/level_cycle_support.py
```

## Model

For a parent tire `T = (B_out, O, E_ann)`, enumerate simple bounded
face cycles of `O`.

A cycle is admissible only if:

- it is a bounded face cycle of `O`;
- it is distinct from the outer-face boundary of `O`;
- it is tested in this inner/next-level role, never as an outer
  boundary of a tire at the same level.

For each admissible cycle `C`, compute the set of proper 4-colorings
of `C` that extend to a proper 4-coloring of the parent tire graph.
Supports are normalized under color relabeling and dihedral symmetries
of `C`.

## Capped Validation Run

Command:

```bash
python3 -u papers/nested_tire_decompositions_of_plane_triangulations/experiments/level_cycle_support.py \
  --n-min 3 --n-max 6 --outer-max 5 --inner-max 7 --max-chords 2 --max-paths 30
```

Result:

```text
n=3
  proper C_n colorings          : 24
  distinct level-cycle supports : 1
  most restrictive support      : 24/24
  overlap among max-restrict    : 24

n=4
  proper C_n colorings          : 84
  distinct level-cycle supports : 3
  most restrictive support      : 60/84
  overlap among max-restrict    : 60

n=5
  proper C_n colorings          : 240
  distinct level-cycle supports : 2
  most restrictive support      : 120/240
  overlap among max-restrict    : 120

n=6
  proper C_n colorings          : 732
  distinct level-cycle supports : 13
  most restrictive support      : 252/732
  overlap among max-restrict    : 252
```

The most restrictive admissible `n=4` level-cycle support found here
has size `60/84`, and there is only one worst support type in this
capped window.

Representative `n=4` admissible witness:

```text
size=60
m=3, k=5
path=OOOIIIII
chords=0-2
cycle=(2, 3, 4, 0)
```

Here `O` is a 5-cycle with chord `0-2`.  The tested 4-cycle is the
bounded face cycle `(2,3,4,0)`, not the outer-face boundary of `O`.

## Current Interpretation

With level-cycle admissibility enforced, the first-pass data no longer
supports a zero-overlap obstruction at `n=4`.  In the capped search,
the maximum-restriction support type is unique for `n=3,4,5,6`, so
overlap among maximum restrictions is trivially the whole worst
support.

This is not yet a proof.  The exact all-path `n=4` run with
`--max-chords 2` was stopped after it ran too long interactively.  The
next implementation step should canonicalize outerplanar `O` and
annular paths, or switch to a transfer/DP support computation, before
claiming exhaustive results beyond small capped windows.

## Canonical Tire Quotient

The script now quotients out the dihedral symmetry of the tire on the
rung sequence.  Concretely, a tire `T = (m, k, path, chords)` together
with a chosen level cycle `C` admits an order-`2(m+k)` action:

- cyclic shift `s`: "start counting from rung `s` of the original path".
  This rotates the inner labelling by `-b_s mod k`, where `b_s` is the
  number of inner steps in the first `s` moves; chords and `C` are
  carried by the same shift.
- reflection: traverse the tire in the opposite direction.  The path
  string reverses and each inner label `j` flips to `(k - j) mod k`,
  taking chord `(a, b)` to `((k - a) mod k, (k - b) mod k)` and reversing
  `C`.

The canonical form of `(T, C)` is the lex-min `(path, chords, cycle)`
under that action, with `C` itself further minimised under its own
`D_n` (which the support already quotients out, so this stage is free).

Two `(T, C)` pairs in the same canonical class produce identical
normalised supports, so we compute the support once per class.  Sanity
checks at `n = 3, 4, 5` reproduce the prior capped support sizes
(`24/24`, `60/84`, `120/240`) exactly while reducing raw work by
roughly 20×–25×.

## Exhaustive `n=6` Run

With the canonical quotient in place we can now exhaust a meaningful
window for `n = 6`.  The smallest admissible inner ring is `k = 7`
(a `k`-cycle plus chords cannot host a non-outer bounded `6`-face for
`k < 7`).

Command:

```bash
python3 -u papers/nested_tire_decompositions_of_plane_triangulations/experiments/level_cycle_support.py \
  --n-min 6 --n-max 6 --outer-min 3 --outer-max 6 --inner-min 7 --inner-max 8 \
  --progress --examples 6
```

Result:

```text
n=6
  raw (tire,cycle) combos       : 238506
  canonical (tire,cycle) classes: 9144
  proper C_6 colorings          : 732
  distinct level-cycle supports : 17
  most restrictive support      : 252/732 (1 support type)
  least restrictive support     : 732/732
  overlap among max-restrict    : 252
```

Compared to the earlier `--outer-max 5 --inner-max 7 --max-chords 2
--max-paths 30` capped run, the distinct-support count climbs from
`13` to `17`, but the **minimum support size is unchanged at `252/732`
and is still realised by a unique support type**.  The minimum is
witnessed by the same minimal-`O` configuration that already showed up
at smaller `n`:

```text
size=252
m=3, k=7
chords=0-2
cycle=(2, 3, 4, 5, 6, 0)
```

i.e. the bounded `6`-face of a `7`-cycle with one chord, sitting inside
the thinnest annulus `(m=3)`.  Adding outer length (`m` up to `6`),
inner length (`k` up to `8`), and unrestricted chord sets produces
strictly *less* restrictive supports — never a new floor.

### Wider sweep: `outer 3..7, inner 7..9`

Command:

```bash
python3 -u papers/nested_tire_decompositions_of_plane_triangulations/experiments/level_cycle_support.py \
  --n-min 6 --n-max 6 --outer-min 3 --outer-max 7 --inner-min 7 --inner-max 9 \
  --progress --examples 6
```

Result:

```text
n=6
  raw (tire,cycle) combos       : 5662518
  canonical (tire,cycle) classes: 186818
  proper C_6 colorings          : 732
  distinct level-cycle supports : 19
  most restrictive support      : 252/732 (1 support type)
  least restrictive support     : 732/732
  overlap among max-restrict    : 252
```

Adding `k = 9` and `m = 7` brings 2 new distinct supports (`17 → 19`),
**both strictly above the floor**.  The most restrictive support is
**still `252/732`, still unique, and still realised by the same
minimal-`O` witness** (`m=3, k=7, chord=0-2, cycle=(2,3,4,5,6,0)`).
The `m = 3` configurations dominated the floor in every (`m`, `k`)
sweep examined.

### What this changes

- The "most restrictive support is unique" claim for `n = 6` is now
  backed by an exhaustive (not capped) sweep over `m ∈ [3, 7]`,
  `k ∈ [7, 9]`, all chord sets, all annular paths.
- The earlier-feared zero-overlap obstruction at `n = 4` does not
  reappear at `n = 6` either: overlap among maximum-restriction
  supports is trivially the whole worst support, because there is only
  one worst support.
- The witness for the floor is structurally the same across
  `n = 3, 4, 5, 6`: a single chord on a `(n+1)`-cycle, embedded in the
  thinnest annulus, with the tested cycle taken as the bounded
  `n`-face.  That stability is suggestive (it hints that the worst
  level-cycle support is governed by a small canonical configuration)
  but is not yet a theorem.

### Floor-stability-in-`m` conjecture

Across every searched `n`, the floor witness has been `m = 3`.  This
is consistent with a **support-monotonicity** picture: subdividing any
outer or annular edge of an `m = 3` floor witness produces an `m = 4`
tire whose support strictly contains the original (the new degree-`2`
vertex adds coloring freedom, and the subdivided edge's endpoints are
no longer adjacent, so they may share a color).  By induction the
floor over `m ≥ 3` is bounded above by the `m = 3` floor.

The empirical run confirms this bound is tight up to `m ≤ 7, k ≤ 9` at
`n = 6`: no `m ≥ 4` tire produced a support strictly smaller than the
`m = 3` floor.  A theorem-style statement would be:

> **(Conjecture)** For every `n`, every `k ≥ n + 1`, and every chord
> set on `C_k` containing an `n`-face, the level-cycle support floor
> over all annular paths and all `m ≥ 3` is achieved at `m = 3`.

If true, this collapses the exhaustive search to `m = 3` only and
opens the door to closed-form support computation for the worst case.
The obstruction to a quick proof is exotic `m ≥ 4` configurations not
reachable by subdivision from an `m = 3` floor witness — none has
appeared empirically, but their non-existence is not yet ruled out.

#### Skip-`m=3` sweep (partial)

To probe the conjecture more directly we ran a "skip-`m=3`" sweep
explicitly excluding `m = 3` from the search:

```bash
python3 -u papers/nested_tire_decompositions_of_plane_triangulations/experiments/level_cycle_support.py \
  --n-min 6 --n-max 6 --outer-min 4 --outer-max 10 --inner-min 7 --inner-max 9 \
  --progress
```

The sweep ran for `11h 49m` and was terminated partway through `m = 8,
k = 9` at chord-set #6 of the 2-chord block (raw=6.45M canonical=223k).
Throughout the run --- across `m ∈ [4, 7]` exhaustively and `m = 8`
partially --- the distinct-support count stayed locked at **`13`**
(vs `19` for the full `m ∈ [3, 7]` run).  The six missing support
types are precisely the ones with `m = 3`-only witnesses, including
the unique `252/732` floor.

Conclusion of the partial run: no support of size `≤ 252` appeared
under `m ≥ 4` in any configuration searched, and the support count
saturated early, suggesting the support landscape for `m ≥ 4` is
strictly looser than for `m = 3` even as `m` grows.  The conjecture is
not falsified by any data we have; pushing `m` to `9` or `10` is
left as future work (path-count growth makes it expensive: `m = 10,
k = 9` alone has `C(19, 10) ≈ 92{,}000` paths per chord set).

### Floor-containment conjecture — refuted

Floor-stability bounds the *size* of the worst-case support but not
its content.  For the tire-tree compatibility argument, what would
have closed the loop is a containment statement:

> **(Conjecture, refuted)** For every `n`, the unique floor support
> `F_n` is a *subset* of every admissible level-cycle support.  Every
> level-cycle coloring that the `m = 3` floor witness allows is also
> allowed by every other tire.

The `check_floor_containment` helper in `level_cycle_support.py`
tests this directly on the computed supports.  The conjecture **fails
at `n = 4` and `n = 6`**:

```text
n=4: floor (size 60) is NOT a subset of 1 of 2 other supports
  missing: floor coloring (1, 2, 1, 2) absent from support of size 72

n=6: floor (size 252) is NOT a subset of 11 of 16 other supports
  missing: floor coloring (1, 3, 2, 1, 3, 2) absent from support of size 708
  missing: floor coloring (2, 3, 2, 1, 3, 1) absent from support of size 492
  missing: floor coloring (2, 3, 2, 3, 2, 3) absent from support of size 720
```

(`n = 3` is trivial — only one support type.  `n = 5` happens to
satisfy containment in the searched window but only against a single
other support, so the data is too thin to be evidence either way.)

The missing colorings cluster on **bipartite alternations**
(`(1,2,1,2)`, `(2,3,2,3,2,3)`) and **3-periodic patterns**
(`(1,3,2,1,3,2)`).  These are the most "structured" colorings of `C_n`
— colorings the thin `m = 3` annulus is free to produce, but other
tires (with larger annulus / heavier chord patterns) actively forbid
because their interior forces additional colour variety.

**Consequence.**  The simple structural shortcut — "all supports
contain a common floor, hence pairwise intersections are trivially
non-empty" — does not hold.  Same-`n` compatibility (which by `4CT` is
still forced to hold) cannot be reduced to a single containment fact;
it requires a finer structural analysis of *which* colorings sit in
*which* supports, or a different shortcut entirely.
