Source author record

Attila Pór

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 math.MG math.NT

Catalog footprint

Research overview

9works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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})$ .

preprint2020arXiv

Random bipartite posets and extremal problems

Previously, Erdős, Kierstead and Trotter investigated the dimension of random height~ $2$ partially ordered sets. Their research was motivated primarily by two goals: (1)~analyzing the relative tightness of the Füredi-Kahn upper bounds on dimension in terms of maximum degree; and (2)~developing machinery for estimating the expected dimension of a random labeled poset on $n$ points. For these reasons, most of their effort was focused on the case $0<p\le 1/2$ . While bounds were given for the range $1/2\le p <1$ , the relative accuracy of the results in the original paper deteriorated as $p$ approaches~ $1$ . Motivated by two extremal problems involving conditions that force a poset to contain a large standard example, we were compelled to revisit this subject, but now with primary emphasis on the range $1/2\le p<1$ . Our sharpened analysis shows that as $p$ approaches~ $1$ , the expected value of dimension increases and then decreases, answering in the negative a question posed in the original paper. Along the way, we apply inequalities of Talagrand and Janson, establish connections with latin rectangles and the Euler product function, and make progress on both extremal problems.

preprint2015arXiv

Forcing Posets with Large Dimension to Contain Large Standard Examples

The dimension of a poset $P$ , denoted $\dim(P)$ , is the least positive integer $d$ for which $P$ is the intersection of $d$ linear extensions of $P$ . The maximum dimension of a poset $P$ with $|P|\le 2n+1$ is $n$ , provided $n\ge2$ , and this inequality is tight when $P$ contains the standard example $S_n$ . However, there are posets with large dimension that do not contain the standard example $S_2$ . Moreover, for each fixed $d\ge2$ , if $P$ is a poset with $|P|\le 2n+1$ and $P$ does not contain the standard example $S_d$ , then $\dim(P)=o(n)$ . Also, for large $n$ , there is a poset $P$ with $|P|=2n$ and $\dim(P)\ge (1-o(1))n$ such that the largest $d$ so that $P$ contains the standard example $S_d$ is $o(n)$ . In this paper, we will show that for every integer $c\ge1$ , there is an integer $f(c)=O(c^2)$ so that for large enough $n$ , if $P$ is a poset with $|P|\le 2n+1$ and $\dim(P)\ge n-c$ , then $P$ contains a standard example $S_d$ with $d\ge n-f(c)$ . From below, we show that $f(c)=Ω(c^{4/3})$ . On the other hand, we also prove an analogous result for fractional dimension, and in this setting $f(c)$ is linear in $c$ . Here the result is best possible up to the value of the multiplicative constant.

preprint2014arXiv

The proof of the removable pair conjecture for fractional dimension

In 1971 Trotter conjectured that every finite poset on at least $3$ points has a pair whose removal does not decrease the dimension by more than $1$ . In 1992 Brightwell and Scheinerman introduced fractional dimension of posets, and they made a similar conjecture for fractional dimension. This paper settles this latter conjecture.

preprint2011arXiv

On the connectivity of visibility graphs

The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. This paper establishes bounds on the edge- and vertex-connectivity of visibility graphs. Unless all its vertices are collinear, a visibility graph has diameter at most 2, and so it follows by a result of Plesník (1975) that its edge-connectivity equals its minimum degree. We strengthen the result of Plesník by showing that for any two vertices v and w in a graph of diameter 2, if deg(v) <= deg(w) then there exist deg(v) edge-disjoint vw-paths of length at most 4. Furthermore, we find that in visibility graphs every minimum edge cut is the set of edges incident to a vertex of minimum degree. For vertex-connectivity, we prove that every visibility graph with n vertices and at most l collinear vertices has connectivity at least (n-1)/(l-1), which is tight. We also prove the qualitatively stronger result that the vertex-connectivity is at least half the minimum degree. Finally, in the case that l=4 we improve this bound to two thirds of the minimum degree.

preprint2010arXiv

Blocking Coloured Point Sets

This paper studies problems related to visibility among points in the plane. A point $x$ \emph{blocks} two points $v$ and $w$ if $x$ is in the interior of the line segment $\bar{vw}$ . A set of points $P$ is \emph{ $k$ -blocked} if each point in $P$ is assigned one of $k$ colours, such that distinct points $v,w\in P$ are assigned the same colour if and only if some other point in $P$ blocks $v$ and $w$ . The focus of this paper is the conjecture that each $k$ -blocked set has bounded size (as a function of $k$ ). Results in the literature imply that every 2-blocked set has at most 3 points, and every 3-blocked set has at most 6 points. We prove that every 4-blocked set has at most 12 points, and that this bound is tight. In fact, we characterise all sets $\{n_1,n_2,n_3,n_4\}$ such that some 4-blocked set has exactly $n_i$ points in the $i$ -th colour class. Amongst other results, for infinitely many values of $k$ , we construct $k$ -blocked sets with $k^{1.79...}$ points.

preprint2009arXiv

Every Large Point Set contains Many Collinear Points or an Empty Pentagon

We prove the following generalised empty pentagon theorem: for every integer $\ell \geq 2$ , every sufficiently large set of points in the plane contains $\ell$ collinear points or an empty pentagon. As an application, we settle the next open case of the "big line or big clique" conjecture of Kára, Pór, and Wood [\emph{Discrete Comput. Geom.} 34(3):497--506, 2005].

preprint2009arXiv

On Visibility and Blockers

This expository paper discusses some conjectures related to visibility and blockers for sets of points in the plane.

preprint2008arXiv

Colourings of the Cartesian Product of Graphs and Multiplicative Sidon Sets

Let $F$ be a family of connected bipartite graphs, each with at least three vertices. A proper vertex colouring of a graph $G$ with no bichromatic subgraph in $F$ is $\F$-free. The $F$ -free chromatic number $χ(G,F)$ of a graph $G$ is the minimum number of colours in an $F$ -free colouring of $G$ . For appropriate choices of $F$ , several well-known types of colourings fit into this framework, including acyclic colourings, star colourings, and distance-2 colourings. This paper studies $F$ -free colourings of the cartesian product of graphs. Let $H$ be the cartesian product of the graphs $G_1,G_2,...,G_d$ . Our main result establishes an upper bound on the $F$ -free chromatic number of $H$ in terms of the maximum $F$ -free chromatic number of the $G_i$ and the following number-theoretic concept. A set $S$ of natural numbers is $k$ -multiplicative Sidon if $ax=by$ implies $a=b$ and $x=y$ whenever $x,y\in S$ and $1\leq a,b\leq k$ . Suppose that $χ(G_i,F)\leq k$ and $S$ is a $k$ -multiplicative Sidon set of cardinality $d$ . We prove that $χ(H,F) \leq 1+2k\cdot\max S$ . We then prove that the maximum density of a $k$ -multiplicative Sidon set is $Θ(1/\log k)$ . It follows that $χ(H,F) \leq O(dk\log k)$ . We illustrate the method with numerous examples, some of which generalise or improve upon existing results in the literature.

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.