Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, Γ‰cole polytechnique fΓ©dΓ©rale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Books and Book parts
  4. Excluding a Line Minor via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure
 
book part or chapter

Excluding a Line Minor via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure

Dadush, Daniel
β€’
Eisenbrand, Friedrich  
β€’
Pinchasi, Rom
Show more
January 2026
Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

For a real matrix 𝐀 βˆˆβ„π‘‘Γ—π‘› with non-collinear columns, we show that 𝑛 ≀𝑂⁑(𝑑4β’πœ…π€) where πœ…π€ is the circuit imbalance measure of 𝐀. The circuit imbalance measure πœ… is a real analogue of Ξ”-modularity for integer matrices, satisfying πœ…π€ ≀Δ𝐀 for integer 𝐀. The circuit imbalance measure has numerous applications in the context of linear programming (see Ekkbatani, Natura and VΓ©gh (2022) for a survey). Our result generalizes the 𝑂⁑(𝑑4⁒Δ𝐀) bound of Averkov and Schymura (2023) for integer matrices and provides the first polynomial bound holding for all parameter ranges on real matrices. To derive our result, similar to the strategy of Geelen, Nelson and Walsh (2021) for Ξ”-modular matrices, we show that real representable matroids induced by πœ…-bounded matrices are minor closed and exclude a rank-2 uniform matroid on 𝑂⁑(πœ…) elements as a minor (also known as a line of length 𝑂⁑(πœ…)). As our main technical contribution, we show that any simple rank-𝑑 complex representable matroid which excludes a line of length 𝑙 has at most 𝑂⁑(𝑑4⁒𝑙) elements. This complements the tight bound of (𝑙 βˆ’3)⁒(𝑑2) +𝑑 for 𝑙 β‰₯4, of Geelen, Nelson and Walsh, which holds when the rank 𝑑 is sufficiently large compared to 𝑙 (at least doubly exponential in 𝑙). Our proof of the above relies on an improvement of a Sylvester-Gallai type theorem of Dvir, Saraf and Wigderson (2014). Refining their design matrix technique, we show that for any full dimensional set of 𝑛 points in ℂ𝑑 there always exists a point that lies on at least (1 βˆ’4/𝑑)⁒𝑛 many distinct lines (the constant 4 is improved from 12). The excluded minor bound follows by inductively applying this result to find good elements to contract in the matroid, where the improved constant reduces the dependence on 𝑑 from 𝑑12 to 𝑑4. Interestingly, by relying on geometric techniques, our proof avoids the use of any difficult matroid machinery.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

2510.20301v1-1.pdf

Type

Main Document

Version

Submitted version (Preprint)

Access type

openaccess

License Condition

N/A

Size

654.25 KB

Format

Adobe PDF

Checksum (MD5)

4a457da5bff41c79a2d3c25e5b383200

Logo EPFL, Γ‰cole polytechnique fΓ©dΓ©rale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. Β© EPFL, tous droits rΓ©servΓ©s