29 citations · 92 across the 53 of their papers we have counts for
54 papers · 1 filter
A cyclic non-Ramsey heptagon
Dömötör Pálvölgyi
We present a construction with seven points on a circle that is not Ramsey, disproving a conjecture of Erdős, Graham, Montgomery, Rothschild, Spencer and Straus.
A nearcircumsphere-Ramsey Theorem for Solvable Transitive Configurations
Dömötör Pálvölgyi
Let P be a finite spherical set. We prove that if P admits a solvable group of isometries acting transitively on it, then every r-coloring of a sufficiently high-dimensional sphere…
Note on polychromatic coloring of hereditary hypergraph families II
Dömötör Pálvölgyi
We extend a recent construction concerning polychromatic colorings of hereditary hypergraph families. For every integer we construct a -uniform hypergraph which ha…
Coloring Geometric Hypergraphs: A Survey
Gábor Damásdi, Balázs Keszegh, János Pach +2
The \emph{chromatic number} of a hypergraph is the smallest number of colors needed to color the vertices such that no edge of at least two vertices is monochromatic. Given a famil…
Erdős-Szekeres Maker-Breaker Games
Aleksa Džuklevski, Dömötör Pálvölgyi, Alexey Pokrovskiy +3
We present new results on Maker-Breaker games arising from the Erdős-Szekeres problem in planar geometry. This classical problem asks how large a set in general position has to be…
The complexity of recognizing -free hypergraphs
Gábor Damásdi, Balázs Keszegh, Dömötör Pálvölgyi +1
The study of geometric hypergraphs gave rise to the notion of -free hypergraphs. A hypergraph is called -free if there is an ordering of its vertices such…
On dual-ABAB-free and related hypergraphs
Balázs Keszegh, Dömötör Pálvölgyi
Geometric motivations warranted the study of hypergraphs on ordered vertices that have no pair of hyperedges that induce an alternation of some given length. Such hypergraphs are c…
Odd-Sunflowers
Peter Frankl, János Pach, Dömötör Pálvölgyi
Extending the notion of sunflowers, we call a family of at least two sets an odd-sunflower if every element of the underlying set is contained in an odd number of sets or in none o…
The double Hall property and cycle covers in bipartite graphs
János Barát, Andrzej Grzesik, Attila Jung +2
In a graph , the -neighborhood of a vertex set consists of all vertices of having at least neighbors in . We say that a bipartite graph satisfies the…
Note on polychromatic coloring of hereditary hypergraph families
Dömötör Pálvölgyi
We exhibit a 5-uniform hypergraph that has no polychromatic 3-coloring, but all its restricted subhypergraphs with edges of size at least 3 are 2-colorable. This disproves a bold c…
Query complexity of Boolean functions on the middle slice of the cube
Dániel Gerbner, Balázs Keszegh, Dániel T. Nagy +4
We study the query complexity on slices of Boolean functions. Among other results we show that there exists a Boolean function for which we need to query all but 7 input bits to co…
Projective and external saturation problem for posets
Dömötör Pálvölgyi, Balázs Patkós
We introduce two variants of the poset saturation problem. For a poset and the Boolean lattice , a family of sets, not necessarily from $\mathcal{B…
On graphs that contain exactly k copies of a subgraph, and a related problem in search theory
Dániel Gerbner, Balázs Keszegh, Dániel Lenger +5
We study , the largest number of edges in an -vertex graph that contains exactly copies of a given subgraph . The case is the Turán number…
Orientation of good covers
Péter Ágoston, Gábor Damásdi, Balázs Keszegh +1
We study systems of orientations on triples that satisfy the following so-called interiority condition: impl…
Orientation of convex sets
Péter Ágoston, Gábor Damásdi, Balázs Keszegh +1
We introduce a novel definition of orientation on the triples of a family of pairwise intersecting planar convex sets and study its properties. In particular, we compare it to othe…
Three-chromatic geometric hypergraphs
Gábor Damásdi, Dömötör Pálvölgyi
We prove that for any planar convex body C there is a positive integer m with the property that any finite point set P in the plane can be three-colored such that there is no trans…
The number of tangencies between two families of curves
Balázs Keszegh, Dömötör Pálvölgyi
We prove that the number of tangencies between the members of two families, each of which consists of pairwise disjoint curves, can be as large as . We show that fr…
On tangencies among planar curves with an application to coloring L-shapes
Eyal Ackerman, Balázs Keszegh, Dömötör Pálvölgyi
We prove that there are tangencies among any set of red and blue planar curves in which every pair of curves intersects at most once and no two curves of the same color…
Exchange properties of finite set-systems
Peter Frankl, János Pach, Dömötör Pálvölgyi
In a recent breakthrough, Adiprasito, Avvakumov, and Karasev constructed a triangulation of the -dimensional real projective space with a subexponential number of vertices. They…
On the number of hyperedges in the hypergraph of lines and pseudo-discs
Chaya Keller, Balázs Keszegh, Dömötör Pálvölgyi
Consider the hypergraph whose vertex set is a family of lines in general position in the plane, and whose hyperedges are induced by intersections with a family of pseudo-discs.…
Realizing an m-uniform four-chromatic hypergraph with disks
Gábor Damásdi, Pálvölgyi Dömötör
We prove that for every there is a finite point set in the plane such that no matter how is three-colored, there is always a disk containing exactly…
An improved constant factor for the unit distance problem
Péter Ágoston, Dömötör Pálvölgyi
We prove that the number of unit distances among planar points is at most , improving on the previous best bound of . We also give better upper and…
Induced and non-induced poset saturation problems
Balázs Keszegh, Nathan Lemons, Ryan R. Martin +2
A subfamily of sets is a non-induced (weak) copy of a poset in if there exists a bijection $i:P\rightarrow \ma…
Turán problems for Edge-ordered graphs
Dániel Gerbner, Abhishek Methuku, Dániel T. Nagy +3
In this paper we initiate a systematic study of the Turán problem for edge-ordered graphs. A simple graph is called , if its edges are linearly ordered. An i…