Aug 2026· SIAM Journal on Discrete Mathematics· Vol 40, pp. 1342-1368· 0 citations· 9 references
Abstract
Abstract.
The column number question asks for the maximum number of columns of an integer matrix with the property that all its rank size minors are bounded by a fixed parameter [Formula: see text] in absolute value. Polynomial upper bounds have been proved in various settings in recent years, with consequences for algorithmic questions in integer linear programming and matroid theory. In this paper, we focus on the exact determination of the maximum column number of such matrices with two rows and no vanishing 2-minors. We prove that for large enough [Formula: see text], this number is a quasi-linear function, nondecreasing, and always even. Such basic structural properties of column number functions are barely known, but may be expected to hold in other settings as well. Moreover, our results identify the unique excluded (co)rank two minors for the class of matroids that are representable as a [Formula: see text]-submodular matrix.
The Ramsey number $R(m,n)$ is the smallest order at which every red-blue edge coloring of a complete graph must contain a blue clique (a complete subgraph) of size $m$ or a red clique of size $n$. Determining these numbers exactly is extremely hard, and even certifying a lower bound requires exhibiting an explicit colo...
Stefano Coniglio, Fabio Furini, I. Ljubić et al.· 0 citations
By using constant term manipulations, we present the first polynomial-time algorithm for lattice-point counting in fixed dimension that does not rely on Barvinok's unimodular decomposition. The algorithm instead operates directly on a rational generating function in the form of a nested root average, as produced by the...
It is proved that Minimal-to-Maximal Conversion Search is in fact not output-polynomial and the lower bound construction motivates a more detailed analysis of how certain heuristic choices in the algorithm design affect the running time.
The recursive-line Zarankiewicz number maximizes the number of squares in a structured irreducible sum-of-squares representation encoded by an augmentation of an extremal $C_4$-free bipartite graph. We determine its four-column behavior under the strengthened recursive definition in the manuscript of L\"ofberg and Qi d...
We introduce and study a new family of circulant digraphs associated with the cyclic group \({\mathbb Z}_N\), obtained by restricting admissible combinations of two generators \(a\) and \(b\) to three coordinate sectors. The resulting distance-like function differs from the standard directed distance in circulant digra...
C. Dalf'o, M. Fiol, M. Reyes· Utilitas mathematica· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
