Source author record

Martin Balko

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computational Geometry Discrete Mathematics math.MG math.PR

Catalog footprint

Research overview

10works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Erdős--Szekeres-type problems in the real projective plane

We consider point sets in the real projective plane $\mathbb{R}P^2$ and explore variants of classical extremal problems about planar point sets in this setting, with a main focus on Erdős--Szekeres-type problems. We provide asymptotically tight bounds for a variant of the Erdős--Szekeres theorem about point sets in convex position in $\mathbb{R}P^2$ , which was initiated by Harborth and Möller in 1994. The notion of convex position in $\mathbb{R}P^2$ agrees with the definition of convex sets introduced by Steinitz in 1913. For $k \geq 3$ , an (\affine) $k$ -hole in a finite set $S \subseteq \mathbb{R}^2$ is a set of $k$ points from $S$ in convex position with no point of $S$ in the interior of their convex hull. After introducing a new notion of $k$ -holes for points sets from $\mathbb{R}P^2$ , called projective $k$ -holes, we find arbitrarily large finite sets of points from $\mathbb{R}P^2$ with no \projective 8-holes, providing an analogue of a classical planar construction by Horton from 1983. We also prove that they contain only quadratically many \projective $k$ -holes for $k \leq 7$ . On the other hand, we show that the number of $k$ -holes can be substantially larger in~ $\mathbb{R}P^2$ than in $\mathbb{R}^2$ by constructing, for every $k \in \{3,\dots,6\}$ , sets of $n$ points from $\mathbb{R}^2 \subset \mathbb{R}P^2$ with $Ω(n^{3-3/5k})$ \projective $k$ -holes and only $O(n^2)$ \affine $k$ -holes. Last but not least, we prove several other results, for example about projective holes in random point sets in $\mathbb{R}P^2$ and about some algorithmic aspects. The study of extremal problems about point sets in $\mathbb{R}P^2$ opens a new area of research, which we support by posing several open problems.

preprint2022arXiv

Holes and islands in random point sets

For $d\in\mathbb{N}$ , let $S$ be a set of points in $\mathbb{R}^d$ in general position. A set $I$ of $k$ points from $S$ is a $k$ -island in $S$ if the convex hull $\mathrm{conv}(I)$ of $I$ satisfies $\mathrm{conv}(I) \cap S = I$ . A $k$ -island in $S$ in convex position is a $k$ -hole in $S$ . For $d,k\in\mathbb{N}$ and a convex body $K\subseteq\mathbb{R}^d$ of volume $1$ , let $S$ be a set of $n$ points chosen uniformly and independently at random from $K$ . We show that the expected number of $k$ -holes in $S$ is in $O(n^d)$ . Our estimate improves and generalizes all previous bounds. In particular, we estimate the expected number of empty simplices in $S$ by $2^{d-1}\cdot d!\cdot\binom{n}{d}$ . This is tight in the plane up to a lower-order term. Our method gives an asymptotically tight upper bound $O(n^d)$ even in the much more general setting, where we estimate the expected number of $k$ -islands in $S$ .

preprint2022arXiv

Tight bounds on the expected number of holes in random point sets

For integers $d \geq 2$ and $k \geq d+1$ , a $k$ -hole in a set $S$ of points in general position in $\mathbb{R}^d$ is a $k$ -tuple of points from $S$ in convex position such that the interior of their convex hull does not contain any point from $S$ . For a convex body $K \subseteq \mathbb{R}^d$ of unit $d$ -dimensional volume, we study the expected number $EH^K_{d,k}(n)$ of $k$ -holes in a set of $n$ points drawn uniformly and independently at random from $K$ . We prove an asymptotically tight lower bound on $EH^K_{d,k}(n)$ by showing that, for all fixed integers $d \geq 2$ and $k\geq d+1$ , the number $EH_{d,k}^K(n)$ is at least $Ω(n^d)$ . For some small holes, we even determine the leading constant $\lim_{n \to \infty}n^{-d}EH^K_{d,k}(n)$ exactly. We improve the currently best known lower bound on $\lim_{n \to \infty}n^{-d}EH^K_{d,d+1}(n)$ by Reitzner and Temesvari (2019). In the plane, we show that the constant $\lim_{n \to \infty}n^{-2}EH^K_{2,k}(n)$ is independent of $K$ for every fixed $k \geq 3$ and we compute it exactly for $k=4$ , improving earlier estimates by Fabila-Monroy, Huemer, and Mitsche (2015) and by the authors (2020).

preprint2020arXiv

A superlinear lower bound on the number of 5-holes

Let $P$ be a finite set of points in the plane in general position, that is, no three points of $P$ are on a common line. We say that a set $H$ of five points from $P$ is a $5$ -hole in $P$ if $H$ is the vertex set of a convex $5$ -gon containing no other points of $P$ . For a positive integer $n$ , let $h_5(n)$ be the minimum number of 5-holes among all sets of $n$ points in the plane in general position. Despite many efforts in the last 30 years, the best known asymptotic lower and upper bounds for $h_5(n)$ have been of order $Ω(n)$ and $O(n^2)$ , respectively. We show that $h_5(n) = Ω(n\log^{4/5}{n})$ , obtaining the first superlinear lower bound on $h_5(n)$ . The following structural result, which might be of independent interest, is a crucial step in the proof of this lower bound. If a finite set $P$ of points in the plane in general position is partitioned by a line $\ell$ into two subsets, each of size at least 5 and not in convex position, then $\ell$ intersects the convex hull of some 5-hole in $P$ . The proof of this result is computer-assisted.

preprint2020arXiv

Almost-equidistant sets

For a positive integer $d$ , a set of points in $d$ -dimensional Euclidean space is called almost-equidistant if for any three points from the set, some two are at unit distance. Let $f(d)$ denote the largest size of an almost-equidistant set in $d$ -space. It is known that $f(2)=7$ , $f(3)=10$ , and that the extremal almost-equidistant sets are unique. We give independent, computer-assisted proofs of these statements. It is also known that $f(5) \ge 16$ . We further show that $12\leq f(4)\leq 13$ , $f(5)\leq 20$ , $18\leq f(6)\leq 26$ , $20\leq f(7)\leq 34$ , and $f(9)\geq f(8)\geq 24$ . Up to dimension $7$ , our work is based on various computer searches, and in dimensions $6$ to $9$ , we give constructions based on the known construction for $d=5$ . For every dimension $d \ge 3$ , we give an example of an almost-equidistant set of $2d+4$ points in the $d$ -space and we prove the asymptotic upper bound $f(d) \le O(d^{3/2})$ .

preprint2019arXiv

Ramsey numbers of ordered graphs

An ordered graph is a pair $\mathcal{G}=(G,\prec)$ where $G$ is a graph and $\prec$ is a total ordering of its vertices. The ordered Ramsey number $\overline{R}(\mathcal{G})$ is the minimum number $N$ such that every ordered complete graph with $N$ vertices and with edges colored by two colors contains a monochromatic copy of $\mathcal{G}$ . In contrast with the case of unordered graphs, we show that there are arbitrarily large ordered matchings $\mathcal{M}_n$ on $n$ vertices for which $\overline{R}(\mathcal{M}_n)$ is superpolynomial in $n$ . This implies that ordered Ramsey numbers of the same graph can grow superpolynomially in the size of the graph in one ordering and remain linear in another ordering. We also prove that the ordered Ramsey number $\overline{R}(\mathcal{G})$ is polynomial in the number of vertices of $\mathcal{G}$ if the bandwidth of $\mathcal{G}$ is constant or if $\mathcal{G}$ is an ordered graph of constant degeneracy and constant interval chromatic number. The first result gives a positive answer to a question of Conlon, Fox, Lee, and Sudakov. For a few special classes of ordered paths, stars or matchings, we give asymptotically tight bounds on their ordered Ramsey numbers. For so-called monotone cycles we compute their ordered Ramsey numbers exactly. This result implies exact formulas for geometric Ramsey numbers of cycles introduced by Károlyi, Pach, Tóth, and Valtr.

preprint2016arXiv

On the Beer index of convexity and its variants

Let $S$ be a subset of $\mathbb{R}^d$ with finite positive Lebesgue measure. The Beer index of convexity $\operatorname{b}(S)$ of $S$ is the probability that two points of $S$ chosen uniformly independently at random see each other in $S$ . The convexity ratio $\operatorname{c}(S)$ of $S$ is the Lebesgue measure of the largest convex subset of $S$ divided by the Lebesgue measure of $S$ . We investigate the relationship between these two natural measures of convexity. We show that every set $S\subseteq\mathbb{R}^2$ with simply connected components satisfies $\operatorname{b}(S)\leqα\operatorname{c}(S)$ for an absolute constant $α$ , provided $\operatorname{b}(S)$ is defined. This implies an affirmative answer to the conjecture of Cabello et al. that this estimate holds for simple polygons. We also consider higher-order generalizations of $\operatorname{b}(S)$ . For $1\leq k\leq d$ , the $k$ -index of convexity $\operatorname{b}_k(S)$ of a set $S\subseteq\mathbb{R}^d$ is the probability that the convex hull of a $(k+1)$ -tuple of points chosen uniformly independently at random from $S$ is contained in $S$ . We show that for every $d\geq 2$ there is a constant $β(d)>0$ such that every set $S\subseteq\mathbb{R}^d$ satisfies $\operatorname{b}_d(S)\leqβ\operatorname{c}(S)$ , provided $\operatorname{b}_d(S)$ exists. We provide an almost matching lower bound by showing that there is a constant $γ(d)>0$ such that for every $\varepsilon\in(0,1)$ there is a set $S\subseteq\mathbb{R}^d$ of Lebesgue measure $1$ satisfying $\operatorname{c}(S)\leq\varepsilon$ and $\operatorname{b}_d(S)\geqγ\frac{\varepsilon}{\log_2{1/\varepsilon}}\geqγ\frac{\operatorname{c}(S)}{\log_2{1/\operatorname{c}(S)}}$ .

preprint2014arXiv

Crossing numbers and combinatorial characterization of monotone drawings of $K_n$

In 1958, Hill conjectured that the minimum number of crossings in a drawing of $K_n$ is exactly $Z(n) = \frac{1}{4} \lfloor\frac{n}{2}\rfloor \left\lfloor\frac{n-1}{2}\right\rfloor \left\lfloor\frac{n-2}{2}\right\rfloor\left\lfloor\frac{n-3}{2}\right\rfloor$ . Generalizing the result by Ábrego et al. for 2-page book drawings, we prove this conjecture for plane drawings in which edges are represented by $x$ -monotone curves. In fact, our proof shows that the conjecture remains true for $x$ -monotone drawings of $K_n$ in which adjacent edges may cross an even number of times, and instead of the crossing number we count the pairs of edges which cross an odd number of times. We further discuss a generalization of this result to shellable drawings, a notion introduced by Ábrego et al. We also give a combinatorial characterization of several classes of $x$ -monotone drawings of complete graphs using a small set of forbidden configurations. For a similar local characterization of shellable drawings, we generalize Carathéodory's theorem to simple drawings of complete graphs.

preprint2013arXiv

Bounded Representations of Interval and Proper Interval Graphs

Klavik et al. [arXiv:1207.6960] recently introduced a generalization of recognition called the bounded representation problem which we study for the classes of interval and proper interval graphs. The input gives a graph G and in addition for each vertex v two intervals L_v and R_v called bounds. We ask whether there exists a bounded representation in which each interval I_v has its left endpoint in L_v and its right endpoint in R_v. We show that the problem can be solved in linear time for interval graphs and in quadratic time for proper interval graphs. Robert's Theorem states that the classes of proper interval graphs and unit interval graphs are equal. Surprisingly the bounded representation problem is polynomially solvable for proper interval graphs and NP-complete for unit interval graphs [Klav\'ık et al., arxiv:1207.6960]. So unless P = NP, the proper and unit interval representations behave very differently. The bounded representation problem belongs to a wider class of restricted representation problems. These problems are generalizations of the well-understood recognition problem, and they ask whether there exists a representation of G satisfying some additional constraints. The bounded representation problems generalize many of these problems.

preprint2012arXiv

Grid Representations and the Chromatic Number

A grid drawing of a graph maps vertices to grid points and edges to line segments that avoid grid points representing other vertices. We show that there is a number of grid points that some line segment of an arbitrary grid drawing must intersect. This number is closely connected to the chromatic number. Second, we study how many columns we need to draw a graph in the grid, introducing some new $\NP$-complete problems. Finally, we show that any planar graph has a planar grid drawing where every line segment contains exactly two grid points. This result proves conjectures asked by David Flores-Peñaloza and Francisco Javier Zaragoza Martinez.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Martin Balko

Research overview

Is this your work?

10 publications

Erdős--Szekeres-type problems in the real projective plane

Holes and islands in random point sets

Tight bounds on the expected number of holes in random point sets

A superlinear lower bound on the number of 5-holes

Almost-equidistant sets

Ramsey numbers of ordered graphs

On the Beer index of convexity and its variants

Crossing numbers and combinatorial characterization of monotone drawings of $K_n$

Bounded Representations of Interval and Proper Interval Graphs

Grid Representations and the Chromatic Number

See the researcher in context

Building this map preview

Martin Balko

Research overview

Is this your work?

10 publications

Erdős--Szekeres-type problems in the real projective plane

Holes and islands in random point sets

Tight bounds on the expected number of holes in random point sets

A superlinear lower bound on the number of 5-holes

Almost-equidistant sets

Ramsey numbers of ordered graphs

On the Beer index of convexity and its variants

Crossing numbers and combinatorial characterization of monotone drawings of KnK_nKn​

Bounded Representations of Interval and Proper Interval Graphs

Grid Representations and the Chromatic Number

See the researcher in context

Building this map preview

Crossing numbers and combinatorial characterization of monotone drawings of $K_n$