On the distribution of runners on a circle

DOI10.1016/J.EJC.2020.103137MaRDI QIDQ2198971zbMATH OpenOpenAlexFDO

Authors Pavel Hrubeš

Publication date 15 September 2020

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Newton polytopesreal \(\tau\)-conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Ramsey theory (05D10)

Abstract: Consider $n$ runners running on a circular track of unit length with constant speeds such that $k$ of the speeds are distinct. We show that, at some time, there will exist a sector $S$ which contains at least $|S|n+Omega(sqrtk)$ runners. The result can be generalized as follows. Let $f(x,y)$ be a complex bivariate polynomial whose Newton polytope has $k$ vertices. Then there exists $ainmathbbCsetminus0$ and a complex sector $$ such that the univariate polynomial $f(x,a)$ contains at least $$ non-zero roots in $S$ (where $n$ is the total number of such roots and $$). This shows that the Real $au$-Conjecture of Koiran implies the conjecture on Newton polytopes of Koiran et al.

Recommendations

• Problems on track runners
• Some remarks on the lonely runner conjecture
• A note on the lonely runner conjecture
• On the real \(\tau\)-conjecture and the distribution of complex roots
• On the Lonely Runner Conjecture.

Cites work

• scientific article; zbMATH DE number 3125787 (Why is no real title available?)
• scientific article; zbMATH DE number 3865403 (Why is no real title available?)
• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• scientific article; zbMATH DE number 233956 (Why is no real title available?)
• scientific article; zbMATH DE number 3059981 (Why is no real title available?)
• A Sufficient Condition for All the Roots of a Polynomial To Be Real
• A \(\tau \)-conjecture for Newton polygons
• A probabilistic approach to problems of diophantine approximation
• Complementary sets of sequences
• Completeness and reduction in algebraic complexity theory
• Mathematical problems for the next century
• On sufficient conditions for a polynomial to be sign-independently hyperbolic or to have real separated zeros
• On the distribution of roots of polynomials
• On the real \(\tau\)-conjecture and the distribution of complex roots

Cited in

(4)

• On the real \(\tau\)-conjecture and the distribution of complex roots
• Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
• Running Clubs-A Combinatorial Investigation
• Shadows of Newton polytopes

This page was built for publication: On the distribution of runners on a circle

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