On totally positive matrices and geometric incidences

DOI10.1016/J.JCTA.2014.08.004MaRDI QIDQ458293zbMATH OpenOpenAlexFDO

Authors Miriam Farber, Shakhar Smorodinsky, Saurabh Ray

Publication date 7 October 2014

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.4542

zbMATH Keywords

discrete geometrygeometric incidencestotally positive

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Positive matrices and their generalizations; cones of matrices (15B48) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20)

Abstract: A matrix is called totally positive if every minor of it is positive. Such matrices are well studied and have numerous applications in Mathematics and Computer Science. We study how many times the value of a minor can repeat in a totally positive matrix and show interesting connections with incidence problems in combinatorial geometry. We prove that the maximum possible number of repeated $dimesd$-minors in a $dimesn$ totally-positive matrix is $O(n^{d-fracdd+1})$. For the case $d=2$ we also show that our bound is optimal. We consider some special families of totally postive matrices to show non-trivial lower bounds on the number of repeated minors. In doing so, we arrive at a new interesting problem: How many unit-area and axis-parallel rectangles can be spanned by two points in a set of $n$ points in the plane? This problem seems to be interesting in its own right especially since it seem to have a flavor of additive combinatorics and relate to interesting incidence problems where considering only the topology of the curves involved is not enough. We prove an upper bound of $O(n^{frac43})$ and provide a lower bound of $n^{1+frac1O(loglogn)}$.

Recommendations

• Publication:4940093
• Totally positive matrices and cyclic polytopes
• scientific article; zbMATH DE number 3946154
• On geometric posets and partial matroids
• Totally positive matrices and totally positive hypergraphs
• Incidence matrices, geometrical bases, combinatorial prebases and matroids
• scientific article; zbMATH DE number 4175158
• scientific article; zbMATH DE number 4028168
• Combinatorial results on completely positive matrices
• scientific article; zbMATH DE number 5138838

Cites work

• scientific article; zbMATH DE number 3523640 (Why is no real title available?)
• scientific article; zbMATH DE number 1943961 (Why is no real title available?)
• scientific article; zbMATH DE number 2145241 (Why is no real title available?)
• Advanced determinant calculus
• Combinatorial complexity bounds for arrangements of curves and spheres
• Combinatorics and total positivity
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• Equal entries in totally positive matrices
• Extremal problems in discrete geometry
• Fast distance multiplication of unit-Monge matrices
• Large Complete Bipartite Subgraphs In Incidence Graphs Of Points And Hyperplanes
• On the Monge property of matrices
• On the Vector Representations of Induced Matroids
• The cone of Monge matrices: Extremal rays and applications
• Totally nonnegative matrices

Cited in

(6)

• Geometric multiplicities of completions of partial triangular matrices
• Zarankiewicz's problem for semi-algebraic hypergraphs
• Point-curve incidences in the complex plane
• Arrangements of minors in the positive Grassmannian and a triangulation of the hypersimplex
• Arrangements of equal minors in the positive Grassmannian
• Equal entries in totally positive matrices

This page was built for publication: On totally positive matrices and geometric incidences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q458293)