List of Publications

Dömötör Pálvölgyi

Papers and preprints:

Attila Jung, Dömötör Pálvölgyi. k-dimensional transversals for balls. [arxiv]

János Barát, Andrzej Grzesik, Attila Jung, Zoltán Lóránt Nagy, Dömötör Pálvölgyi. The double Hall property and cycle covers in bipartite graphs. [arxiv]

Dániel Gerbner, Balázs Keszegh, Dániel T. Nagy, Kartal Nagy, Dömötör Pálvölgyi, Balázs Patkós, Gábor Wiener. Query complexity of Boolean functions on the middle slice of the cube. [arxiv]

Dömötör Pálvölgyi. Note on polychromatic coloring of hereditary hypergraph families. [arxiv]

Dömötör Pálvölgyi, Balázs Patkós. Projective and external saturation problem for posets. [arxiv]

Gábor Damásdi, Nóra Frankl, János Pach, Dömötör Pálvölgyi. Monochromatic configurations on a circle. Conference version in Eurocomb 2023. [conference]

Peter Frankl, János Pach, Dömötör Pálvölgyi. Odd-Sunflowers. Conference version in Eurocomb 2023. [arxiv conference]

Márton Benedek, Péter Biró, Walter Kern, Dömötör Pálvölgyi, Daniël Paulusma. Partitioned Matching Games for International Kidney Exchange. [arxiv]

Dániel Gerbner, Balázs Keszegh, Dániel Lenger, Dániel T. Nagy, Dömötör Pálvölgyi, Balázs Patkós, Máté Vizer, Gábor Wiener. On graphs that contain exactly k copies of a subgraph, and a related problem in search theory. Discrete Applied Mathematics, 341 (December 2023), 196-203. [arxiv journal]

Péter Ágoston, Gábor Damásdi, Balázs Keszegh, Dömötör Pálvölgyi. Orientation of good covers. [arxiv]

Péter Ágoston, Gábor Damásdi, Balázs Keszegh, Dömötör Pálvölgyi. Orientation of convex sets. [arxiv]

Balázs Keszegh, Dömötör Pálvölgyi. The number of tangencies between two families of curves. Combinatorica, online first. [arxiv journal]

Gábor Damásdi, Dömötör Pálvölgyi. Three-chromatic geometric hypergraphs. Journal of the European Mathematical Society, to appear. Conference version in proceedings of SoCG 2022. [arxiv conference]

Gábor Damásdi, Dömötör Pálvölgyi. Unit disks hypergraphs are three-colorable. Only in proceedings of Eurocomb 2021. [.pdf conference]

Michael A. Bekos, Martin Gronemann, Fabrizio Montecchiani, Dömötör Pálvölgyi, Antonios Symvonis, Leonidas Theocharous. Grid Drawings of Graphs with Constant Edge-Vertex Resolution. Computational Geometry, 98 (October 2021), 101789. [arxiv journal]

Chaya Keller, Balázs Keszegh, Dömötör Pálvölgyi. On the number of hyperedges in the hypergraph of lines and pseudo-discs. Electronic Journal of Combinatorics, 29(3): P3.25, 2022. [arxiv journal]

Peter Frankl, János Pach, Dömötör Pálvölgyi. Exchange properties of finite set-systems. SIAM Journal on Discrete Mathematics, 36(3): 2073-2081, 2022. Conference version in Eurocomb 2021, 617-624. [arxiv journal]

John Fearnley, Dömötör Pálvölgyi, Rahul Savani. A faster algorithm for finding Tarski fixed points. ACM Transactions on Algorithms, 18(3), article 23, 23 pages, 2022. [arxiv journal]

Eyal Ackerman, Balázs Keszegh, Dömötör Pálvölgyi. On tangencies among planar curves with an application to coloring L-shapes. European Journal of Combinatorics, 2023, available online. (Conference version in proceedings of of Eurocomb 2021, 123-128.) [arxiv journal]

Gábor Damásdi, Dömötör Pálvölgyi. Realizing an m-uniform four-chromatic hypergraph with disks. Combinatorica 42: 1027-1048, 2022. (Conference version in proceedings of CCCG 2020.) [arxiv journal conference]

Cory Palmer, Dömötör Pálvölgyi. At most 3.55^n stable matchings. Proceedings of FOCS 2021, 217-227, 2022. [arxiv conference]

Péter Ágoston, Dömötör Pálvölgyi. Improved constant factor for the unit distance problem. Studia Scientiarum Mathematicarum Hungarica: Combinatorics, Geometry and Topology, 59(1): 40-57, 2022. Conference version in EuroCG 2020. [arxiv journal conference]

Dmitrii Zhelezov, Dömötör Pálvölgyi. Query complexity and the polynomial Freiman-Ruzsa conjecture. Advances in Mathematics 392 (December 2021), 108043 [arxiv journal corrigendum]

Balázs Keszegh, Nathan Lemons, Ryan R. Martin, Dömötör Pálvölgyi, Balázs Patkós. Induced and non-induced poset saturation problems. Journal of Combinatorial Theory A 184 (November 2021), 105497. [arxiv journal]

Dániel Gerbner, Abhishek Methuku, Dániel T. Nagy, Dömötör Pálvölgyi, Gábor Tardos, Máté Vizer. Turán problems for Edge-ordered graphs. Journal of Combinatorial Theory B 160 (May 2023), 66-113. [arxiv journal]

Jean Cardinal, Kolja Knauer, Piotr Micek, Dömötör Pálvölgyi, Torsten Ueckerdt, Narmada Varadarajan Colouring bottomless rectangles and arborescences. Computational Geometry: Theory and Applications 115 (December 2023), 102020. Proceedings of EuroCG 2020. [arxiv journal conference]

Nóra Frankl, Tamás Hubai and Dömötör Pálvölgyi. Almost-monochromatic sets and the chromatic number of the plane. Discrete and Computational Geometry, online published. Proceedings of SoCG 2020. [arxiv journal conference]

Dömötör Pálvölgyi. Radon numbers grow linearly. Discrete and Computational Geometry, 68(1):165-171, 2022. Proceedings of SoCG 2020. [arxiv journal conference]

Anat Ganor, Karthik C. S. and Dömötör Pálvölgyi. On Communication Complexity of Fixed Point Computation. ACM Transactions on Economics and Computation, 9(4):1-27, 2021. [arxiv journal]

Péter Biró, Walter Kern, Dömötör Pálvölgyi, Daniël Paulusma. Generalized Matching Games for International Kidney Exchange. Proceedings of the 18th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 413-421, 2019. [conference]

Dömötör Pálvölgyi. Exponential lower bound for Berge-Ramsey problems. Graphs and Combinatorics, 37(4), 1433-1435 (2021). [arxiv journal]

Gábor Damásdi, Dániel Gerbner, Gyula O.H. Katona, Balázs Keszegh, Dániel Lenger, Abhishek Methuku, Dániel T. Nagy, Dömötör Pálvölgyi, Balázs Patkós, Máté Vizer, Gábor Wiener. Adaptive Majority Problems for Restricted Query Graphs and for Weighted Sets. Discrete Applied Mathematics, 288 (2021), 235-245. (Conference version in Acta Mathematica Universitatis Comenianae 88(3) (Eurocomb 2019): 601-609, 2019.) [arxiv journal]

András Gyárfás, Dömötör Pálvölgyi, Patkós Balázs and Matthew Wales. Distribution of colors in Gallai colorings. European Journal of Combinatorics, 86 (2020), 103087. [arxiv journal]

Eyal Ackerman, Balázs Keszegh and Dömötör Pálvölgyi. Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs. SIAM J. on Discrete Math, 34(4) (2020), 2250-2269. (Conference version in Acta Mathematica Universitatis Comenianae 88(3) (Eurocomb 2019): 363-370, 2019.) [arxiv journal]

Dömötör Pálvölgyi. The range of non-linear natural polynomials cannot be context-free. Kybernetika, 56(4):722-726, 2020. [arxiv journal]

Dömötör Pálvölgyi and Gábor Tardos. Unlabeled Compression Schemes Exceeding the VC-dimension. Discrete Applied Mathematics, 276:102-107, 2020. [arxiv journal]

Balázs Keszegh and Dömötör Pálvölgyi. Aligned plane drawings of the generalized Delaunay-graphs for pseudo-disks. Journal of Computational Geometry, 11(1): 354-370, 2020. [arxiv journal]

Eyal Ackerman, Balázs Keszegh and Dömötör Pálvölgyi. Coloring Delaunay-Edges and their Generalizations. Computational Geometry: Theory and Applications, 96 (2021), 101745. [arxiv journal]

Zoltán Király and Dömötör Pálvölgyi. Acyclic orientations with degree constraints. [arxiv]

Dömötör Pálvölgyi. Complexity of Domination in Triangulated Plane Graphs. Acta Univ. Sapientiae Informatica, 11(2):174-183, 2019. [arxiv journal]

Benjamin Gunby and Dömötör Pálvölgyi. Asymptotics of Pattern Avoidance in the Klazar Set Partition and Permutation-Tuple Settings. European Journal of Combinatorics, 82:1-21, 2019. [arxiv journal]

Dömötör Pálvölgyi. All or Nothing Caching Games with Bounded Queries. International Game Theory Review, 20(1):1-9, 2018. [arxiv journal]

Balázs Keszegh and Dömötör Pálvölgyi. Proper Coloring of Geometric Hypergraphs. Discrete and Computational Geometry, 62(3), 674-689, 2019. (Conference version in LIPIcs 77 (SoCG 2017): 47:1-47:15.) [arxiv conference journal]

Radoslav Fulek, Jan Kynčl, and Dömötör Pálvölgyi. Unified Hanani-Tutte theorem. Electronic Journal of Combinatorics, 24(3):1-8, 2017. [arxiv journal]

Dömötör Pálvölgyi. Weak embeddings of posets to the Boolean lattice. Discrete Mathematics and Theoretical Computer Science, 20(1):1-10, 2018. [arxiv journal]

Dániel Gerbner, Balázs Keszegh, Dömötör Pálvölgyi, Patkós Balázs, Máté Vizer and Gábor Wiener. Finding a non-minority ball with majority answers. Discrete Applied Mathematics, 219: 18-31, 2017. (Conference version in Electronic Notes in Discrete Mathematics 49 (Eurocomb 2015): 345-351, 2015.) [arxiv journal conference]

Balázs Keszegh and Dömötör Pálvölgyi. More on Decomposing Coverings by Octants. Journal of Computational Geometry, 6(1): 300-315, 2015. [arxiv journal]

Balázs Keszegh and Dömötör Pálvölgyi. An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes. Journal of Computational Geometry, 10(1):1-26, 2019. (Conference version in LNCS 9224 (WG 2015): 266-280.) [arxiv journal conference]

Dömötör Pálvölgyi and Gyuri Venter. Multiple Equilibria in Noisy Rational Expectations Economies. [ssrn]

Abhishek Methuku and Dömötör Pálvölgyi. Forbidden hypermatrices imply general bounds on induced forbidden subposet problems. Combinatorics, Probability and Computing, 26: 593-602, 2017. [arxiv journal]

Ferdinando Cicalese, Balázs Keszegh, Bernard Lidický, Dömötör Pálvölgyi and Tomáš Valla. On the Tree Search Problem with Non-uniform Costs. Theoretical Computer Science, 647: 22-32, 2016. (Conference version in LNCS 9224 (WG 2015): 90-102.) [arxiv journal]

Dániel Gerbner, Balázs Keszegh, Cory Palmer and Dömötör Pálvölgyi. Topological orderings of weighted directed acyclic graphs. Information Processing Letters, 116(9):564-568, 2016. [arxiv journal]

Dániel Gerbner, Balázs Keszegh, Dömötör Pálvölgyi, Günter Rote and Gábor Wiener. Search for the end of a path in the d-dimensional grid and in other graphs. Ars Mathematica Contemporanea, 12(2): 301-314, 2017. [arxiv journal]

Dömötör Pálvölgyi. Partitioning to three matchings of given size is NP-complete for bipartite graphs. Acta Univ. Sapientiae Informatica, 6(2):206-209, 2014. [egres QP journal .pdf]

János Pach and Dömötör Pálvölgyi. Unsplittable coverings in the plane. Advances in Mathematics, 302: 433-457, 2016. (Conference version in LNCS 9224 (WG 2015): 281-296.) [arxiv journal .pdf]

Balázs Keszegh and Dömötör Pálvölgyi. Convex Polygons are Self-Coverable. Discrete and Computational Geometry, 51(4):885-895, 2014. [arxiv journal .pdf]

Dániel Gerbner, Viola Mészáros, Dömötör Pálvölgyi, Alexey Pokrovskiy and Günter Rote. Advantage in the discrete Voronoi game. Journal of Graph Algorithms and Applications, 18(3):439-457, 2014. (Conference version in 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications.) [arxiv journal .pdf]

Radoslav Fulek, Jan Kynčl, Igor Malinović and Dömötör Pálvölgyi. Clustered Planarity Testing Revisited. In Electronic Journal of Combinatorics, 22(4):1-29, 2015. (Conference version in LNCS 8871 (Graph Drawing 2014): 428-439, 2014.) [arxiv journal .pdf]

Balázs Keszegh, Nathan Lemons and Dömötör Pálvölgyi. Online and quasi-online colorings of wedges and intervals. Order, 33(3): 389-409, 2016. (Conference version in LNCS 7741 (SOFSEM 2013): 292-306, 2013.) [bib arxiv journal conference .pdf]

Péter L. Erdös, Dömötör Pálvölgyi, Claude Tardif and Gábor Tardos. Regular families of forests, antichains and duality pairs of relational structures. Combinatorica, 37(4):651-672, 2017. [arxiv journal .pdf]

Balázs Keszegh and Dömötör Pálvölgyi. Octants are Cover-Decomposable into Many Coverings. Computational Geometry: Theory and Applications, 47(5):585-588, 2014. [arxiv journal .pdf]

János Pach, Dömötör Pálvölgyi, and Géza Tóth. Survey on Decomposition of Multiple Coverings. Geometry--Intuitive, Discrete, and Convex (I. Bárány, K. J. Böröczky, G. Fejes Tóth, J. Pach eds.), Bolyai Society Mathematical Studies 24, 219-257, Springer-Verlag, 2014. [journal .pdf]

Dömötör Pálvölgyi and András Gyárfás. Domination in transitive colorings of tournaments. Journal of Combinatorial Theory, Series B, 107:1-11, 2014. [arxiv journal .pdf]

Dániel Gerbner, Balázs Keszegh, Dömötör Pálvölgyi, and Gábor Wiener. Density-based group testing. Information Theory, Combinatorics, and Search Theory - In Memory of Rudolf Ahlswede, LNCS 7777: 543-556, 2013. [arxiv chapter .pdf]

Dániel Gerbner, Gyula O. H. Katona, Dömötör Pálvölgyi, and Balázs Patkós. Majority and Plurality Problems. Discrete Applied Mathematics, 161(6):813-818, 2013. [bib arxiv journal .pdf]

Dömötör Pálvölgyi. Lower bounds for finding the maximum and minimum elements with k lies. Acta Univ. Sapientiae Informatica., 3(2):224-229, 2011. [bib arxiv journal .pdf]

Dániel Gerbner, Balázs Keszegh, Nathan Lemons, Cory Palmer, Dömötör Pálvölgyi, and Balázs Patkós. Saturating sperner families. Graphs and Combinatorics, 29(5):1355-1364, 2013. (Conference version in 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications.) [bib arxiv journal .pdf]

Dániel Gerbner, Nathan Lemons, Cory Palmer, Dömötör Pálvölgyi, Balázs Patkós, and Vajk Szécsi. Almost cross-intersecting and almost cross-sperner pairs of families of sets. Graphs and Combinatorics, 29(3):489-498, 2013. [bib journal .pdf]

Panagiotis Cheilaris, Balázs Keszegh, and Dömötör Pálvölgyi. Unique-maximum and conflict-free colorings for hypergraphs and tree graphs. SIAM J. Discrete Math.m 27(4):1788-1799, 2013. (Conference version in SOFSEM 2012 and 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications.) [bib arxiv journal conference .pdf]

Balázs Keszegh, János Pach, and Dömötör Pálvölgyi. Drawing Planar Graphs of Bounded Degree with Few Slopes. SIAM J. Discrete Math., 27(2):1171-1183, 2013. (Conference version in LNCS 6502 (Graph Drawing 2010): 293-304, 2010.) [bib arxiv journal .pdf]

Friedrich Eisenbrand, Dömötör Pálvölgyi, and Thomas Rothvoß. Bin packing via discrepancy of permutations. In ACM Transactions on Algorithms (TALG) - SODA 2011, 9(3): 1-15, 2013. [bib arxiv journal .pdf]

András Gyárfás and Dömötör Pálvölgyi. Monochromatic even cycles. Contributions to Discrete Mathematics, 7(1), 2012. [bib journal .pdf]

Padmini Mukkamala, János Pach, and Dömötör Pálvölgyi. Lower bounds on the obstacle number of graphs. Electronic Journal of Combinatorics, 19(2):1-8, 2012. [arxiv journal .pdf]

Padmini Mukkamala and Dömötör Pálvölgyi. Drawing cubic graphs with the four basic slopes. LNCS 7034 (Graph Drawing 2011): 254-265, 2012. [bib arxiv journal .pdf]

Balázs Keszegh and Dömötör Pálvölgyi. Octants are cover decomposable. Discrete and Computational Geometry, 47(3):598-609, 2012. (Conference version in Electronic Notes in Discrete Mathematics 38 (EuroComb 2011), pp. 499-504, 2011.) [bib arxiv journal .pdf]

Zoltán Király, Zoltán Lóránt Nagy, Dömötör Pálvölgyi, and Mirkó Visontai. On weakly intersecting pairs of sets. Fundamenta Informaticae, 117(1):189-198, 2012. [bib journal .pdf]

Kevin Buchin, Jiří Matoušek, Robin Moser, and Dömötör Pálvölgyi. Vectors in a box. Mathematical Programming Ser. A, 135(1-2):323-335, 2012. [bib arxiv journal .pdf]

Padmini Mukkamala and Dömötör Pálvölgyi. Asymptotically optimal pairing strategy for tic-tac-toe with numerous directions. Electronic Journal of Combinatorics, 17(1):1-6, 2010. [bib arxiv journal .pdf]

Tobias Christ, Dömötör Pálvölgyi, and Miloš Stojaković. Consistent digital line segments. Discrete and Computational Geometry, 47(4):691-710, 2012. (Conference version in Electronic Notes in Discrete Mathematics 38 (SoCG '10): 273-278, 2011.) [bib arxiv journal .pdf]

András Gács, Tamás Héger, Zoltán Lóránt Nagy, and Dömötör Pálvölgyi. Permutations, hyperplanes and polynomials over finite fields. Finite Fields and their Applications, 16(5):301-314, 2010. [bib journal .pdf]

Dániel Gerbner, Dömötör Pálvölgyi, Balázs Patkós, and Gábor Wiener. Finding the maximum and minimum elements with one lie. Discrete Applied Mathematics, 158(9):988-995, 2010. [bib journal .pdf]

Friedrich Eisenbrand, Nicolai Hähnle, Dömötör Pálvölgyi, and Gennady Shmonin. Testing additive integrality gaps. Mathematical Programming Ser. A, 141(1-2):257-271, 2013. (Conference version in Proceedings of SODA 2010: 1227-1234, 2010.) [bib journal .pdf]

Dániel Gerbner, Balázs Keszegh, Nathan Lemons, Cory Palmer, Dömötör Pálvölgyi, and Balázs Patkós. Polychromatic colorings of arbitrary rectangular partitions. Discrete Mathematics, 310(1):21-30, 2010. [bib journal .pdf]

Dömötör Pálvölgyi. Indecomposable coverings with concave polygons. Discrete and Computational Geometry, 44(3):577-588, 2010. [bib journal .pdf]

Dömötör Pálvölgyi and Géza Tóth. Convex polygons are cover-decomposable. Discrete and Computational Geometry, 43(3):483-496, 2010. [bib journal .pdf]

Balázs Keszegh, János Pach, Dömötör Pálvölgyi, and Géza Tóth. Cubic graphs have bounded slope parameter. Journal of Graph Algorithms and Applications, 14(1):5-17, 2010. (Conference version in LNCS 5417 (Graph Drawing 2008): 50-60, 2009.) [bib journal .pdf]

Dömötör Pálvölgyi. 2D-TUCKER is PPAD-complete. In 5th International Workshop on Internet and Network Economics (WINE), LNCS 5929:569-574, 2009. [bib conference .pdf]

Dömötör Pálvölgyi. Partitionability to two trees is NP-complete. Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae - Sectio mathematica, 52(1):131-135, 2009. [bib egres arxiv .pdf]

Dömötör Pálvölgyi. Combinatorial necklace splitting. Electronic Journal of Combinatorics, 16(1):1-8, 2009. [bib journal .pdf]

Dömötör Pálvölgyi. Deciding soccer scores and partial orientations of graphs. Acta Univ. Sapientiae Math., 1(1):35-42, 2009. [bib egres journal .pdf]

Balázs Keszegh, János Pach, Dömötör Pálvölgyi, and Géza Tóth. Drawing cubic graphs with at most five slopes. Computational Geometry: Theory and Applications, 40(2):138-147, 2008. (Conference version in LNCS 4372 (Graph Drawing 2006):114-125, 2007.) [bib journal .pdf]

Dömötör Pálvölgyi. Revisiting sequential search using question-sets with bounded intersections. J. Stat. Theory Pract., 1(2):199-204, 2007. [bib journal .pdf] See how this problem generalizes the puzzle about throwing eggs from a building to find out where they start breaking here: [.pdf]

János Pach and Dömötör Pálvölgyi. Bounded-degree graphs can have arbitrarily large slope numbers. Electronic Journal of Combinatorics, 13(1):1-4, 2006. [bib journal .pdf]

Dömötör Pálvölgyi. Baljó S árnyak (english: Left compressed shadows - a simple proof of the Kruskal-Katona theorem). Matematikai Lapok, 10(2):13-16, 2005. [bib .pdf in english.pdf] Later I learned that this proof has been discovered earlier by several people.

Theses and other:

Dömötör Pálvölgyi. Decomposition of Geometric Set Systems and Graphs. PhD thesis, Ecole Polytechnique Fédérale de Lausanne, 2010. [arxiv .html .pdf]

Dömötör Pálvölgyi. Communication complexity. Master's thesis, Eötvös University Budapest, 2005. [arxiv elte.pdf .pdf] Later I was told that Theorem 3.13 already appeared in Yao's seminal paper without proof, still mine seems to be the first proof written down.

Dömötör Pálvölgyi. Érmegráfok. [Érintõ] - Elektronikus Matematikai Lapok, 2023 szeptember.

Nóra Frankl, Tamás Hubai and Dömötör Pálvölgyi. A sík kromatikus száma. [Érintõ] - Elektronikus Matematikai Lapok, 2018 szeptember.

Péter Csikvári, Zoltán Lóránt Nagy, Dömötör Pálvölgyi. Diszkrét matematikai feladatok. Exercises in Discrete Mathematics (in Hungarian), Typotex, 2014, ISBN: e978-963-2792-62-0. [.html]

Emléktábla workshop proceedings, since 2010. [.html]

Dömötör Pálvölgyi. Three halving conjectures in combinatorial search. [.pdf]