We prove weighted matroid equitability. Let $M=(E,\mathcal{I})$ be a matroid whose ground set can be partitioned into $k$ bases, and assign a nonnegative weight to every element. Then $E$ has a partition into $k$ bases such that the weights of any two bases differ by at most the largest element weight. We present two proofs based on the localized exchange theorem of Akrami, Liu, Raj, and V\'egh. The first is existential, while the second is constructive and leads to a strongly polynomial-time algorithm. As applications, we obtain an additive guarantee for matroid-constrained makespan minimization for identical machines and a strongly polynomial-time algorithm for finding an EF1 allocation under a matroid constraint and identical additive valuations. We further generalize the Beck--Fiala framework in discrepancy theory to settings with matroid constraints. Given a nonnegative matrix of column sparsity $\Delta$, we show that a fractional basis can be rounded to a basis of no larger cost while preserving every row sum within additive error $2\Delta$ times the largest matrix entry. Motivated by the $2$-sparse prefix Beck--Fiala conjecture, we formulate a conjecture on prefix-constrained matroid bases and prove a discrepancy bound $O(\log n)$. Finally, we give a counterexample to the weighted carpooling conjecture, thereby also disproving a conjecture by Morell and Skutella on single-source unsplittable flows with two-sided discrepancy bounds.
Consider the problem of maximizing the number of satisfied constraints of an arbitrary boolean constraint satisfaction problem with arity $k$. We obtain a polynomial time algorithm that achieves a $(k/2^k)$-approximation, improving on the previous best guarantee of $0.626612\; k/2^k$, due to Makarychev and Makarychev (arXiv:1206.3603). Assuming the Unique Games Conjecture, De and Mossel (arXiv:1202.5258) showed that achieving an approximation ratio better than $(k+1)/2^k$ for odd $k$ and $(k+2)/2^k$ for even $k$, is NP-hard. The main technical ingredient is an extension of a recently established Gaussian comparison inequality, used to resolve the Weak Simplex Conjecture in coding theory (arXiv:2607.14087).
We introduce folded-algebraic matroids. In such a representation, every matroid element is replaced by a finite tuple of algebraic quantities, and transcendence degree agrees with matroid rank after one uniform scaling. The resulting class contains both algebraic and folded-linear matroids and is contained in the class of almost-entropic matroids, whose rank functions are limits of scaled entropy functions. We prove that the latter containment is proper. Our main result concerns the classical rank-three matroids $M(p)$ of Gordon. For every prime $p$, we show that $M(p)$ has a folded-algebraic representation over a field $K$ if and only if $K$ has characteristic $p$. We then use a point-identification construction that preserves almost-entropicity to obtain a $13$-element rank-three $3$-connected matroid $C_{2,3}$ that is almost entropic but not folded algebraic. Choosing a common element as dealer also yields a connected $12$-participant port with incompatible characteristic requirements. Finally, we record compact explicit witnesses and size bounds for several other separating regions among the representation classes.
We give a counterexample to the convergence conjecture in Remark 12 of [Bolte&Pauwels, 2021] for mini-batch stochastic approximation with definable potentials. The construction uses two convex piecewise-affine, hence semialgebraic, summands on $\mathbb{R}$. We choose a deterministic nonincreasing block stepsize sequence satisfying $\alpha_k = o(1/\log k)$ and an admissible minimum-norm selection from each aggregate batch field. On successive blocks, the iterates form lazy reflected random walks on nested dyadic lattices. An explicit endpoint-cover-time estimate, Markov's inequality, and the first Borel-Cantelli lemma imply that almost surely every sufficiently late block's iterates visit their entire lattice. Consequently, the iterates remain in $[-1,1]$ but do not converge, and their accumulation set is exactly $[-1,1]$, on which the averaged objective is constant. Finally, the construction has $\sum_k \alpha_k^2 =\infty$. Both Chat-GPT 5.6 (Sol) and Gemini Pro 3.1 (DeepThink) were used in the development and drafting of this result.
We study the simultaneous approximation of constant-degree polynomials over convex sets. For any family of $m$ degree-$d$ polynomials and any convex set ${H} \subseteq \mathbb{R}_{\ge0}^n$, we construct an $\epsilon$-Cover of the joint value set $\{(f_1(x), \dots, f_m(x)) : x \in {H}\}$ in the $\ell_\infty$-norm. This cover is of size $n^{O(\log(mn)/\epsilon^2)}$, provided the polynomials have constant range over the smallest $\ell_1$-ball inscribing ${H}$. Our approach extends classical net-based sparsifications for linear functions (e.g., Lipton, Markakis, and Mehta [2003]) to arbitrary families of constant-degree polynomials over general convex sets. We use a two-step scheme: first, we construct a quasi-polynomial pre-cover of the family on the smallest $\ell_1$-ball containing ${H}$ by using a concentration argument and leveraging a connection between Bernstein approximation and multinomial distributions; we then compress the pre-cover to ${H}$ by using a recursive degree reduction and feasibility programs anchored at points of the pre-cover. The existence of these covers immediately yields a unified framework for Quasi-Polynomial Time Approximation Schemes (QPTAS) across a wide range of a problems, including fixed-degree polynomial minimization over polyhedral sets, Constraint Satisfaction Problems (CSPs), Free Games, variational inequalities with polynomial operators (which implies guarantees for local Nash equilibria in polynomial games), and additive approximation for normalized densest $k$-subhypergraph on $O(1)$-uniform hypergraphs.
Martino Bernasconi, Matteo Castiglioni, Andrea Celli et al.· arXiv.org· 1 citation
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.
We determine all equality cases in the Tu--Deng bound $|S_{t,k}|\le 2^{k-1}$. If the $k$-bit cyclic word of $t$ has $R$ ones, $Z$ zeros, and cyclic one-gap lengths $g_1,\ldots,g_Z$, then equality holds if and only if $g_i\ge Z-1$ for every $i$. This resolves Conjecture~3.20 of Flori, Randriambololona, Cohen and Mesnager, and we also enumerate all equality parameters. For $R\ge Z$ we determine the sharp first stability gap and all extremal words, while for $R<Z$ we obtain an exact quantization of the deficit and an explicit run-sensitive lower bound. The proofs are structural: an explicit matrix conjugation identifies the auxiliary enumerators in the two recent complete proofs of the Tu--Deng conjecture. We then develop a rooted coarsening model for all coefficients, prove one-sided deletion rigidity and an exact Macaulay-flux identity, and derive a Macaulay--M\"obius formula from the bounded simplex at the highest cyclic level.
Kaimin Cheng· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
