# Medial Tire Restriction Findings

Question: among possible full medial tire graphs, which examples most
restrict the inner boundary coloring relative to the outer boundary
coloring?

## Model

The experiment uses the ambient full-medial tread model.

- Annular medial vertices form a cycle `A_0, ..., A_{n-1}`.
- Each annular face contributes one boundary-medial vertex `B_i`.
- `B_i` is adjacent to `A_i` and `A_{i+1}`.
- `B_i` is tagged `O` or `I` according to whether the corresponding
  primal boundary edge lies on the outer or inner boundary.

Boundary states are quotient by color permutations only.  Boundary
order is fixed: rotations and reversals are not identified.

Inner chords of the inner outerplanar graph do not affect this ambient
full medial tire graph, because they are not incident to annular tread
faces.

## Metrics

For the quotient transfer relation

```text
R_T subset outer_state_orbits x inner_state_orbits
```

the script reports:

- `min_outer_extensions`: minimum number of compatible inner state
  orbits over realized outer state orbits.
- `avg_outer_extensions`: average number of compatible inner state
  orbits over realized outer state orbits.
- `relation_density_all`: `|R_T|` divided by all possible outer/inner
  state orbit pairs.
- `blocked_outer_orbits`: number of outer boundary state orbits that
  are not compatible with any inner boundary state orbit.
- `blocked_inner_orbits`: number of inner boundary state orbits that
  are not compatible with any outer boundary state orbit.

## Exhaustive Sweep Through 10 Faces

Command:

```bash
python3 papers/medial_tire_decompositions_of_plane_triangulations/experiments/medial_tire_restriction_search.py --exhaustive --min-faces 6 --max-faces 10 --limit 3
```

Result:

```text
graphs analyzed: 1974
boundary states quotient by color permutations only; no rotations or reversals

most restrictive by min_outer_extensions
  types=IIIOOO
    faces=6 outer=3 inner=3 outer_orbits=5 inner_orbits=5
    realized_outer=4 realized_inner=4 relation=10
    blocked_outer=1 (0.200) blocked_inner=1 (0.200)
    min_outer_extensions=1 avg_outer_extensions=2.500
    density_all=0.400000 density_realized_outer=0.500000
    worst_outer_states=((0, 1, 2),)
  types=IIOIOO
    faces=6 outer=3 inner=3 outer_orbits=5 inner_orbits=5
    realized_outer=5 realized_inner=5 relation=9
    blocked_outer=0 (0.000) blocked_inner=0 (0.000)
    min_outer_extensions=1 avg_outer_extensions=1.800
    density_all=0.360000 density_realized_outer=0.360000
    worst_outer_states=((0, 0, 1), (0, 1, 2))
  types=IIOOIO
    faces=6 outer=3 inner=3 outer_orbits=5 inner_orbits=5
    realized_outer=5 realized_inner=5 relation=9
    blocked_outer=0 (0.000) blocked_inner=0 (0.000)
    min_outer_extensions=1 avg_outer_extensions=1.800
    density_all=0.360000 density_realized_outer=0.360000
    worst_outer_states=((0, 1, 1), (0, 1, 2))

most restrictive by avg_outer_extensions
  types=IIOOOO
    faces=6 outer=4 inner=2 outer_orbits=14 inner_orbits=2
    realized_outer=8 realized_inner=2 relation=8
    blocked_outer=6 (0.429) blocked_inner=0 (0.000)
    min_outer_extensions=1 avg_outer_extensions=1.000
    density_all=0.285714 density_realized_outer=0.500000
  types=IOIOOO
    faces=6 outer=4 inner=2 outer_orbits=14 inner_orbits=2
    realized_outer=9 realized_inner=2 relation=9
    blocked_outer=5 (0.357) blocked_inner=0 (0.000)
    min_outer_extensions=1 avg_outer_extensions=1.000
    density_all=0.321429 density_realized_outer=0.500000
  types=IOOIOO
    faces=6 outer=4 inner=2 outer_orbits=14 inner_orbits=2
    realized_outer=9 realized_inner=2 relation=9
    blocked_outer=5 (0.357) blocked_inner=0 (0.000)
    min_outer_extensions=1 avg_outer_extensions=1.000
    density_all=0.321429 density_realized_outer=0.500000

most restrictive by relation_density_all
  types=IIIIIIIIIO
    faces=10 outer=1 inner=9 outer_orbits=1 inner_orbits=3281
    realized_outer=1 realized_inner=171 relation=171
    blocked_outer=0 (0.000) blocked_inner=3110 (0.948)
    min_outer_extensions=171 avg_outer_extensions=171.000
    density_all=0.052118 density_realized_outer=0.052118
```

## Random Sweep Through 14 Faces

Command:

```bash
python3 papers/medial_tire_decompositions_of_plane_triangulations/experiments/medial_tire_restriction_search.py --samples 5000 --max-faces 14 --limit 3
```

Result:

```text
graphs analyzed: 3227

most restrictive by min_outer_extensions
  types=IIIOOO
    min_outer_extensions=1 avg_outer_extensions=2.500
    density_all=0.400000 density_realized_outer=0.500000
  types=IIOIOO
    min_outer_extensions=1 avg_outer_extensions=1.800
    density_all=0.360000 density_realized_outer=0.360000
  types=IIOOIO
    min_outer_extensions=1 avg_outer_extensions=1.800
    density_all=0.360000 density_realized_outer=0.360000

most restrictive by avg_outer_extensions
  types=IIOOOO
    min_outer_extensions=1 avg_outer_extensions=1.000
    density_all=0.285714 density_realized_outer=0.500000
  types=IOIOOO
    min_outer_extensions=1 avg_outer_extensions=1.000
    density_all=0.321429 density_realized_outer=0.500000
  types=IOOIOO
    min_outer_extensions=1 avg_outer_extensions=1.000
    density_all=0.321429 density_realized_outer=0.500000

most restrictive by relation_density_all
  types=IIIOIIIIIIIIII
    faces=14 outer=1 inner=13 relation=2731
    min_outer_extensions=2731 avg_outer_extensions=2731.000
    density_all=0.010278 density_realized_outer=0.010278
  types=OOOOOOOIOOOOOO
    faces=14 outer=13 inner=1 relation=2731
    min_outer_extensions=1 avg_outer_extensions=1.000
    density_all=0.010278 density_realized_outer=1.000000
  types=IIIOOIIIIIIIII
    faces=14 outer=2 inner=12 relation=2048
    min_outer_extensions=683 avg_outer_extensions=1024.000
    density_all=0.011561 density_realized_outer=0.011561
```

## Interpretation

The most restrictive small examples for extension counts appear at six
annular faces.  Alternating or clustered `O/I` boundary-face patterns
with a small boundary on one side can force each realized outer state
to a single inner orbit.

The raw density metric favors highly unbalanced boundaries, such as one
outer boundary state position and many inner positions.  This may be a
less useful notion of "worst case" unless boundary sizes are fixed or
the density is normalized within a fixed `(outer, inner)` size class.

The blocked-state metrics make the asymmetry explicit.  For instance,
`IIIOOO` blocks one of the five possible outer state orbits, while
`IIOIOO` and `IIOOIO` block none but still contain outer states with a
unique compatible inner state orbit.  Highly unbalanced cases can block
most state orbits on the larger boundary simply because the annular
cycle has far fewer colorings than the unconstrained ordered boundary.
