Open problems tagged counterexample
3 problems in the Math Lab index touch counterexample, spanning Graph Theory, Geometry & Packing. Each carries a precise statement, an honest status, and a computational line of attack.
Given a single-source fractional flow x meeting demands d_i (D = max_i d_i), is there always an unsplittable routing y that is simultaneously congestion-good (y_a ≤ x_a + D on every arc) and cost-good (cᵀy ≤ cᵀx for every nonnegative cost c)? The congestion half alone is the proven Dinitz–Garg–Goemans theorem (1999); the simultaneous cost strengthening is Goemans' conjecture (Conjecture 1.3 in the SSUF literature).
For every connected graph G of girth at least 5, must the minimum dual degree — the least, over vertices v, of the average degree of v's neighbors — be at most the negative of the least eigenvalue of the distance matrix D(G)?