BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Géza Tóth

Géza Tóth appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.MGComputational GeometryDiscrete Mathematics

Catalog footprint

What is connected

11works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

11 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access