BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Janos Pach

Janos Pach contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.COComputational GeometryDiscrete Mathematicsmath.MGmath.NT

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
10works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

10 published item(s)

preprint2026arXiv

Enumeration of intersection graphs of $x$-monotone curves

A curve in the plane is $x$-monotone if every vertical line intersects it at most once. A family of curves are called pseudo-segments if every pair of them have at most one point in common. We construct $2^{Ω(n^{4/3})}$ families, each consisting of $n$ labelled $x$-monotone pseudo-segments such that their intersection graphs are different. On the other hand, we show that the number of such intersection graphs is at most $2^{O(n^{4/3}\log^2n)}$. Our proof uses a new upper bound on the number of set systems of size $m$ on a ground set of size $n$, with VC-dimension at most $d$. Much better upper bounds are obtained if we only count bipartite intersection graphs, or, in general, intersection graphs with bounded chromatic number.

0 citations0 reviewsNo code linkedOpen access
preprint2025arXiv

Polynomial extensions of Raimi's theorem

Raimi's theorem guarantees the existence of a partition of $\mathbb{N}$ into two parts with an unavoidable intersection property: for any finite coloring of $\mathbb{N}$, some color class intersects both parts infinitely many times, after an appropriate shift (translation). We establish a polynomial extension of this result, proving that such intersections persist under polynomial shifts in any dimension. Let $P^{(1)},\dots,P^{(f)}\in\mathbb{Z}[x]$ be non-constant polynomials with positive leading coefficients and $P^{(j)}(0)=0$ for every $j$. We construct a partition of $\mathbb{N}^k$ into an arbitrarily fixed finite number of pieces such that for any coloring of $\mathbb{N}^k$ with finitely many colors, there exist $x_0\in \mathbb{N}$ and a single color class that meets all partition pieces after shifts by $x_0+P^{(j)}(h)$ in each of the $k$ coordinate directions, for every $j$ and infinitely many values $h\in \mathbb{N}$. Our proof exploits Weyl's equidistribution theory, Pontryagin duality, and the structure of polynomial relation lattices. We also prove some finite analogues of the above results for abelian groups and $SL_2(\mathbb{F}_q)$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the number of edges of separated multigraphs

We prove that the number of edges of a multigraph $G$ with $n$ vertices is at most $O(n^2\log n)$, provided that any two edges cross at most once, parallel edges are noncrossing, and the lens enclosed by every pair of parallel edges in $G$ contains at least one vertex. As a consequence, we prove the following extension of the Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi and Leighton, if $G$ has $e \geq 4n$ edges, in any drawing of $G$ with the above property, the number of crossings is $Ω\left(\frac{e^3}{n^2\log(e/n)}\right)$. This answers a question of Kaufmann et al. and is tight up to the logarithmic factor.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Optimal embedded and enclosing isosceles triangles

Given a triangle $Δ$, we study the problem of determining the smallest enclosing and largest embedded isosceles triangles of $Δ$ with respect to area and perimeter. This problem was initially posed by Nandakumar and was first studied by Kiss, Pach, and Somlai, who showed that if $Δ'$ is the smallest area isosceles triangle containing $Δ$, then $Δ'$ and $Δ$ share a side and an angle. In the present paper, we prove that for any triangle $Δ$, every maximum area isosceles triangle embedded in $Δ$ and every maximum perimeter isosceles triangle embedded in $Δ$ shares a side and an angle with $Δ$. Somewhat surprisingly, the case of minimum perimeter enclosing triangles is different: there are infinite families of triangles $Δ$ whose minimum perimeter isosceles containers do not share a side and an angle with $Δ$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Shattered matchings in intersecting hypergraphs

Let $X$ be an $n$-element set, where $n$ is even. We refute a conjecture of J. Gordon and Y. Teplitskaya, according to which, for every maximal intersecting family $\mathcal{F}$ of $\frac{n}2$-element subsets of $X$, one can partition $X$ into $\frac{n}2$ disjoint pairs in such a way that no matter how we pick one element from each of the first $\frac{n}2 - 1$ pairs, the set formed by them can always be completed to a member of $\mathcal{F}$ by adding an element of the last pair. The above problem is related to classical questions in extremal set theory. For any $t\ge 2$, we call a family of sets $\mathcal{F}\subset 2^X$ {\em $t$-separable} if for any ordered pair of elements $(x,y)$ of $X$, there exists $F\in\mathcal{F}$ such that $F\cap\{x,y\}=\{x\}$. For a fixed $t, 2\le t\le 5$ and $n\rightarrow\infty$, we establish asymptotically tight estimates for the smallest integer $s=s(n,t)$ such that every family $\mathcal{F}$ with $|\mathcal{F}|\ge s$ is $t$-separable.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Applications of a new separator theorem for string graphs

An intersection graph of curves in the plane is called a string graph. Matousek almost completely settled a conjecture of the authors by showing that every string graph of m edges admits a vertex separator of size O(\sqrt{m}\log m). In the present note, this bound is combined with a result of the authors, according to which every dense string graph contains a large complete balanced bipartite graph. Three applications are given concerning string graphs G with n vertices: (i) if K_t is not a subgraph of G for some t, then the chromatic number of G is at most (\log n)^{O(\log t)}; (ii) if K_{t,t} is not a subgraph of G, then G has at most t(\log t)^{O(1)}n edges,; and (iii) a lopsided Ramsey-type result, which shows that the Erdos-Hajnal conjecture almost holds for string graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The number of edges in k-quasi-planar graphs

A graph drawn in the plane is called k-quasi-planar if it does not contain k pairwise crossing edges. It has been conjectured for a long time that for every fixed k, the maximum number of edges of a k-quasi-planar graph with n vertices is O(n). The best known upper bound is n(\log n)^{O(\log k)}. In the present note, we improve this bound to (n\log n)2^{α^{c_k}(n)} in the special case where the graph is drawn in such a way that every pair of edges meet at most once. Here α(n) denotes the (extremely slowly growing) inverse of the Ackermann function. We also make further progress on the conjecture for k-quasi-planar graphs in which every edge is drawn as an x-monotone curve. Extending some ideas of Valtr, we prove that the maximum number of edges of such graphs is at most 2^{ck^6}n\log n.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A computational approach to Conway's thrackle conjecture

A drawing of a graph in the plane is called a thrackle if every pair of edges meets precisely once, either at a common vertex or at a proper crossing. Let t(n) denote the maximum number of edges that a thrackle of n vertices can have. According to a 40 years old conjecture of Conway, t(n)=n for every n>2. For any eps>0, we give an algorithm terminating in e^{O((1/eps^2)ln(1/eps))} steps to decide whether t(n)<(1+eps)n for all n>2. Using this approach, we improve the best known upper bound, t(n)<=3/2(n-1), due to Cairns and Nikolayevsky, to 167/117n<1.428n.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Overlap properties of geometric expanders

The {\em overlap number} of a finite $(d+1)$-uniform hypergraph $H$ is defined as the largest constant $c(H)\in (0,1]$ such that no matter how we map the vertices of $H$ into $\R^d$, there is a point covered by at least a $c(H)$-fraction of the simplices induced by the images of its hyperedges. In~\cite{Gro2}, motivated by the search for an analogue of the notion of graph expansion for higher dimensional simplicial complexes, it was asked whether or not there exists a sequence $\{H_n\}_{n=1}^\infty$ of arbitrarily large $(d+1)$-uniform hypergraphs with bounded degree, for which $\inf_{n\ge 1} c(H_n)>0$. Using both random methods and explicit constructions, we answer this question positively by constructing infinite families of $(d+1)$-uniform hypergraphs with bounded degree such that their overlap numbers are bounded from below by a positive constant $c=c(d)$. We also show that, for every $d$, the best value of the constant $c=c(d)$ that can be achieved by such a construction is asymptotically equal to the limit of the overlap numbers of the complete $(d+1)$-uniform hypergraphs with $n$ vertices, as $n\rightarrow\infty$. For the proof of the latter statement, we establish the following geometric partitioning result of independent interest. For any $d$ and any $ε>0$, there exists $K=K(ε,d)\ge d+1$ satisfying the following condition. For any $k\ge K$, for any point $q \in \mathbb{R}^d$ and for any finite Borel measure $μ$ on $\mathbb{R}^d$ with respect to which every hyperplane has measure $0$, there is a partition $\mathbb{R}^d=A_1 \cup \ldots \cup A_{k}$ into $k$ measurable parts of equal measure such that all but at most an $ε$-fraction of the $(d+1)$-tuples $A_{i_1},\ldots,A_{i_{d+1}}$ have the property that either all simplices with one vertex in each $A_{i_j}$ contain $q$ or none of these simplices contain $q$.

0 citations0 reviewsNo code linkedOpen access