Integer Carathéodory Property for Intersecting Matroid Base Polytopes

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

A matroid consists of a finite ground set with a hereditary independence family satisfying exchange. It is strongly base orderable if for every two bases $B_1,B_2$ there is a bijection $\phi:B_1\to B_2$ such that for every $X\subseteq B_1$, both $(B_1\setminus X)\cup\phi(X)$ and $(B_2\setminus\phi(X))\cup X$ are bases. Its base polytope is the convex hull of base incidence vectors. The Integer Caratheodory Property requires that for every positive integer $k$ and integer $w\in kP$, one can write $w=\sum_i n_ix_i$, where the $x_i$ are affinely independent integer points of $P$, the $n_i$ are nonnegative integers, and $\sum_i n_i=k$.

A polyhedron is an intersection of finitely many closed affine half-spaces; a polytope is a bounded polyhedron. Its faces are its intersections with supporting hyperplanes.

Statement recorded in the supplied source.

Does the intersection of two base polytopes of strongly base orderable matroids have the Integer Carathéodory Property? [S2]

Source status.

The supplied catalogue labels this record open. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Determine whether intersections of the specified matroid base polytopes admit the stated integer decompositions.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30001931 (OWR-11451-004). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Combinatorial Optimization $2012$, Oberwolfach Reports, DOI 10.4171/owr/2011/53, pp. 3003--3076 https://doi.org/10.4171/owr/2011/53.
• S3 Gijswijt--Regts ICP theorem https://arxiv.org/abs/1004.4552. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Preparation and review.

Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30001931 and source code OWR-11451-004 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Literature and context check

The primary report on printed pages 3026--3027 distinguishes integer decomposition from the stronger Integer Caratheodory Property and asks about strongly base orderable intersections. The following proves the stronger property for the explicit subclass of two vertex-partition matroids defining bipartite perfect matchings. This known-style special case does not cover all strongly base orderable matroids.

Research attempt: Greedy affine-independent decomposition for bipartite matching polytopes

A common-base subclass: bipartite perfect matchings

Let the ground set be the allowed edges of a bipartite graph with equally many left and right vertices, with at least one vertex on each side. The empty graph instead has the singleton empty-vector polytope and its Integer Caratheodory Property is immediate. One partition matroid allows at most one edge at each left vertex, and the other at most one at each right vertex. Assume a perfect matching exists. Each matroid is strongly base orderable: for two bases, biject the unique chosen edges within each vertex block; swapping any subset of these matched pairs leaves exactly one edge in every block, in both bases. Their base polytopes are products of unit simplices, because a vector of nonnegative coordinates with block sums one is the convex average of choices, obtained by independently choosing one edge per block with those probabilities. Hence their intersection consists of nonnegative edge vectors with all row and column sums one.

Let $w$ be an integer vector in its $k$-fold dilation, $k\geq1$. Its positive-support bipartite graph has a perfect matching: for a set $U$ of left vertices, the total incident weight is $k|U|$, all lying on its neighboring right vertices, whose total available column weight is at most $k|N(U)|$. Thus $|N(U)|\geq|U|$. To recall the matching implication, a maximum matching failing to cover a left vertex yields an alternating-path search. With no augmenting path, all reached right vertices are matched to reached left vertices other than the initial unmatched one, and all neighbors of reached left vertices are reached. This would give a set with fewer neighbors than vertices, contradicting the inequality.

Choose a perfect matching incidence vector $x$ in the support and let $\lambda=\min_{e:x_e=1}w_e$. This is a positive integer. Subtraction leaves a nonnegative integer vector with every row and column sum $k-\lambda$. Repeat until the residual is zero. The positive multiplicities sum to $k$, and the original $w$ is their weighted sum of matching incidence vectors.

The chosen vectors are affinely independent, an assertion stronger than merely having an integer decomposition. At each step select an edge where the displayed minimum is attained; that edge occurs in the current matching and has zero weight in every later residual, so it occurs in no later chosen matching. In a linear dependence among the chosen vectors, take the earliest nonzero coefficient. Its selected edge has contribution only from that vector and earlier vectors; the earlier coefficients are zero and later vectors omit the edge. That coefficient must therefore be zero, a contradiction. Thus the vectors are even linearly independent, and in particular affinely independent. This proves the Integer Caratheodory Property for this common-base subclass.

Verification and adversarial audit

The selected matching exists in every nonzero residual by the weighted Hall argument. Its multiplicity is a positive integer and lowers the residual row sum, proving termination. Affine independence is proved from an edge eliminated at each step, rather than inferred from integrality or from the number of terms. The strong base-ordering condition is checked directly for both partition matroids.

Audit corrections.

Proved affine independence separately from integer decomposition and kept the common-base subclass explicit.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The general intersection question remains unresolved. For arbitrary matroid intersections, nonnegativity and block sums do not describe all constraints, so the same minimum-coordinate subtraction need not stay inside the residual common-base polytope. No general substitute for this key step is proved.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/46369 (consulted 2026-10-11).

Model and contributor disclosure

The parent Codex GPT-6 model reviewed the written arguments at their declared scopes. This is model-assisted review, not independent human verification. OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration and repository-format review; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.