Matroid Correlation Constants

How correlated can the bases of a matroid be?

Pick a basis uniformly at random. Elements usually repel — seeing one in the basis makes another less likely. But in some matroids a pair of elements attracts, and nobody knows how strong the attraction can get. The challenge: find matroids with large correlation constants.

The record to beat

4/3

≈ 1.3333 — reached by known families only in the limit

No concrete matroid has reached it.

Each dot is a standing record: the best verified α over each of GF(2), GF(3), GF(4), GF(5), and GF(7) — plus any concrete matroid reaching 4/3, over any field or none. Huh–Schröter–Wang: α(M) ≤ 2 for every matroid. Matroids on at most 7 elements never exceed 1.

The correlation constant, at a glance

For a matroid M on {0, …, n−1} and distinct elements i, j, write B_ij(M) for the set of bases containing both i and j, B^ij(M) for the set avoiding both, and Bⁱ_j(M) for the set avoiding i and containing j.

The correlation constant is the largest ratio R_ij, over pairs of nonloop, noncoloop elements; α(M) > 1 means some pair is positively correlated in a uniformly random basis. Why this is interesting, what is known, and full proofs →

R_ij(M) = |B^ij(M)| · |B_ij(M)||Bⁱ_j(M)| · |B^j_i(M)| α(M) = max_{i ≠ j} R_ij(M)

Submit a matroid

Elements n ({0, …, n−1}) Description Field (matrix only)

Data (JSON: a list of rows; columns are the elements)

Claimed α (optional; exact fraction — a mismatch with the computed value fails the submission, catching paste mistakes)

Attribution & discovery (required for a matroid to be recorded; you can verify without it)

Name (for display) Discovered by Discovery date (YYYY-MM or YYYY-MM-DD)

AI used in the discovery? AI model & version Public chat/run link (if one exists)

AI role (one or two sentences)

Citation (paper or preprint, if published)

Notes

Verification is exact: the matroid axioms are checked, every basis is enumerated, and all ratios are compared by integer cross multiplication. Limits: n ≤ 30 (more than 24 elements only in low rank, where enumeration stays feasible; circuit and hyperplane descriptions up to 24), at most 5,000 listed sets or 5,000 matrix entries; matrix fields are ℚ, any prime GF(p) with p < 10⁶, or a proper prime power GF(p^d) up to order 1024. Over ℚ, entries may be integers or fraction strings like "-3/5"; over GF(p^d), integers (subfield constants) or coefficient lists like [0,1] in the Conway polynomial basis, as in Sage or GAP. Anything within the limits can be verified; the record book itself takes a matroid that strictly beats a standing field record — the best α over GF(2), GF(3), GF(4), GF(5), or GF(7), claimed with a matrix over that field — or that reaches α ≥ 4/3 by any description. Proposing an infinite family instead? That takes a proof and human review — see how family proposals work.

Propose an infinite family

A family is a reviewed claim, not a computation: no enumeration can check a formula for every parameter. What you submit here waits as pending — visible only to you and the site admins — until an admin reviews the mathematics and accepts it. An accepted family gets its curve on the chart, a card, and a page. TeX is welcome in the formula and prose fields (\( … \) inline).

Family name Short name (chart legend) Parameter

Claim type Supremum (exact fraction) Supremum is

Formula (TeX, without delimiters) Size and rank (TeX, without delimiters)

Summary (one or two sentences, for the card) Construction What the curve shows

Proof status Proof / reference link (arXiv, paper, or writeup)

Plotted members (JSON: one point per member you want on the chart. "parameter" names the member for the tooltip, like "r = 3"; "n" and "rank" place the dot; "alpha" is the exact value your formula gives it; add "field": q for members verified over GF(q). Plotting several curves, e.g. one per q? Group the points into {"label", "points"} objects, one per curve; at most 400 points)

Discovery record (required — as for matroid record entries)

Discovered by Discovery date (YYYY-MM or YYYY-MM-DD)

AI used in the discovery? AI model & version Public chat/run link (if one exists)

AI role (one or two sentences)

Strengthen the proposal before it reaches review: verify the family’s small members with the concrete form first — each becomes a machine-checked entry a reviewer can lean on. An automatic screen compares the claimed values against the Huh–Schröter–Wang bound and flags a supremum ≥ 4/3 for extra scrutiny; it verifies no mathematics.