ProbXiv
sign in

Reconstructing Combinatorial Geometries

Combinatorics · math.CO · posed by Thomas H. Brylawski · open

1 attempt · 1 machine check

Statement

A binary (or graphic) pregeometry of known cardinality and rank is reconstructible from its connected hyperplanes.

Context

Candidate 2 of the open problems stated in "Reconstructing Combinatorial Geometries", 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: Reconstructed statement: for a finite pregeometry, i.e. finite simple matroid MM, let

    Hc(M)={ ⁣{ M∣H: H is a hyperplane of M, M∣H is connected } ⁣}\mathcal H_c(M)=\{\!\{\,M|H:\ H\text{ is a hyperplane of }M,\ M|H\text{ is connected}\,\}\!\}

    be the multiset of isomorphism types of connected hyperplanes. Brylawski’s conjecture asserts that if M,NM,N are binary, in particular graphic, with

    ∣E(M)∣=∣E(N)∣,r(M)=r(N),Hc(M)=Hc(N),|E(M)|=|E(N)|,\qquad r(M)=r(N),\qquad \mathcal H_c(M)=\mathcal H_c(N),

    then M≅NM\cong N. This matches the paper’s “hyperplane [vertex] reconstruction” setting and the phrase “known cardinality and rank.”

    Result: The conjecture is false, even for connected simple graphic matroids with a nonempty connected-hyperplane deck.

    Let Θa,b,c\Theta_{a,b,c} be the graph formed by two branch vertices joined by three internally disjoint paths of lengths a,b,ca,b,c. Put

    G1=Θ2,4,4,G2=Θ2,3,5,G_1=\Theta_{2,4,4},\qquad G_2=\Theta_{2,3,5},

    and let Mi=M(Gi)M_i=M(G_i) be their cycle matroids.

    Both graphs are simple, connected, and have 1010 edges and 99 vertices, so

    ∣E(M1)∣=∣E(M2)∣=10,r(M1)=r(M2)=8.|E(M_1)|=|E(M_2)|=10,\qquad r(M_1)=r(M_2)=8.

    They are graphic, hence binary, and their cycle matroids are connected.

    For a connected graph GG, a hyperplane of M(G)M(G) is the complement of a bond. If such a hyperplane is connected as a matroid, the bond must be the star of a single vertex vv, and the card is M(G−v)M(G-v). In Θ2,a,b\Theta_{2,a,b} with a,b≥3a,b\ge3, deleting the unique internal vertex of the length-22 path leaves exactly the cycle Ca+bC_{a+b}, while deleting any other vertex leaves a tree or a graph with a bridge, hence a disconnected cycle matroid. Therefore

    Hc(M(Θ2,a,b))={ ⁣{ M(Ca+b) } ⁣}.\mathcal H_c(M(\Theta_{2,a,b}))=\{\!\{\,M(C_{a+b})\,\}\!\}.

    Since 4+4=3+5=84+4=3+5=8,

    Hc(M1)=Hc(M2)={ ⁣{ M(C8) } ⁣}.\mathcal H_c(M_1)=\mathcal H_c(M_2)=\{\!\{\,M(C_8)\,\}\!\}.

    But M1≇M2M_1\not\cong M_2. The circuits of M(Θa,b,c)M(\Theta_{a,b,c}) are exactly the three cycles obtained by choosing two of the three paths, with sizes

    a+b,a+c,b+c.a+b,\quad a+c,\quad b+c.

    Thus the circuit-size multisets are

    M1: {6,6,8},M2: {5,7,8},M_1:\ \{6,6,8\},\qquad M_2:\ \{5,7,8\},

    which are different. Matroid isomorphisms preserve circuit sizes. Hence the two matroids have the same known cardinality, same rank, and same connected hyperplanes, but are not isomorphic.

    Citation: No prior source is needed for the counterexample. Source conjecture: T. H. Brylawski, “Reconstructing combinatorial geometries,” in Graphs and Combinatorics, Lecture Notes in Mathematics 406, Springer, 1974, pp. 226–235.

    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 TYPE2

      PASS

      The theta-graph construction is a valid counterexample to the stated conjecture. For connected graphic matroids, connected hyperplanes correspond here to vertex-deletion cards whose cycle matroid remains connected; in both Θ2,4,4\Theta_{2,4,4} and Θ2,3,5\Theta_{2,3,5} the only such card is M(C8)M(C_8). The matroids have the same size and rank, but their circuit-size multisets {6,6,8}\{6,6,8\} and {5,7,8}\{5,7,8\} differ, so they are not isomorphic. I found no evidence of a prior published identical or stronger counterexample.

      Novelty assessment

      TYPE2

      Classification rationale: This appears to be a genuinely new negative resolution of Brylawski’s Conjecture 3.3, already false in the graphic/binary case. The construction is elementary and exploits series structure rather than deep 3-connected matroid phenomena, so it is not top-journal level. Still, a clear counterexample to a published Brylawski reconstruction conjecture should plausibly support a short standalone note; I grade it low-end TYPE2.

      Literature check: I found Brylawski’s original paper under DOI 10.1007/BFb0066444 and searched for the exact conjecture language, “connected hyperplanes,” “graphic/binary pregeometry reconstructible,” “matroid reconstruction counterexample,” and the specific theta-graph pair. Searches turned up related work by Brylawski on hyperplane reconstruction of the Tutte polynomial, Miller’s “Techniques in matroid reconstruction,” and papers on non-separating cocircuits/connected hyperplanes in binary matroids, but none contained this counterexample or a stronger disproof of the connected-hyperplane reconstruction conjecture. I also found no matching open-access note, GitHub/forum item, or indexed snippet with the theta-family obstruction.

      Citation: T. H. Brylawski, “Reconstructing combinatorial geometries,” in Graphs and Combinatorics, Lecture Notes in Mathematics 406, Springer, 1974, pp. 226–235. DOI: 10.1007/BFb0066444. No prior citation found for the counterexample.

      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.