On totally positive matrices and geometric incidences

DOI10.1016/J.JCTA.2014.08.004zbMATH Open1301.05215arXiv1309.4542OpenAlexW2093992348MaRDI QIDQ458293FDOQ458293

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)

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)}$.

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

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
• scientific article; zbMATH DE number 4028168
• Combinatorial results on completely positive matrices
• scientific article; zbMATH DE number 5138838

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)

Cites Work

• Title not available (Why is that?)
• Advanced determinant calculus
• Combinatorics and total positivity
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• Title not available (Why is that?)
• Extremal problems in discrete geometry
• Combinatorial complexity bounds for arrangements of curves and spheres
• Title not available (Why is that?)
• On the Vector Representations of Induced Matroids
• Totally nonnegative matrices
• Equal entries in totally positive matrices
• Fast distance multiplication of unit-Monge matrices
• The cone of Monge matrices: Extremal rays and applications
• Large Complete Bipartite Subgraphs In Incidence Graphs Of Points And Hyperplanes
• On the Monge property of 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)