On the distribution of runners on a circle

DOI10.1016/J.EJC.2020.103137zbMATH Open1447.05203arXiv1906.02511OpenAlexW3017857753MaRDI QIDQ2198971FDOQ2198971

Authors: Pavel Hrubeš 

Publication date: 15 September 2020

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

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.

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A Sufficient Condition for All the Roots of a Polynomial To Be Real
• Title not available (Why is that?)
• Mathematical problems for the next century
• Completeness and reduction in algebraic complexity theory
• Title not available (Why is that?)
• On the distribution of roots of polynomials
• A \(\tau \)-conjecture for Newton polygons
• Complementary sets of sequences
• Title not available (Why is that?)
• A probabilistic approach to problems of diophantine approximation
• On sufficient conditions for a polynomial to be sign-independently hyperbolic or to have real separated zeros
• 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)