CS Paper Radar

Almost entropic matroids and $(k,L)$-systems

Andrey Kupavskii, Nikolai Terekhov

cs.IT math.CO ·submitted 2026-10-20 09:12 UTC · v1
theory

Abstract

For an integer $k$ and a set of integers $L$, a $(k,L)$-system is a family of $k$-element sets such that the size of the intersection of any two distinct members belongs to $L$. Let $m(n,k,L)$ denote the maximum size of a $(k,L)$-system on a ground set of $n$ elements. In this work, we establish a close connection between the asymptotic growth of $m(n,k,L)$ and almost entropic matroids. As a consequence, we obtain a general computable upper bound on the asymptotics of $m(n,k,L)$ that unifies and strengthens all previously known upper bounds.

Closest papers

Nearest neighbours by meaning across the whole index.

Asymptotically Optimal Bounds for Counting Near-Minimum Circuits in Regular Matroids

cs.DM math.CO ·2026-11-11 ·Robert P. Streit
theory similarity 0.72
Abstract · 28 pages

For a regular matroid on $m$ elements with positive weights and weighted girth $g_w$, we prove that the number of circuits of weight at most $αg_w$ is bounded by $(Km)^{2α}$, for every real $α\ge1$ and an absolute constant $K$. This improves the previous $m^{O(α^2)}$ bound of Gurjar and Vishnoi and matches classic graph cut and cycle counting bounds of Karger and Subramanian. We also show this is asymptotically optimal for all real $α\geq 1$ under the Erdős girth conjecture, while unconditional optimality holds for half-integer $α$ by prior results. As consequences, we resolve a recent conjecture by Khanna, Putterman, and Song implying the existence of a parallel basis search algorithm for regular matroids terminating in logarithmically many rounds of independence queries, and obtain improved bounds on the number of near-minimum weight codewords in regular codes and near-shortest vectors in totally unimodular lattices under $\ell_p$-norms.

0.23

Integrality-Gap Bounds for Weighted Matchoids and Matroid Intersection

cs.DM math.CO ·2026-09-18 ·Yu Cong, Yajie Zhao
theory similarity 0.68
Abstract

The weighted $k$-matroid intersection problem asks for a maximum-weight set that is independent in each of $k$ matroids on a common ground set. The natural LP relaxation optimizes over the intersection of the $k$ matroid independent set polytopes. It is conjectured that this LP has integrality gap at most $k-1$. The conjecture is known for $k\le3$, but for $k\ge4$ the best general upper bound was $k$. We improve this bound to $k-1+1/k$. More generally, we prove that the natural LP of a $p$-matchoid has integrality gap at most $p-1+1/p$, with a deterministic LP-relative algorithm attaining the same factor. The matchoid extension resolves the $p$-matchoid part of a conjecture of Lee, Sviridenko, and Vondrák; projective planes give explicit tight instances whenever one of order $p-1$ exists.

0.25

Analysis of the two-for-one swap heuristic for approximating the maximum independent set in a k-polymatroid

cs.DS ·2026-10-06 ·Adrian Calinescu, Gruia Calinescu
published similarity 0.66
Abstract

Let f:2^N --> \cZ^+ be a polymatroid (an integer-valued non-decreasing submodular set function with f(emptyset) = 0). A k-polymatroid satisfies that f(e) <= k for all e in N. We call a subset S of N independent if f(S) equals the sum of f(e) over the elements e of S and f(e) > 0 for all e in S. Finding a maximum-size independent set in a 2-polymatroid has been studied and polynomial-time algorithms are known for linear polymatroids. For k >= 3, the problem is NP-hard, and an approximation algorithm with ratio approaching 2/k is known and is obtained by swapping as long as possible a "large" subset from the current solution by a set with one more element. Here we give a simple analysis of the more particular two-for-one repeated swapping heuristic, obtaining a (weaker) 2/(k+1)-approximation.

0.24

$L$-systems on the large Witt design

cs.IT math.CO ·2026-11-16 ·Toshihiro Shimizu, Norihide Tokushige
theory similarity 0.64
Abstract · 14 pages

Let $L=\{0,1,2,3,4,8\}$, associated with the large Witt design $S(5,8,24)$, and let $m(n,24,L)$ be the maximum size of a family of $24$-element subsets of an $n$-element set whose distinct members have intersection sizes in $L$. We prove that there are positive constants $c,C,n_0$ such that, for every $n\geq n_0$, \[ cn^{316/63}\leq m(n,24,L)\leq Cn^{169/29}. \] We also obtain similar results for the systems associated with $S(4,7,23)$, $S(3,6,22)$, and $S(3,4,14)$. The upper bounds follow from a non-Shannon information inequality and disprove conjectures of Kupavskii and Terekhov. The lower bounds follow from an algebraic construction for arbitrary Steiner systems.

0.35

Derandomizing Karger's Contraction Algorithm for Matroids

cs.DS cs.DMmath.CO ·2026-08-17 ·Yu Cong, Chao Xu, Yajie Zhao
theory similarity 0.64
Abstract

Karger's randomized contraction algorithm finds a minimum-weight cocircuit of a matroid whenever the cogirth-density ratio is bounded. We prove that the same hypothesis yields a deterministic algorithm with the same exponent. If every contraction minor of rank at least $r_0$ of a matroid $M$ has cogirth-density ratio at most $c$, then a minimum-weight cocircuit of $M$ is computable deterministically in $m^{O(r_0)} n^{O(c)}$ time when the contraction minors of bounded rank have at most $m$ parallel classes, by an algorithm that knows neither $r_0$ nor $c$. As a consequence, we give a deterministic algorithm computing the cogirth of rank-$p$ perturbed graphic matroids in $2^{O(p^2)} n^{O(1)}$ time, fixed-parameter tractable in $p$, settling the cogirth side of a question of Geelen and Kapadia (2018). The extensions of the contraction method carry over deterministically: enumerating all near-minimum 1-cocycles, computing a minimum-weight $k$-cocycle, and computing the Pareto frontier under several positive criteria.

0.35

On the Strong Matroid Secretary Conjecture and Beyond

cs.DS ·2026-09-16 ·Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, Danny Mittal
theoryhot directionhighly cited similarity 0.64
Abstract

The strong matroid secretary conjecture asserts that every matroid admits a $1/e$-competitive secretary algorithm, matching the classical single-choice guarantee. We formulate a finite linear program whose value is the optimal ordinal competitive ratio of any fixed matroid; for all matroids of positive rank on seven elements and nearly all on eight, this value exceeds $1/e$. The same computations suggested that the optimal ratio is monotone under truncation of the matroid; we prove this for uniform matroids, where the ratio is strictly increasing in the rank, and refute it for a graphic matroid. Guided by this evidence, we prove the conjecture for every linear matroid, a class that includes graphic matroids, regular matroids, laminar matroids, and gammoids, giving a $1/e$-competitive ordinal secretary algorithm. The algorithm maintains bounds on the expected intersection dimension of the accepted span with every ambient subspace. Uncrossing and separation show that these bounds can be preserved while admitting each current greedy-basis element with a prescribed probability and the construction uses finite linear programs. For every matroid, we also give a single-sample prophet algorithm with competitive ratio $1/2$ in any fixed arrival order independent of the samples and values. Its output, including the selected values, has exactly the law of an independent fair thinning of an optimum from a fresh product draw. The algorithm uses $O(n^2)$ independence queries on $n$ elements. Both constants are tight in their respective models. We also give a self-contained black-box reduction that converts a single-sample prophet ratio $α$ into a secretary ratio $α^2/16$, preserving polynomial running time. Our single-sample algorithm consequently yields a $1/64$-competitive ordinal secretary algorithm for arbitrary matroids.

0.46

Random Deletion for Circuits in Regular Matroids

cs.DS ·2026-10-24 ·Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu
similarity 0.63
Abstract · 43 pages, 5 figures

We study a simple random deletion algorithm to find short circuits in regular matroids. Given a regular matroid $M$ with $m$ elements, the algorithm randomly deletes each element independently with probability $1-1/m^{Θ(1/g)}$ where $g$ is the size of a minimum circuit, and returns the remaining set $R$ of elements. We establish the following results: 1. With high probability, $R$ contains no circuit and is therefore independent. 2. For every $α$-approximate minimum circuit $C$ where $α\geq 1$, with probability at least $m^{-O(α)}$, the entire circuit $C$ survives in $R$ and moreover, the minimum number of elements that need to be removed to make $R$ independent is $O(α\log(α+2))$. This yields an algorithmic proof that the number of $α$-approximate minimum circuits is $m^{O(α)}$, improving the previous known bound of $m^{O(α^2)}$ by Gurjar and Vishnoi, and resolving a recent conjecture of Khanna, Putterman, and Song. Our results yield two immediate applications. First, we obtain very simple RNC algorithms for computing the shortest circuit, and for enumerating all $α$-approximate circuits, of a regular matroid without computing the Seymour decomposition. Second, we obtain a randomized parallel algorithm to find a basis of a regular matroid under independence-oracle access. It uses polynomially many independence-oracle queries in $O(\log m)$ adaptive rounds and succeeds with high probability. This follows from the framework of Khanna, Putterman, and Song and the improved counting bound, and extends their result from graphic matroids to regular matroids.

0.61

A Faster Auction Algorithm for Weighted Matroid Intersection

cs.DS ·2026-10-01 ·Tatsuya Terao
similarity 0.63
Abstract · 17 pages. In this version, we have completely rewritten the proof, which is now simpler and easier to follow, and improved the clarity and p…

We consider the weighted matroid intersection problem in the independence-oracle model. A sequence of works by Huang--Kakimura--Kamiyama~[SODA'16 \& Math. Program'19], Chekuri--Quanrud~[SODA'16], Quanrud~[ICALP'24], and Dudeja--Grilnberger~[IPCO'26] has developed efficient $(1-\varepsilon)$-approximation algorithms for this problem. We present a simple deterministic auction algorithm that, given two matroids on a common ground set of size $n$, computes a $(1-\varepsilon)$-approximate maximum-weight common independent set using $O(n \varepsilon^{-2} \log^2(n))$ independence-oracle queries. This is the first deterministic $(1-\varepsilon)$-approximation algorithm for the weighted matroid intersection problem whose query complexity is nearly linear in $n$ and polynomial in $1/\varepsilon$. Our algorithm builds on the auction algorithm for unweighted matroid intersection by Huang--Kobayashi~['26].

0.08