Source author record

Géza Tóth

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

ResearcherUnclaimed source record

math.CO math.MG Computational Geometry Discrete Mathematics

Catalog footprint

Research overview

11works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Helly-type theorems for the ordering of the vertices of a hypergraph

Let $H$ be a complete $r$ -uniform hypergraph such that two vertices are marked in each edge as its `boundary' vertices. A linear ordering of the vertex set of $H$ is called an {\em agreeing linear order}, provided all vertices of each edge of $H$ lie between its two boundary vertices. We prove the following Helly-type theorem: if there is an {agreeing linear order} on the vertex set of every subhypergraph of $H$ with at most $2r-2$ vertices, then there is an agreeing linear order on the vertex set of $H$ . We also show that the constant $2r-2$ cannot be reduced in the theorem. The case $r=3$ of the theorem has particular interest in the axiomatic theory of betweenness. Similar results are obtained for further $r$ -uniform hypergraphs ( $r\geq 3$ ), where one or two vertices are marked in each edge, and the linear orders need to satisfy various rules of agreement. In one of the cases we prove that no such Helly-type statement holds.

preprint2023arXiv

Two trees are better than one

We consider partitions of a point set into two parts, and the lengths of the minimum spanning trees of the original set and of the two parts. If $w(P)$ denotes the length of a minimum spanning tree of $P$ , we show that every set $P$ of $n \geq 12$ points admits a bipartition $P= R \cup B$ for which the ratio $\frac{w(R)+w(B)}{w(P)}$ is strictly larger than $1$ ; and that $1$ is the largest number with this property. Furthermore, we provide a very fast algorithm that computes such a bipartition in $O(1)$ time and one that computes the corresponding ratio in $O(n \log{n})$ time. In certain settings, a ratio larger than $1$ can be expected and sometimes guaranteed. For example, if $P$ is a set of $n$ random points uniformly distributed in $[0,1]^2$ ( $n \to \infty$ ), then for any $\eps>0$, the above ratio in a maximizing partition is at least $\sqrt2 -\eps$ with probability tending to $1$ . As another example, if $P$ is a set of $n$ points with spread at most $α\sqrt{n}$ , for some constant $α>0$ , then the aforementioned ratio in a maximizing partition is $1 + Ω(α^{-2})$ . All our results and techniques are extendable to higher dimensions.

preprint2022arXiv

Crossing lemma for the odd-crossing number

A graph is $1$ -planar, if it can be drawn in the plane such that there is at most one crossing on every edge. It is known, that $1$ -planar graphs have at most $4n-8$ edges. We prove the following odd-even generalization. If a graph can be drawn in the plane such that every edge is crossed by at most one other edge {\em an odd number of times}, then it is called 1-odd-planar and it has at most $5n-9$ edges. As a consequence, we improve the constant in the Crossing Lemma for the odd-crossing number, if adjacent edges cross an even number of times. We also give upper bound for the number of edges of $k$ -odd-planar graphs.

preprint2020arXiv

Crossings between non-homotopic edges

We call a multigraph {\em non-homotopic} if it can be drawn in the plane in such a way that no two edges connecting the same pair of vertices can be continuously transformed into each other without passing through a vertex, and no loop can be shrunk to its end-vertex in the same way. It is easy to see that a non-homotopic multigraph on $n>1$ vertices can have arbitrarily many edges. We prove that the number of crossings between the edges of a non-homotopic multigraph with $n$ vertices and $m>4n$ edges is larger than $c\frac{m^2}{n}$ for some constant $c>0$ , and that this bound is tight up to a polylogarithmic factor. We also show that the lower bound is not asymptotically sharp as $n$ is fixed and $m$ tends to infinity.

preprint2020arXiv

Improvement on the crossing number of crossing-critical graphs

The crossing number of a graph $G$ is the minimum number of edge crossings over all drawings of $G$ in the plane. A graph $G$ is $k$ -crossing-critical if its crossing number is at least $k$ , but if we remove any edge of $G$ , its crossing number drops below $k$ . There are examples of $k$ -crossing-critical graphs that do not have drawings with exactly $k$ crossings. Richter and Thomassen proved in 1993 that if $G$ is $k$ -crossing-critical, then its crossing number is at most $2.5k+16$ . We improve this bound to $2k+6\sqrt{k}+44$ .

preprint2015arXiv

Erdős - Szekeres Theorem for Lines

According to the Erdős-Szekeres theorem, for every $n$ , a sufficiently large set of points in general position in the plane contains $n$ in convex position. In this note we investigate the line version of this result, that is, we want to find $n$ lines in convex position in a sufficiently large set of lines that are in general position. We prove almost matching upper and lower bounds for the minimum size of the set of lines in general position that always contains $n$ in convex position. This is quite unexpected, since in the case of points, the best known bounds are very far from each other. We also establish the dual versions of many variants and generalizations of the Erd\H os-Szekeres theorem.

preprint2015arXiv

Improvements on the density of maximal 1-planar graphs

A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. A graph, together with a 1-planar drawing is called 1-plane. Brandenburg et al. showed that there are maximal 1-planar graphs with only $\frac{45}{17}n + O(1)\approx 2.647n$ edges and maximal 1-plane graphs with only $\frac{7}{3}n+O(1)\approx 2.33n$ edges. On the other hand, they showed that a maximal 1-planar graph has at least $\frac{28}{13}n-O(1)\approx 2.15n-O(1)$ edges, and a maximal 1-plane graph has at least $2.1n-O(1)$ edges. We improve both lower bounds to $\frac{20n}{9}\approx 2.22n$ .

preprint2015arXiv

Separation with restricted families of sets

Given a finite $n$ -element set $X$ , a family of subsets ${\mathcal F}\subset 2^X$ is said to separate $X$ if any two elements of $X$ are separated by at least one member of $\mathcal F$ . It is shown that if $|\mathcal F|>2^{n-1}$ , then one can select $\lceil\log n\rceil+1$ members of $\mathcal F$ that separate $X$ . If $|\mathcal F|\ge α2^n$ for some $0<α<1/2$ , then $\log n+O(\log\frac1α\log\log\frac1α)$ members of $\mathcal F$ are always sufficient to separate all pairs of elements of $X$ that are separated by some member of $\mathcal F$ . This result is generalized to simultaneous separation in several sets. Analogous questions on separation by families of bounded Vapnik-Chervonenkis dimension and separation of point sets in ${\mathbb{R}}^d$ by convex sets are also considered.

preprint2014arXiv

Multiple coverings with closed polygons

A planar set $P$ is said to be cover-decomposable if there is a constant $k=k(P)$ such that every $k$ -fold covering of the plane with translates of $P$ can be decomposed into two coverings. It is known that open convex polygons are cover-decomposable. Here we show that closed, centrally symmetric convex polygons are also cover-decomposable. We also show that an infinite-fold covering of the plane with translates of $P$ can be decomposed into two infinite-fold coverings. Both results hold for coverings of any subset of the plane.

preprint2014arXiv

Saturated simple and $k$ -simple topological graphs

A simple topological graph $G$ is a graph drawn in the plane so that any pair of edges have at most one point in common, which is either an endpoint or a proper crossing. $G$ is called saturated if no further edge can be added without violating this condition. We construct saturated simple topological graphs with $n$ vertices and $O(n)$ edges. For every $k>1$ , we give similar constructions for $k$ -simple topological graphs, that is, for graphs drawn in the plane so that any two edges have at most $k$ points in common. We show that in any $k$ -simple topological graph, any two independent vertices can be connected by a curve that crosses each of the original edges at most $2k$ times. Another construction shows that the bound $2k$ cannot be improved. Several other related problems are also considered.

preprint2012arXiv

Improvement on the decay of crossing numbers

We prove that the crossing number of a graph decays in a continuous fashion in the following sense. For any epsilon>0 there is a delta>0 such that for a sufficiently large n, every graph G with n vertices and m > n^{1+epsilon} edges, has a subgraph G' of at most (1-delta)m edges and crossing number at least (1-epsilon)cr(G). This generalizes the result of J. Fox and Cs. Toth.

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.

Géza Tóth

Research overview

Is this your work?

11 publications

Helly-type theorems for the ordering of the vertices of a hypergraph

Two trees are better than one

Crossing lemma for the odd-crossing number

Crossings between non-homotopic edges

Improvement on the crossing number of crossing-critical graphs

Erdős - Szekeres Theorem for Lines

Improvements on the density of maximal 1-planar graphs

Separation with restricted families of sets

Multiple coverings with closed polygons

Saturated simple and $k$ -simple topological graphs

Improvement on the decay of crossing numbers

See the researcher in context

Building this map preview

Géza Tóth

Research overview

Is this your work?

11 publications

Helly-type theorems for the ordering of the vertices of a hypergraph

Two trees are better than one

Crossing lemma for the odd-crossing number

Crossings between non-homotopic edges

Improvement on the crossing number of crossing-critical graphs

Erdős - Szekeres Theorem for Lines

Improvements on the density of maximal 1-planar graphs

Separation with restricted families of sets

Multiple coverings with closed polygons

Saturated simple and kkk-simple topological graphs

Improvement on the decay of crossing numbers

See the researcher in context

Building this map preview

Saturated simple and $k$ -simple topological graphs