we-solve (beta)

Math-1026 · mathematics · Combinatorics

Aharoni-Berger conjecture

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Let $E$ be finite and let $k\ge2$ and $\ell\ge1$ be integers. For each $i\in\{1,\ldots,k\}$, let $M_i=(E,\mathcal I_i)$ be a matroid: $\mathcal I_i$ is a nonempty hereditary family with the exchange property that if $I,J\in\mathcal I_i$ and $|I|<|J|$, an element of $J\setminus I$ can be added to $I$ while preserving membership in $\mathcal I_i$. Its rank function is $r_i(X)=\max\{|I|:I\subseteq X,\ I\in\mathcal I_i\}$.

An ordered partition of $E$ into $k$ parts means pairwise disjoint sets $X_1,\ldots,X_k$ with union $E$; empty parts are permitted, and the part $X_i$ is assigned to the particular matroid $M_i$. Suppose that every such partition satisfies \[ \sum_{i=1}^k r_i(X_i)\ge\ell(k-1). \] The conjecture concludes that there exists a single subset $I\subseteq E$ with $|I|=\ell$ and $I\in\bigcap_{i=1}^k\mathcal I_i$. Thus one selects exactly the same elements independently in all the matroids, rather than separate independent subsets for the different parts of a partition.

The factor $k-1$ and the quantification over all ordered partitions are part of the proposed sufficient condition. The case $k=1$ is excluded: with that value the displayed hypothesis would be vacuous and could not imply the claimed conclusion. Allowing empty parts prevents a vacuous hypothesis when the ground set is small.

Short English statement

Does the specified rank bound over every partition force an independent set of size $\ell$ common to all $k$ matroids?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-1026-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on Math-1026

Aharoni-Berger conjecture

Definitions and mathematical statement

Let $E$ be finite and let $k\ge2$ and $\ell\ge1$ be integers. For each $i\in\{1,\ldots,k\}$, let $M_i=(E,\mathcal I_i)$ be a matroid: $\mathcal I_i$ is a nonempty hereditary family with the exchange property that if $I,J\in\mathcal I_i$ and $|I|<|J|$, an element of $J\setminus I$ can be added to $I$ while preserving membership in $\mathcal I_i$. Its rank function is $r_i(X)=\max\{|I|:I\subseteq X,\ I\in\mathcal I_i\}$.

An ordered partition of $E$ into $k$ parts means pairwise disjoint sets $X_1,\ldots,X_k$ with union $E$; empty parts are permitted, and the part $X_i$ is assigned to the particular matroid $M_i$. Suppose that every such partition satisfies \[ \sum_{i=1}^k r_i(X_i)\ge\ell(k-1). \] The conjecture concludes that there exists a single subset $I\subseteq E$ with $|I|=\ell$ and $I\in\bigcap_{i=1}^k\mathcal I_i$. Thus one selects exactly the same elements independently in all the matroids, rather than separate independent subsets for the different parts of a partition.

The factor $k-1$ and the quantification over all ordered partitions are part of the proposed sufficient condition. The case $k=1$ is excluded: with that value the displayed hypothesis would be vacuous and could not imply the claimed conclusion. Allowing empty parts prevents a vacuous hypothesis when the ground set is small.

Short English statement

Does the specified rank bound over every partition force an independent set of size $\ell$ common to all $k$ matroids?

Research attempt: a closure certificate and the missing factor

Scope and literature check.
GPT-6 Astra Ultra, 1 October 2026. The parts of the partition are ordered and can be empty. The original discussion [S2] identifies $k=2$ with matroid intersection and records the $k=3$ result of Aharoni--Berger. The authors' research report [S3] explains the matroid/complex intersection framework. Our elementary argument below does not reproduce that topological theorem. It obtains a $k$-factor bound and, by integrality, settles the stated conclusion when $\ell<k$.
1. Define the two extremal quantities.
Let \[ R=\min_{E=X_1\sqcup\cdots\sqcup X_k}\sum_i r_i(X_i),\qquad \nu=\max\{|I|: I\text{ is independent in every }M_i\}. \] These extrema exist on the finite ground set. If $I$ is common independent, then $I\cap X_i$ is independent in $M_i$ and hence $r_i(X_i)\ge|I\cap X_i|$. Summing gives $R\ge\nu$. This necessary inequality alone has the wrong direction to force a large $I$.
2. Every maximal common independent set certifies $R\le k|I|$.
Construct $I$ greedily until no element can be added while retaining independence in all matroids. Write $s=|I|$; maximality here is under inclusion, not necessarily maximum cardinality. For each $e\notin I$ choose an index $i(e)$ such that $I\cup\{e\}$ is dependent in $M_i$. Since $I$ is independent, this says $r_i(I\cup\{e\})=r_i(I)=s$, or $e\in\operatorname{cl}_i(I)$.

For completeness, adjoining all such individually spanned elements does not raise rank. If $r_i(I\cup A)=s$ and $r_i(I\cup\{e\})=s$, submodularity yields \[ r_i(I\cup A\cup\{e\})+r_i(I) \le r_i(I\cup A)+r_i(I\cup\{e\})=2s. \] Induction establishes the claim for every finite collection of them.

Assign each outside element to $X_{i(e)}$, and assign the elements of $I$ arbitrarily to the parts, for example all to $X_1$. Then $X_i\subseteq\operatorname{cl}_i(I)$, so $r_i(X_i)\le s$ for every $i$. This is an actual ordered partition, and therefore \[ R\le\sum_i r_i(X_i)\le ks. \] Applying the hypothesis $R\ge\ell(k-1)$ gives \[ |I|\ge\left\lceil\frac{\ell(k-1)}k\right\rceil. \] In particular if $1\le\ell<k$, the number inside the ceiling is $\ell-\ell/k\in(\ell-1,\ell)$, so $|I|\ge\ell$. Any $\ell$-subset of $I$ answers the question in this parameter range.

3. Where the tempting improvement breaks.
One might try to replace $ks$ by $(k-1)s$ by saying that each element of $I$ was assigned to only one part. That does not bound the ranks of the other parts: a part disjoint from $I$ may still have rank $s$ while lying in its closure. For a rank-one matroid with two parallel nonloops $a,b$, the set $\{b\}$ is disjoint from the basis $\{a\}$, lies in its closure, and has full rank one. In higher rank, parallel copies of all basis elements give the same obstruction. Thus accounting for membership in $I$ cannot save one whole rank contribution.
Verification and remaining gap.
The argument permits loops; they simply belong to the closure of every set and contribute no rank. If $I$ were empty, the constructed partition would have total rank zero, contradicting the positive hypothesis. At $\ell=k$, the bound supplies only $k-1$, so the integrality argument has a genuine endpoint. A proof for larger $\ell$ needs a more effective exchange or partition certificate than single-element maximality. No unjustified $k$-matroid analogue of the two-matroid min--max theorem is used.

Final status

UNRESOLVED in general. A constructive lower bound for every maximal common independent set and the full implication for $\ell<k$ are proved. The known $k=2,3$ results are attributed to the literature; no new general solution or completion percentage is claimed.

Sources

Go to contribution →