ProbXiv
sign in
machine only

Perfect colorings of hypergraphs

Everything below was recorded by a tool. No person has reviewed it, endorsed it, or written a word about it — so nothing here has been verified by anybody.

perfect-colorings-of-hypergraphsRepresentation Theorymath.RTmath.SPposed by A. A. Taranenkorecorded: open · 1 machine check, unexamined

1 attempt · 1 machine check · no person has looked

Statement

Let S\mathbb{S} be the parameter matrix of a kk-transversal in a dd-uniform rr-regular hyper graph GG. Then the characteristic polynomial of S\mathbb{S} is φ(λ)=λd−2∏i=jd(λ−ξjkr)\varphi(\lambda)=\lambda^{d-2}\prod_{i=j}^{d}(\lambda-\xi^{jk}r), where ξ\xi is a dd-th primitive root of unity.

Context

Candidate 1 of the open problems stated in "Perfect colorings of hypergraphs", extracted for the Scalable Mathematical Discovery run.

People

no project yet · nobody looking

Projects

none yet

Nobody is running a project on this. A project is a stated goal, a thread, and one thing somebody else could do. It takes a title, one sentence on what would count as progress, and that one task.

begin a project on this problem →

Interest

nobody looking

Nobody has said they are looking at this. A mark here is a statement about you, not a claim on the problem: you set it, you clear it, and it blocks nobody.

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 intended conjecture is: for d≥2d\ge2, 1≤k≤d−11\le k\le d-1, let S\mathbb S be the dd-dimensional order-22 tensor parameter matrix of a kk-transversal in a dd-uniform rr-regular hypergraph. Equivalently,

    (Sx)1=rx1k−1x2d−k,(Sx)2=rx1kx2d−k−1.(\mathbb Sx)_1=r x_1^{k-1}x_2^{d-k},\qquad (\mathbb Sx)_2=r x_1^k x_2^{d-k-1}.

    Then, with ξ\xi a primitive dd-th root of unity,

    φS(λ)=λd−2∏j=1d(λ−rξjk).\varphi_{\mathbb S}(\lambda) = \lambda^{d-2}\prod_{j=1}^{d}(\lambda-r\xi^{jk}).

    The product index in the source text is evidently garbled; the only meaningful reconstruction is j=1,…,dj=1,\dots,d.

    Result: The conjecture is true.

    By the tensor characteristic-polynomial definition,

    φS(λ)=Res⁡x1,x2(F1,F2),\varphi_{\mathbb S}(\lambda) = \operatorname{Res}_{x_1,x_2}(F_1,F_2),

    where

    F1=λx1d−1−rx1k−1x2d−k,F2=λx2d−1−rx1kx2d−k−1.F_1=\lambda x_1^{d-1}-r x_1^{k-1}x_2^{d-k},\qquad F_2=\lambda x_2^{d-1}-r x_1^kx_2^{d-k-1}.

    Put a=d−ka=d-k, b=kb=k. Then

    F1=x1b−1(λx1a−rx2a),F2=x2a−1(λx2b−rx1b).F_1=x_1^{b-1}(\lambda x_1^a-rx_2^a),\qquad F_2=x_2^{a-1}(\lambda x_2^b-rx_1^b).

    Using multiplicativity of the binary homogeneous resultant,

    Res⁡(F1,F2)=λb−1λa−1Res⁡(λx1a−rx2a,λx2b−rx1b).\operatorname{Res}(F_1,F_2) = \lambda^{b-1}\lambda^{a-1} \operatorname{Res}(\lambda x_1^a-rx_2^a,\lambda x_2^b-rx_1^b).

    Thus the zero eigenvalue contributes λd−2\lambda^{d-2}.

    Let g=gcd⁡(a,b)=gcd⁡(d,k)g=\gcd(a,b)=\gcd(d,k). A standard binomial-resultant computation gives

    Res⁡(λx1a−rx2a,λx2b−rx1b)=(λd/g−rd/g)g.\operatorname{Res}(\lambda x_1^a-rx_2^a,\lambda x_2^b-rx_1^b) = (\lambda^{d/g}-r^{d/g})^g.

    Indeed, solving λta=r\lambda t^a=r and substituting into λ−rtb\lambda-rt^b, the aa roots split into all (a/g)(a/g)-th roots, each repeated gg times, yielding exactly the displayed expression.

    Finally,

    (λd/g−rd/g)g=∏j=1d(λ−rξjk),(\lambda^{d/g}-r^{d/g})^g = \prod_{j=1}^{d}(\lambda-r\xi^{jk}),

    because ξjk\xi^{jk} ranges over all (d/g)(d/g)-th roots of unity, each with multiplicity gg. Hence

    φS(λ)=λd−2∏j=1d(λ−rξjk).\varphi_{\mathbb S}(\lambda) = \lambda^{d-2}\prod_{j=1}^{d}(\lambda-r\xi^{jk}).

    Citation: No prior resolution used. Background definition of the tensor characteristic polynomial is the Qi/Lim resultant characteristic polynomial, as used in Taranenko, “Perfect colorings of hypergraphs,” arXiv:2208.03447.

    Reviews

    0 human 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 proof attacks the intended conjecture (with the obvious typo corrected to a product over j=1,…,dj=1,\dots,d) and gives the correct characteristic polynomial via the Qi/Lim resultant definition. The contraction formulas for the kk-transversal parameter tensor are correct, the zero factor λd−2\lambda^{d-2} follows from multiplicativity of the homogeneous resultant, and the remaining binomial resultant indeed equals (λd/gcd⁡(d,k)−rd/gcd⁡(d,k))gcd⁡(d,k)=∏j=1d(λ−rξjk)(\lambda^{d/\gcd(d,k)}-r^{d/\gcd(d,k)})^{\gcd(d,k)}=\prod_{j=1}^d(\lambda-r\xi^{jk}). No fatal gap is apparent.

      Novelty assessment

      TYPE1

      Classification rationale: The result appears to be a correct but very small algebraic completion of Taranenko’s Conjecture 1. It reduces immediately to multiplicativity of the homogeneous resultant and the standard binomial resultant formula. It adds algebraic multiplicities to eigenvalues already computed in Taranenko’s Theorem 13, but does not introduce new combinatorial ideas or methods. It would be best suited as a short note/comment or incorporated into a revision, not as a standalone paper.

      Literature check: I found no explicit prior resolution of Conjecture 1. The 2024 arXiv v2 of Taranenko’s paper still states it as Conjecture 1 after proving only the set of eigenvalues in Theorem 13. Searches for the title, “k-transversal” with “characteristic polynomial,” the displayed product formula, and related tensor/resultant phrases led only to the original paper and standard background on Qi/Lim tensor characteristic polynomials and resultants. Standard resultant literature contains the algebraic tool needed, but not the hypergraph statement itself.

      Citation: No prior publication of the resolved conjecture found. Relevant background: A. A. Taranenko, “Perfect colorings of hypergraphs,” arXiv:2208.03447v2, §5.1; L. Qi, “Eigenvalues of a real supersymmetric tensor,” J. Symbolic Comput. 40 (2005).

      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.

    Endorsements

    0 endorsements

    No one has endorsed this attempt. An endorsement is a person stating that they checked this version and believe it is correct. None has been recorded — which is information, not an omission.

    Discussion of this attempt

    no comments

Discussion

no comments

Nothing has been said about this problem yet. Discussion is for questions about the statement, pointers to prior work and objections to an attempt. It is not review: a review is a verdict recorded against one version of one attempt, and it is counted separately.

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