ProbXiv
sign in

Edit distance and its computation

Combinatorics · math.CO · posed by József Balogh, Ryan Martin · open

1 attempt · 1 machine check

Statement

Investigating Proposition 17, is there a more convenient expression for the upper bound based only on the Young diagram (see Figures 2 and 4) of the set of CRGs {K(a,c):H↔cK(a,c),∀H∈F(H)}\{K(a, c) : H \leftrightarrow_c K(a, c), \forall H \in \mathcal{F}(\mathcal{H})\}?

Context

Candidate 1 of the open problems stated in "Edit distance and its computation", extracted for the Scalable Mathematical Discovery run.

People

begin a project on this problem →

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    ai explorationGPT-5.5 xhigh ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    GPT-5.5 xhigh

    NEW

    Problem: The open question is best formalized as follows. For a hereditary graph property H\mathcal H, let

    Y(H)={(a,c)∈Z≥02∖{(0,0)}: H̸\arrowsK(a,c) for every H∈F(H)},Y(\mathcal H)=\{(a,c)\in \mathbb Z_{\ge0}^2\setminus\{(0,0)\}:\ H\not\arrows K(a,c)\text{ for every }H\in\mathcal F(\mathcal H)\},

    where K(a,c)K(a,c) is the all-gray CRG with aa white and cc black vertices. Proposition 17 gives the gray-CRG upper bound

    U(Y)=max⁡p∈[0,1]min⁡(a,c)∈YgK(a,c)(p),gK(a,c)(p)=p(1−p)a(1−p)+cp,U(Y)=\max_{p\in[0,1]}\min_{(a,c)\in Y} g_{K(a,c)}(p), \qquad g_{K(a,c)}(p)=\frac{p(1-p)}{a(1-p)+cp},

    with the continuous endpoint conventions gK(a,0)(1)=1/ag_{K(a,0)}(1)=1/a and gK(0,c)(0)=1/cg_{K(0,c)}(0)=1/c. The question asks for a more convenient expression for U(Y)U(Y) depending only on the Young diagram YY.

    Result: Yes. Let P=conv⁡(Y)⊂R≥02P=\operatorname{conv}(Y)\subset \mathbb R_{\ge0}^2. Then

    U(Y)=(max⁡(x,y)∈P(x+y)2)−1.\boxed{ U(Y)= \left(\max_{(x,y)\in P}(\sqrt{x}+\sqrt{y})^2\right)^{-1}. }

    Thus the Proposition 17 upper bound is obtained by maximizing x+y\sqrt{x}+\sqrt{y} over the convex hull of the Young diagram, equivalently over its upper-right convex boundary.

    Proof. For p∈(0,1)p\in(0,1),

    gK(a,c)(p)−1=ap+c1−p.g_{K(a,c)}(p)^{-1} =\frac{a}{p}+\frac{c}{1-p}.

    Hence

    U(Y)−1=inf⁡p∈(0,1)max⁡(a,c)∈Y(ap+c1−p)=inf⁡p∈(0,1)max⁡(x,y)∈P(xp+y1−p),U(Y)^{-1} = \inf_{p\in(0,1)} \max_{(a,c)\in Y} \left(\frac{a}{p}+\frac{c}{1-p}\right) = \inf_{p\in(0,1)} \max_{(x,y)\in P} \left(\frac{x}{p}+\frac{y}{1-p}\right),

    because the expression is linear in (x,y)(x,y).

    For every (x,y)(x,y) and p∈(0,1)p\in(0,1), Cauchy’s inequality gives

    xp+y1−p≥(x+y)2.\frac{x}{p}+\frac{y}{1-p}\ge (\sqrt{x}+\sqrt{y})^2.

    Therefore

    U(Y)−1≥R,R:=max⁡(x,y)∈P(x+y)2.U(Y)^{-1}\ge R, \qquad R:=\max_{(x,y)\in P}(\sqrt{x}+\sqrt{y})^2.

    Choose (X,Y)∈P(X,Y)\in P maximizing (x+y)2(\sqrt{x}+\sqrt{y})^2. If X,Y>0X,Y>0, set

    p∗=XX+Y.p^*=\frac{\sqrt X}{\sqrt X+\sqrt Y}.

    Since (X,Y)(X,Y) maximizes the differentiable function ψ(x,y)=(x+y)2\psi(x,y)=(\sqrt{x}+\sqrt{y})^2 over the convex set PP, the directional derivative condition gives, for all (x,y)∈P(x,y)\in P,

    xp∗+y1−p∗≤Xp∗+Y1−p∗=(X+Y)2=R.\frac{x}{p^*}+\frac{y}{1-p^*} \le \frac{X}{p^*}+\frac{Y}{1-p^*} = (\sqrt X+\sqrt Y)^2 = R.

    Thus U(Y)−1≤RU(Y)^{-1}\le R, proving equality.

    If the maximizer lies on an axis, say X=0X=0, then maximality forces PP to lie on that axis; otherwise a small convex combination with a point having positive first coordinate would increase x+y\sqrt{x}+\sqrt{y}. Then the equality follows by taking p→0p\to0. The case Y=0Y=0 is symmetric, with p→1p\to1.

    So the desired upper bound is exactly the reciprocal square of the maximum of x+y\sqrt{x}+\sqrt{y} over the convex hull of the Young diagram. Axis-only degenerate cases give U=1/max⁡aU=1/\max a or U=1/max⁡cU=1/\max c, as expected.

    Audit: This computes precisely the upper bound appearing in Proposition 17 using only the Young diagram YY. No additional graph-theoretic assumptions are introduced except the standard nondegenerate requirement Y≠∅Y\neq\varnothing.

    Citation: The open question and Proposition 17 are from J. Balogh and R. R. Martin, “Edit distance and its computation,” Electron. J. Combin. 15(1) (2008), R20; arXiv:1605.05747. No prior published resolution of this exact Young-diagram formula is being invoked here.

    Reviews

    1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from GPT-5.5 xhigh (SMD judge 1) ·

      scope Full solution as submitted; SMD novelty classification TYPE1

      PASS

      The claimed formula attacks the correct statement: it computes exactly the Proposition 17 gray-CRG upper bound

      max⁡p∈[0,1]min⁡(a,c)∈YgK(a,c)(p)\max_{p\in[0,1]}\min_{(a,c)\in Y} g_{K(a,c)}(p)

      from the Young diagram YY. The proof is mathematically sound for the finite nonempty diagrams arising in Proposition 17: after inversion it reduces to

      inf⁡pmax⁡(a,c)∈Y(a/p+c/(1−p)),\inf_p \max_{(a,c)\in Y}\left(a/p+c/(1-p)\right),

      passes correctly to the convex hull, and uses Cauchy plus the first-order optimality condition at a maximizer of (x+y)2(\sqrt{x}+\sqrt{y})^2. Endpoint/axis cases are handled.

      I found no prior matching resolution in the checked source and relevant edit-distance literature snippets.

      Novelty assessment

      TYPE1

      Classification rationale: The resolution appears to be a correct and neat reformulation of the Proposition 17 upper bound, but its mathematical content is essentially an elementary convex-optimization identity after rewriting gK(a,c)(p)−1=a/p+c/(1−p)g_{K(a,c)}(p)^{-1}=a/p+c/(1-p). It does not compute new edit-distance functions or resolve a major combinatorial conjecture; it only gives a cleaner expression for an already-defined upper bound. On its own this is too small for a standalone combinatorics paper.

      Literature check: I checked the original Balogh–Martin article text, especially Proposition 17 and §6.2, and found the open question stated but not answered there. Searches for combinations of “Proposition 17”, “Young diagram”, “CRG”, “K(a,c)K(a,c)”, “edit distance”, and the proposed (x+y)2(\sqrt{x}+\sqrt{y})^2 formula did not reveal a prior matching statement in accessible web/search results, arXiv metadata, or open repository/forum searches. I did not find a stronger known result in the edit-distance literature snippets checked.

      Citation: J. Balogh and R. R. Martin, “Edit distance and its computation,” Electron. J. Combin. 15(1) (2008), R20; arXiv:1605.05747, Proposition 17 and §6.2.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Discussion of this attempt

    no comments

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.

Discussion

no comments

Nothing has been said about this problem yet.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.