Jan Soukup

collaborators

4 papers

cs.GT2024

On Approximately Strategy-Proof Tournament Rules for Collusions of Size at Least Three

David Mikšaník, Ariel Schvartzman, Jan Soukup

A tournament organizer must select one of $n$ possible teams as the winner of a competition after observing all $(2 n)$ matches between them. The organizer would like to fin…

cs.CG2024

Connected Matchings

Oswin Aichholzer, Sergio Cabello, Viola Mészáros +2

We show that each set of $n \geq 2$ points in the plane in general position has a straight-line matching with at least $(5 n + 1) /27$ edges whose segments form a connected set, and such…

math.CO2024

Bicolored point sets admitting non-crossing alternating Hamiltonian paths

Jan Soukup

Consider a bicolored point set $P$ in general position in the plane consisting of $n$ blue and $n$ red points. We show that if a subset of the red points forms the vertices of a co…

math.CO2023

Extending simple monotone drawings

Jan Kynčl, Jan Soukup

We prove the following variant of Levi's Enlargement Lemma: for an arbitrary arrangement $A$ of $x$ -monotone pseudosegments in the plane and a pair of points $a, b$ with d…