Matroid Correlation
Constants

← all families

proved exact · solid curve

Sparse paving extension

\(P_r\) is the free coextension of free extension of \(M\oplus M\), where \(M\) is a sparse paving matroid of rank \(r\) on \(2r\) elements with a lot of circuit hyperplanes.

parameter

integer \(r \geq 2\)

supremum

supremum 4/3 — approached, never attained

discovered by

Michael Feigen and Nicholas Proudfoot

discovery date

2026-08-06

proposed by

proudf

Construction

Let \(M_r\) be a sparse paving matroid of rank \(r\) on \(2r\) elements with \(h\) circuit hyperplanes, and let \(P_r\) be the free coextension of the free extension of \(M\oplus M\). The correlation constant of \(P_r\) with respect to the two new elements is equal to \[\frac{4}{2 + \frac{\binom{2r}{r}^2 - h^2}{\binom{2r}{r-1}\binom{2r}{r+1}}}.\] When \(h=0\), \(M\) is uniform, and we recover the known formula in that case. The correlation constant is maximized by making \(h\) as large as possible. Let \(h_r\) be the maximum possible \(h\) for a given parameter \(r\). We always have \[\frac{1}{2r}\binom{2r}{r}\leq h_r \leq \frac{1}{r+1}\binom{2r}{r}.\] We define \(P_r\) by taking \(h\) to be the ceiling of the lower bound for \(h_r\).

What the curve shows

This curve shows that it is possible to approach \(4/3\) slightly faster than you can by taking \(M\) to be uniform rather than sparse paving.

Proof status

This formula has been proved. The lower bound for \(h_r\) is due to R. L. Graham and N. J. A. Sloane, “Lower bounds for constant weight codes,” IEEE Transactions on Information Theory 26(1) (1980), 37–43. See also Ferroni "Matroids are not Ehrhart positive" Theorem 5.2 for a quick recount. Proof / reference →

AI disclosure

ChatGPT — ChatGPT was used for searching up known lower bounds for \(h_r\). No public chat link is recorded.

Plotted members

7 plotted members