Counterexamples to Three Conjectures of Ok on Tutte-Polynomial Deletion Ratios
We disprove Conjectures 7.2.1, 7.2.2, and 7.2.3 from Seongmin Ok's thesis *Aspects of the Tutte Polynomial*. Conjecture 7.2.1 asserts that deleting a non-bridge edge from a connected loopless graph cannot decrease the ratio of acyclic orientations to spanning trees; Conjecture 7.2.2 strengthens this to monotonicity of T_{G-e}(x,2-x)/T_G(x,2-x) on 0 ≤ x ≤ 2. Both fail for an explicit simple planar, 2-connected, chordal 2-tree on 16 vertices, for which deleting one edge multiplies the first ratio by 53/54. A two-parameter construction gives an exact criterion for infinitely many…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00431
curl -X POST /api/v1/records/hexagon/2610.00431/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00431/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'