The Strong Secretary Conjecture is True for Linear Matroids
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "The Strong Secretary Conjecture is True for Linear Matroids".
Jane: Here's the gist of the paper. The paper proves that a constant fraction of the optimal weight can be guaranteed in the matroid secretary problem for linear matroids by establishing a 1/e guarantee under both known-matroid and online-representation models The result holds both when the matroid is known in advance and when a linear representation over a finite field is given online Each element of a fixed optimal basis is selected with probability at least 1/e.
Tom: The Core Result The central finding is the proof of a 1/e guarantee for the matroid secretary problem on linear matroids.
Jane: This result is established in two models: the known-matroid model and the online-representation model.
Tom: In the known-matroid model, where the entire matroid is known before arrival, an algorithm can select each element of a fixed optimal basis with probability at least 1/e.
Title and authors: Tom: So, as we wrap up this discussion on "The Strong Secretary Conjecture is True for Linear Matroids," we should quickly look at who wrote this. The paper is by Kristóf Bérczi, Shaddin Dughmi, Vasilis Livanos, and José A. Soto.
Jane: They are deep in the world of matroid theory and secretary problems, which means they’re experts on these kinds of combinatorial structures that deal with independence and selection rules.
Lu: What's notable about the authors is their work connecting these concepts to online mechanisms, which is exactly where this paper focuses its attention.
Meng: I don't see any specific industry experience listed for them, so I’m curious if they’ve actually built production systems using this kind of online selection logic.
Lalam: The authors are clearly pushing the boundaries in how we handle uncertainty when the structure itself is revealed over time, which is a hard problem to solve generally.
Tom: It's about proving a strong conjecture for linear matroids, which is significant because it’s a large class of problems we often deal with in data science.
Jane: The title itself suggests that they are settling this conjecture for the class of linear matroids, meaning they are giving a definitive answer to that question within their mathematical framework.
Lu: They aren't just proving it for one specific type of matroid; they are showing the result extends to broader classes, which is what makes the paper have real theoretical weight.
Meng: If this proof doesn't translate easily into an efficient algorithm, then it’s great math but useless in a real-world sense. What about efficiency?
Lalam: The work focuses on proving that a specific type of guarantee, the one over e probability-competitiveness, is achievable through an ordinal approach <ref:2609.20797#pg1>.
Tom: An ordinal approach suggests a sequence of decisions based on partial information, which is very relevant for streaming data scenarios where you only see what has arrived so far.
Jane: That sounds like it’s designed to work even when the full picture isn't available at the start. It’s about making good choices with incomplete information.
Lu: The authors are using tools like Rado's theorem, which is a classic in matroid theory, to find finite-field representations of matroids where they might not exist otherwise.
Meng: Finding a representation is one thing; keeping the algorithm running efficiently while that representation is being revealed sequentially sounds like the real test.
Lalam: The paper addresses this by using an online mechanism where the algorithm learns the representation vector by vector as elements arrive, which keeps things moving.
Tom: So they’re not just proving a static property about a matroid; they’re showing how to solve the problem sequentially as data streams in.
Jane: That sequential learning aspect is what makes this paper relevant to modern machine learning pipelines that deal with continuous data feeds.
The paper's summary: Tom: To summarize "The Strong Secretary Conjecture is True for Linear Matroids," the main point is they proved a one over e guarantee for linear matroids in two different settings <ref:2609.20797#pg1,The Strong Secretary Conjecture is True for Linear Matroids>.
Jane: That guarantee means that even when you don't know the matroid beforehand, you can still ensure you pick a set whose total weight is at least one over e times the optimal weight <ref:2609.20797#pg1>.
Lu: The paper establishes this under two conditions: first when the entire matroid is known in advance, and second when a representation over a finite field is revealed online.
Meng: So we have one scenario where we know everything upfront, and another where things are happening dynamically as they happen. That’s a huge difference in terms of how you design your system.
Lalam: In the known-matroid model, it extends more generally to matroids that admit a finitary modular extension, which means it covers a wider family of structures than just simple linear ones.
Tom: So if you have any matroid that fits that description, this result applies to you as well. It’s not just for the simplest examples.
Jane: The core finding is that each element of a fixed optimal basis can be selected with a probability of at least one over e in the known-matroid model <ref:2609.20797#pg1,each element of a fixed optimal basis>.
Lu: And in the online representation model, they show an ordinal algorithm always selects an independent set with a probability of at least one over e for every element in the optimal set OPT(E) <ref:2609.20797#pg1>.
Meng: That sounds like they’ve cracked a tough problem about how to maintain performance under uncertainty. That's what I care about when we think about real deployment.
Lalam: This guarantee implies that the expected weight of the selected set is at least w(OPT(E)) divided by e in the online model.
Tom: So, if you’re running a system where you have an online representation, that paper tells you exactly how much performance loss to expect compared to the best possible outcome.
Jane: It sets a high bar for what we can achieve in these kinds of selection scenarios when information is revealed incrementally and imperfectly.
The paper's improvements: Tom: Now, let's talk about how this work improves on previous research, because the authors are building on earlier results like Babaioff et al.
Lu: They improve upon previous bounds which were in the omega(one/ r) expected-weight guarantee by moving to a omega(one/ sqrt r) guarantee, and then later to omega(one/ r) <ref:2609.20797#pg1>.
Meng: Those are improvements on the expected weight guarantees, but this paper is about probability-competitiveness, which requires a much stricter condition—a guarantee for *each* element of the optimum.
Lalam: The strong Matroid Secretary Conjecture asks if that one over e guarantee can be achieved under this stricter criterion for every matroid, and this paper answers yes <ref:2609.20797#pg1>.
Tom: So they are moving from just getting a good average weight to guaranteeing performance for every single element in the optimal set, which is a much stronger statement.
Jane: That shift in requirement is what makes the result so powerful; it moves from an expected value guarantee to a probability-competitiveness guarantee.
Lu: The paper addresses this by using tools like Rado's theorem to find finite-field representations of matroids where they might not exist otherwise.
Meng: Finding those representations seems like the crucial step that unlocks the stronger performance guarantees, so without a representation, it’s just theoretical math for now.
Lalam: The authors show that they can achieve this using an ordinal algorithm, which means their selection strategy is built on a sequence of choices rather than a single guess.
Tom: That sounds like a very controlled way to handle the uncertainty; it’s not throwing pure randomness at the problem; it's guiding the process step by step.
Jane: It means that even when you don't know everything about the matroid, you can use that structure to make decisions sequentially that are guaranteed to be good relative to each other.
Conclusion: Tom: So, wrapping up this discussion on "The Strong Secretary Conjecture is True for Linear Matroids," the key takeaway is that they’ve shown a one over e guarantee holds in both known and online settings for linear matroids <ref:2609.20797#pg1,The Strong Secretary Conjecture is True for Linear Matroids>.
Jane: This means we have a high-performance selection strategy even when you’t dealing with structures that are revealed incrementally.
Lu: The paper provides tools, like the feasibility of the linear program via the Dimension Invariant Inequality, to construct these algorithms reliably.
Meng: For deployment, it confirms that if you can manage the representation step, you can achieve a reliable performance metric under streaming conditions.
Lalam: The ordinal algorithm they developed ensures that for every element in the optimal set, there’s a selection probability of at least one over e <ref:2609.20797#pg1>.
Tom: It's a solid theoretical result that settles this conjecture for linear matroids and gives us concrete bounds on performance.
Jane: We have to remember that this applies specifically to linear matroids, so we shouldn't assume the same guarantees apply to general combinatorial structures without checking that condition first.
Lu: The structure of finitary modular extensions provides a nice extension, showing how these results can be generalized further.
Meng: For me, it’s good to see a concrete result that isn't just some abstract bound; it has actual mathematical machinery behind the numbers.
Lalam: I'm just confident that the paper proves what it claims about the probability of selecting each element of the optimum being at least one over e <ref:2609.20797#pg1>.
Tom: That's exactly what we need to hear when we’re trying to understand how selection algorithms perform in complex environments.
Jane: It’s a big step forward for understanding the limits of what we can guarantee in these secretary problems, and it opens up new avenues for research into online decision-making.
Kristóf Bຕzi, Shaddin Dughmi, Vasilis Livanos, José A. Soto, Victor Verdugo
Eötvös Loránd University · University of Southern California · Universidad de Chile · Pontificia Universidad Catolica de Chile
cs.DS
Submitted: 2026-09-17
Updated: 2026-11-05
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 90/100
The gist: The paper proves that a constant fraction of the optimal weight can be guaranteed in the matroid secretary problem for linear matroids by establishing a 1/e guarantee under both known-matroid and…
Key concepts
- Matroid Secretary Problem
- This problem involves selecting items from a set (like elements in a matroid) sequentially as they arrive, trying to maximize the total weight of the selected items. The goal is to find an algorithm that performs well even when the selection process is adaptive.
- Known-Matroid Model
- In this model, the entire structure of the matroid—all its elements and dependencies—is known completely before any selections are made. The paper shows that under this full knowledge, a 1/e guarantee for selecting optimal basis elements is achievable.
- Online Representation Model
- This scenario occurs when the matroid's structure is revealed piece by piece, typically through its representation over a finite field. The algorithm must make selection decisions based only on the information available at that moment, requiring an ordinal strategy.
- Linear Program (LP) Feasibility
- The core of the proof involves solving a large linear program to determine optimal acceptance probabilities for selecting elements. The paper proves this LP is feasible by relating it to chains of subspaces and using duality and uncrossing techniques.
Terminology
Summary
The paper proves that a constant fraction of the optimal weight can be guaranteed in the matroid secretary problem for linear matroids by establishing a 1/e guarantee under both known-matroid and online-representation models The result holds both when the matroid is known in advance and when a linear representation over a finite field is given online Each element of a fixed optimal basis is selected with probability at least 1/e. p. 0 Soto d
Victor Verdugo e
September 17th, 2026
Abstract
We prove a 1/e guarantee for the matroid secretary problem on linear matroids, therefore
settling the strong secretary conjecture in this class of matroids. The result holds both when
the matroid is known in advance and when a linear representation over a finite field is given
online.Where the paper says it
The Core Result
The central finding is the proof of a 1/e guarantee for the matroid secretary problem on linear matroids. This result is established in two models: the known-matroid model and the online-representation model. p. 0 The result holds both when
the matroid is known in advance and when a linear representation over a finite field is given
online. In the known-matroid model, the result extends more generally to matroids admitting
a finitary modular extension. In the known-matroid model, the result extends more generally to matroids admitting
a finitary modular extension. Each element of a fixed optimal basis is selected with probability
at least 1/e. The result holds both when
the matroid is known in advance and when a linear representation over a finite field is given
online. In the known-matroid model, the result extends more generally to matroids admitting
a finitary modular extension.Where the paper says it
Where the paper says it
Where the paper says it
Online Representation Model
In the online-representation model, where a representation of the matroid over a finite field is revealed online, an ordinal algorithm is shown to always select an independent set with probability at least 1/e for every element of OPT(E). This guarantee implies that the expected weight of the selected set is at least w(OPT(E))/e. p. 1 For nonnegative weights, this implies an expected weight of at least c times w(OPT(E)). In
the classical secretary problem, which corresponds to a rank-one matroid, the optimal probability
guarantee is 1/e. In addition to its state, our algorithm maintains some
auxiliary information for every set Y ⊆ X. Specifically, it stores a distribution µY supported on
the subspaces of ⟨Y ⟩, which is defined recursively.Where the paper says it
Where the paper says it
Algorithm Construction and Feasibility
The algorithm relies on solving a large linear program (LP) to determine acceptance probabilities pY(e, W). The feasibility of this LP is established by reducing it to chains of subspaces using duality and uncrossing techniques. p. 1 The above requirements placed on acceptance probabilities lead to a large linear program (LP),
and the main technical step in our proof is to establish its feasibility. Duality and uncrossing
reduce the feasibility argument to chains of subspaces, for each of which we give an explicit feasible
solution. Define
gp(L) := −(i − k) dim(L) + X
e∈Y
ue(L) + X
e∈Y
EW∼µY −e
[pY (e, W)∆e(W, L)] . (3)
The following lemma relates gp(L) to the Dimension Invariant Inequality for a subspace L under
the distribution µY . By our fixed
choice rule, pX has rational entries, and (2) then implies that µX has rational entries. Thus, pX
and µX are well-defined, and (v) holds.Where the paper says it
Where the paper says it
Where the paper says it
Generalization to Known Matroids
The result extends to known matroids that are restrictions of finitary modular matroids. Corollary 1 states that in the known-matroid model, every linear matroid admits an ordinal 1/e-probability-competitive algorithm. p. 2 Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open.Where the paper says it
Extension to Finitary Modular Extensions
The guarantee is extended to matroids admitting a finitary modular extension. Corollary 2 shows that such a matroid admits an ordinal 1/e-probability-competitive algorithm. p. 2 Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open.Where the paper says it
AI Disclosure
The proof relied on a conversation with ChatGPT-6 Astra which identified the supermodularity of gp and proposed the uncrossing argument used to prove the feasibility of the LP. The resulting proof was initially drafted with assistance from ChatGPT-6 Astra. p. 0 Each element of a fixed optimal basis is selected with probability
at least 1/e. Concurrent Discovery Disclosure: The proof of the main result in this manuscript was
obtained in a conversation with ChatGPT-6 Astra on Tuesday, September 15, 2026 at 1:02 AM
PDT. The probability is over both the preceding arrival order
and the internal randomness of the algorithm. The above requirements placed on acceptance probabilities lead to a large linear program (LP),
and the main technical step in our proof is to establish its feasibility. Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open. The second restricts acceptance to elements of OPT(Y ) and assigns zero acceptance probability whenever e ∈ W, so that
accepting e preserves independence. For each e ∈ OPT(Y ), the third sets the expected value of
pY (e, W) over W ∼ µY −e equal to the target value k/(i − 1). Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems. Each element of a fixed optimal basis is selected with probability
at least 1/e. Concurrent Discovery Disclosure: The proof of the main result in this manuscript was
obtained in a conversation with ChatGPT-6 Astra on Tuesday, September 15, 2026 at 1:02 AM
PDT. Each element of a fixed optimal basis is selected with probability
at least 1/e. Concurrent Discovery Disclosure: The proof of the main result in this manuscript was
obtained in a conversation with ChatGPT-6 Astra on Tuesday, September 15, 2026 at 1:02 AM
PDT. Each element of a fixed optimal basis is selected with probability
at least 1/e. Concurrent Discovery Disclosure: The proof of the main result in this manuscript was
obtained in a conversation with ChatGPT-6 Astra on Tuesday, September 15, 2026 at 1:02 AM
PDT. In particular, no representation need be supplied as part
of the input, and the result applies to matroids representable over an arbitrary field. The same argument extends to known matroids that are restrictions of finitary modular matroids, whose lattices of flats satisfy the modular rank identity.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
References
[1] H. Abdi, K. Banihashem, M. Hajiaghayi, and D. p. 2 A stronger notion is probability-competitiveness, which requires a guarantee for each element
of the optimum. Bateni, Hajiaghayi, and Zadimoghaddam [8] obtained an Ω(1/ log2
r) probabilitycompetitive guarantee, and Soto, Turkieltaub, and Verdugo [40] improved it to Ω(1/ log r). The Strong Secretary Conjecture is True for Linear Matroids
Kristóf Bérczi a Shaddin Dughmi b Vasilis Livanos c José A. Soto d
Victor Verdugo e
September 17th, 2026
Abstract
We prove a 1/e guarantee for the matroid secretary problem on linear matroids, therefore
settling the strong secretary conjecture in this class of matroids.Where the paper says it
Where the paper says it
[3] M. Babaioff, M. p. 0 We are sharing our
manuscript nonetheless in case our exposition is of independent utility to the community, and
we hope this experience stimulates broader discussion about concurrent discovery in the AI era. 1 Introduction
The Matroid Secretary Problem, introduced by Babaioff, Immorlica, and Kleinberg [5], extends
the classical secretary problem from selecting a single element to selecting an independent set of a
matroid. We are sharing our
manuscript nonetheless in case our exposition is of independent utility to the community, and
we hope this experience stimulates broader discussion about concurrent discovery in the AI era. 1 Introduction
The Matroid Secretary Problem, introduced by Babaioff, Immorlica, and Kleinberg [5], extends
the classical secretary problem from selecting a single element to selecting an independent set of a
matroid. Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems.Where the paper says it
Where the paper says it
Where the paper says it
[4] M. Babaioff, N. p. 0 We are sharing our
manuscript nonetheless in case our exposition is of independent utility to the community, and
we hope this experience stimulates broader discussion about concurrent discovery in the AI era. 1 Introduction
The Matroid Secretary Problem, introduced by Babaioff, Immorlica, and Kleinberg [5], extends
the classical secretary problem from selecting a single element to selecting an independent set of a
matroid. We are sharing our
manuscript nonetheless in case our exposition is of independent utility to the community, and
we hope this experience stimulates broader discussion about concurrent discovery in the AI era. 1 Introduction
The Matroid Secretary Problem, introduced by Babaioff, Immorlica, and Kleinberg [5], extends
the classical secretary problem from selecting a single element to selecting an independent set of a
matroid. We are sharing our
manuscript nonetheless in case our exposition is of independent utility to the community, and
we hope this experience stimulates broader discussion about concurrent discovery in the AI era. 1 Introduction
The Matroid Secretary Problem, introduced by Babaioff, Immorlica, and Kleinberg [5], extends
the classical secretary problem from selecting a single element to selecting an independent set of a
matroid. Kleinberg [31] studied
the multiple-choice secretary problem, in which up to k elements may be selected. Later, Babaioff,
Immorlica, and Kleinberg [5] introduced the Matroid Secretary Problem; see also the journal version with Kempe [4]. Related LP formulations have since been used in secretary problems
with advice and in sample-driven optimal stopping [14, 21]. Matroid information model.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[5] M. Babaioff, N. Immorlica, and R. p. 0 We are sharing our
manuscript nonetheless in case our exposition is of independent utility to the community, and
we hope this experience stimulates broader discussion about concurrent discovery in the AI era. 1 Introduction
The Matroid Secretary Problem, introduced by Babaioff, Immorlica, and Kleinberg [5], extends
the classical secretary problem from selecting a single element to selecting an independent set of a
matroid. Soto d
Victor Verdugo e
September 17th, 2026
Abstract
We prove a 1/e guarantee for the matroid secretary problem on linear matroids, therefore
settling the strong secretary conjecture in this class of matroids. The result holds both when
the matroid is known in advance and when a linear representation over a finite field is given
online.Where the paper says it
Where the paper says it
[11] N. Buchbinder, K. p. 2 Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems. Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems. Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems.Where the paper says it
Where the paper says it
Where the paper says it
[36] R. Rado. Note on independence functions. p. 2 The information available about the matroid gives rise to two
standard variants [16,26]. In the known-matroid model, the ground set and the entire independence
structure are available before the arrival process, and only the weights are revealed online. The information available about the matroid gives rise to two
standard variants [16,26]. In the known-matroid model, the ground set and the entire independence
structure are available before the arrival process, and only the weights are revealed online.Where the paper says it
Where the paper says it
[40] J. A. Soto, A. Turkieltaub, and V. p. 2 A stronger notion is probability-competitiveness, which requires a guarantee for each element
of the optimum. Bateni, Hajiaghayi, and Zadimoghaddam [8] obtained an Ω(1/ log2
r) probabilitycompetitive guarantee, and Soto, Turkieltaub, and Verdugo [40] improved it to Ω(1/ log r). A stronger notion is probability-competitiveness, which requires a guarantee for each element
of the optimum. Bateni, Hajiaghayi, and Zadimoghaddam [8] obtained an Ω(1/ log2
r) probabilitycompetitive guarantee, and Soto, Turkieltaub, and Verdugo [40] improved it to Ω(1/ log r). Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open. Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[16] A. Cristi, P. Dütting, R. p. 2 For example, the 1/e guarantee of Kesselheim, Radke, Tönnis, and Vöcking [30] for transversal matroids uses this bipartite representation. Similarly, the strongest previous guarantees for graphic
matroids use the graph representation [7, 10], whereas Dütting, Paes Leme, Pál, and Patel [22]
recently obtained a 1/36 utility-competitive guarantee using only independence queries on arrived
elements. We are sharing our
manuscript nonetheless in case our exposition is of independent utility to the community, and
we hope this experience stimulates broader discussion about concurrent discovery in the AI era. 1 Introduction
The Matroid Secretary Problem, introduced by Babaioff, Immorlica, and Kleinberg [5], extends
the classical secretary problem from selecting a single element to selecting an independent set of a
matroid. For example, the 1/e guarantee of Kesselheim, Radke, Tönnis, and Vöcking [30] for transversal matroids uses this bipartite representation. Similarly, the strongest previous guarantees for graphic
matroids use the graph representation [7, 10], whereas Dütting, Paes Leme, Pál, and Patel [22]
recently obtained a 1/36 utility-competitive guarantee using only independence queries on arrived
elements. Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings,
which map a matroid revealed online into a larger known matroid. They constructed embeddings
for binary and laminar matroids and obtained reductions from unknown to known matroids with
an arbitrarily small loss in the expected-weight guarantee.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[17] N. B. Dimitrov and C. G. Plaxton. Competitive weighted matching in transversal matroids. p. 2 For example, the 1/e guarantee of Kesselheim, Radke, Tönnis, and Vöcking [30] for transversal matroids uses this bipartite representation. Similarly, the strongest previous guarantees for graphic
matroids use the graph representation [7, 10], whereas Dütting, Paes Leme, Pál, and Patel [22]
recently obtained a 1/36 utility-competitive guarantee using only independence queries on arrived
elements.Where the paper says it
[38] S. Singla. The matroid secretary conjecture is true, 2026. p. 0 The Strong Secretary Conjecture is True for Linear Matroids
Kristóf Bérczi a Shaddin Dughmi b Vasilis Livanos c José A. Soto d
Victor Verdugo e
September 17th, 2026
Abstract
We prove a 1/e guarantee for the matroid secretary problem on linear matroids, therefore
settling the strong secretary conjecture in this class of matroids.Where the paper says it
[41] J. A. Soto, A. Turkieltaub, and V. Verdugo. Strong algorithms for the ordinal matroid secretary problem.
[43] Kesselheim, K. p. 2 This additional information has been important in obtaining constant guarantees. For example, the 1/e guarantee of Kesselheim, Radke, Tönnis, and Vöcking [30] for transversal matroids uses this bipartite representation. This additional information has been important in obtaining constant guarantees. For example, the 1/e guarantee of Kesselheim, Radke, Tönnis, and Vöcking [30] for transversal matroids uses this bipartite representation. We prove that the optimal 1/e guarantee is achievable in the
online-representation model, in which a representation of the matroid over a finite field is revealed
online. The algorithm knows the number of elements and the underlying finite field in advance,
but not the representation.Where the paper says it
Where the paper says it
Where the paper says it
[46] Rado. Note on independence functions.
[48] Matroid secretary problem in the random-assignment model. p. 3 Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee
for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and
Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which
elements are inspected.Where the paper says it
[49] Strong algorithms for the ordinal matroid secretary problem. p. 2 Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open.Where the paper says it
[51] Online Matroid Embeddings. p. 3 Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings,
which map a matroid revealed online into a larger known matroid. They constructed embeddings
for binary and laminar matroids and obtained reductions from unknown to known matroids with
an arbitrarily small loss in the expected-weight guarantee.Where the paper says it
[53] Secretary problems via linear programming. p. 2 Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems.Where the paper says it
[54] Matroid secretary problem in the random-assignment model. p. 3 Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee
for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and
Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which
elements are inspected.Where the paper says it
[55] Strong algorithms for the ordinal matroid secretary problem. p. 2 Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open.Where the paper says it
[56] Online Matroid Embeddings. p. 3 Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings,
which map a matroid revealed online into a larger known matroid. They constructed embeddings
for binary and laminar matroids and obtained reductions from unknown to known matroids with
an arbitrarily small loss in the expected-weight guarantee.Where the paper says it
[58] Secretary problems via linear programming. p. 2 Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems.Where the paper says it
[61] Matroid secretary problem in the random-assignment model. p. 3 Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee
for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and
Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which
elements are inspected.Where the paper says it
[63] Strong algorithms for the ordinal matroid secretary problem. p. 2 Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open.Where the paper says it
[64] Online Matroid Embeddings. p. 3 Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings,
which map a matroid revealed online into a larger known matroid. They constructed embeddings
for binary and laminar matroids and obtained reductions from unknown to known matroids with
an arbitrarily small loss in the expected-weight guarantee.Where the paper says it
[65] Secretary problems via linear programming. p. 2 Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems.Where the paper says it
[68] Matroid secretary problem in the random-assignment model. p. 3 Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee
for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and
Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which
elements are inspected.Where the paper says it
[69] Strong algorithms for the ordinal matroid secretary problem. p. 2 Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open.Where the paper says it
[71] Online Matroid Embeddings. p. 3 Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings,
which map a matroid revealed online into a larger known matroid. They constructed embeddings
for binary and laminar matroids and obtained reductions from unknown to known matroids with
an arbitrarily small loss in the expected-weight guarantee.Where the paper says it
[73] Secretary problems via linear programming. p. 2 Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems.Where the paper says it
[81] Matroid secretary problem in the random-assignment model. p. 3 Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee
for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and
Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which
elements are inspected.Where the paper says it
[83] Strong algorithms for the ordinal matroid secretary problem. p. 2 Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open.Where the paper says it
[84] Online Matroid Embeddings. p. 3 Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings,
which map a matroid revealed online into a larger known matroid. They constructed embeddings
for binary and laminar matroids and obtained reductions from unknown to known matroids with
an arbitrarily small loss in the expected-weight guarantee.Where the paper says it
[85] Secretary problems via linear programming. p. 2 Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems.Where the paper says it
[86] Matroid secretary problem in the random-assignment model. p. 3 Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee
for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and
Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which
elements are inspected.Where the paper says it
[87] Strong algorithms for the ordinal matroid secretary problem. p. 2 Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open.Where the paper says it
[88] Online Matroid Embeddings. p. 3 Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings,
which map a matroid revealed online into a larger known matroid. They constructed embeddings
for binary and laminar matroids and obtained reductions from unknown to known matroids with
an arbitrarily small loss in the expected-weight guarantee.Where the paper says it
[89] Secretary problems via linear programming. p. 2 Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems.Where the paper says it
[115] Online Matroid Embeddings. p. 3 Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings,
which map a matroid revealed online into a larger known matroid. They constructed embeddings
for binary and laminar matroids and obtained reductions from unknown to known matroids with
an arbitrarily small loss in the expected-weight guarantee.Where the paper says it
[133] Secretary problems via linear programming. p. 2 Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems.Where the paper says it
[135] Matroid secretary problem in the random-assignment model. p. 3 Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee
for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and
Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which
elements are inspected.Where the paper says it
[138] Strong algorithms for the ordinal matroid secretary problem. p. 2 Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open.Where the paper says it
[141] Online Matroid Embeddings. p. 3 Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings,
which map a matroid revealed online into a larger known matroid. They constructed embeddings
for binary and laminar matroids and obtained reductions from unknown to known matroids with
an arbitrarily small loss in the expected-weight guarantee.Where the paper says it
[143] Secretary problems via linear programming. p. 2 Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems. Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems.Where the paper says it
Where the paper says it
[145] Matroid secretary problem in the random-assignment model. p. 3 Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee
for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and
Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which
elements are inspected. Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee
for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and
Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which
elements are inspected.Where the paper says it
Where the paper says it
[148] Strong algorithms for the ordinal matroid secretary problem. p. 2 Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open. Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open.Where the paper says it
Where the paper says it
[153] Online Matroid Embeddings. p. 3 Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings,
which map a matroid revealed online into a larger known matroid. They constructed embeddings
for binary and laminar matroids and obtained reductions from unknown to known matroids with
an arbitrarily small loss in the expected-weight guarantee. Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings,
which map a matroid revealed online into a larger known matroid. They constructed embeddings
for binary and laminar matroids and obtained reductions from unknown to known matroids with
an arbitrarily small loss in the expected-weight guarantee.Where the paper says it
Where the paper says it
[154] Secretary problems via linear programming. p. 2 Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems. Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems.Where the paper says it
Where the paper says it
[155] Matroid secretary problem in the random-assignment model. p. 3 Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee
for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and
Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which
elements are inspected. Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee
for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and
Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which
elements are inspected.Where the paper says it
Where the paper says it
[158] Strong algorithms for the ordinal matroid secretary problem. p. 2 Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open. Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open.Where the paper says it
Where the paper says it
[163] Online Matroid Embeddings. p. 3 Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings,
which map a matroid revealed online into a larger known matroid. They constructed embeddings
for binary and laminar matroids and obtained reductions from unknown to known matroids with
an arbitrarily small loss in the expected-weight guarantee. Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings,
which map a matroid revealed online into a larger known matroid. They constructed embeddings
for binary and laminar matroids and obtained reductions from unknown to known matroids with
an arbitrarily small loss in the expected-weight guarantee.Where the paper says it
Where the paper says it
[165] Secretary problems via linear programming. p. 2 Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems. Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems.Where the paper says it
Where the paper says it
[168] Matroid secretary problem in the random-assignment model. p. 3 Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee
for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and
Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which
elements are inspected. Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee
for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and
Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which
elements are inspected.Where the paper says it
Where the paper says it
[183] Strong algorithms for the ordinal matroid secretary problem. p. 2 Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open. Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open.Where the paper says it
Where the paper says it
[185] Online Matroid Embeddings. p. 3 Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings,
which map a matroid revealed online into a larger known matroid. They constructed embeddings
for binary and laminar matroids and obtained reductions from unknown to known matroids with
an arbitrarily small loss in the expected-weight guarantee. Cristi, Dütting, Kleinberg, Paes Leme, and Patel [16] introduced online matroid embeddings,
which map a matroid revealed online into a larger known matroid. They constructed embeddings
for binary and laminar matroids and obtained reductions from unknown to known matroids with
an arbitrarily small loss in the expected-weight guarantee.Where the paper says it
Where the paper says it
[186] Secretary problems via linear programming. p. 2 Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems. Linear programming has also been used to design and
analyze secretary algorithms. Buchbinder, Jain, and Singh [11] gave a finite LP characterization
of secretary algorithms, and Chan, Chen, and Jiang [13] developed a continuous LP approach for
generalized secretary problems.Where the paper says it
Where the paper says it
[188] Matroid secretary problem in the random-assignment model. p. 3 Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee
for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and
Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which
elements are inspected. Santiago, Sergeev, and Zenklusen [37] obtained a constant guarantee
for random assignment and random arrival order without knowing the matroid. Jaillet, Soto, and
Zenklusen [29] considered the free-order model, where the algorithm chooses the order in which
elements are inspected.Where the paper says it
Where the paper says it
[189] Strong algorithms for the ordinal matroid secretary problem. p. 2 Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open. Singla [38] recently resolved the original Matroid Secretary Conjecture: he
gave an ordinal algorithm that, even in the unknown-matroid model, selects each element of the
optimum with probability at least 1/4. This answers the long-standing question of whether arbitrary matroids admit a constant-factor competitive guarantee, while the strong Matroid Secretary
Conjecture remains open.Where the paper says it
Where the paper says it
[143] Secretary problems via linear programming.
[145] Matroid secretary problem in the random-assignment model.
[148] Strong algorithms for the ordinal matroid secretary problem.
[153] Online Matroid Embeddings.
[154] Secretary problems via linear programming.
[155] Matroid secretary problem in the random-assignment model.
[158] Strong algorithms for the ordinal matroid secretary problem.
[163] Online Matroid Embeddings.
[165] Secretary problems via linear programming.
[168] Matroid secretary problem in the random-assignment model.
[183] Strong algorithms for the ordinal matroid secretary problem.
[185] Online Matroid Embeddings.
[186] Secretary problems via linear programming.
[188] Matroid secretary problem in the random-assignment model.
[189] Strong algorithms for the ordinal matroid secretary problem.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved AI systems can be equipped with an ordinal online algorithm that always selects an independent set ALG satisfying P [e in ALG] >= 1/e for every e in OPT(E) when a linear representation over a finite field is revealed online.
-
AI systems operating in the known-matroid model can achieve a 1/e guarantee by computing a finite-field representation of any representable matroid, even if it is not initially given, and then applying the online algorithm described in Theorem 1.
-
For matroids admitting a finitary modular extension, AI systems can be equipped with an ordinal 1/e-probability-competitive algorithm by using the structure of flats and rank identities derived from the extension M'.
-
The system can use a fixed chain construction to find acceptance probabilities p in LP(X) such that gp(L), which ensures that the Dimension Invariant Inequality holds for every subspace L.
-
The system can solve a finite linear program LP(Y) to determine acceptance probabilities pY, where the feasibility of this LP is guaranteed if the distributions µY-e satisfy the Dimension Invariant Inequality (1).
Abstract
We prove a 1/e guarantee for Matroid Secretary on linear matroids: each element of a fixed optimal basis is selected with probability at least 1/e. This settles the strong secretary conjecture for this class of matroids. Our result holds both when the matroid is known in advance and when a linear representation is given online. In the known-matroid model, the result extends to fully modular extendable matroids. We also obtain 1/e guarantees for a more general model on linear matroids, both when the matroid is known and when its representation is revealed online. In XOS Matroid Secretary, agents with XOS valuations over the elements arrive in uniformly random order, and the algorithm must assign each arriving agent a bundle of elements. The bundles must be pairwise disjoint, and their union must be an independent set of the matroid. We obtain an expected total value of at least 1/e times the offline optimum. This model contains Group Matroid Secretary, in which the elements are adversarially partitioned into groups that arrive in uniformly random order, and the algorithm selects a subset of each arriving group. For this special case, we select each element of a fixed optimal basis with probability at least 1/e
Sources
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time