[{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2410.08644"}],"publication_status":"published","citation":{"ama":"Gishboliner L, Milojević A, Sudakov B, Wigderson Y. Canonical Ramsey numbers of sparse graphs. <i>SIAM Journal on Discrete Mathematics</i>. 2025;39(3):1491-1519. doi:<a href=\"https://doi.org/10.1137/24m1714964\">10.1137/24m1714964</a>","short":"L. Gishboliner, A. Milojević, B. Sudakov, Y. Wigderson, SIAM Journal on Discrete Mathematics 39 (2025) 1491–1519.","apa":"Gishboliner, L., Milojević, A., Sudakov, B., &#38; Wigderson, Y. (2025). Canonical Ramsey numbers of sparse graphs. <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial &#38; Applied Mathematics. <a href=\"https://doi.org/10.1137/24m1714964\">https://doi.org/10.1137/24m1714964</a>","chicago":"Gishboliner, Lior, Aleksa Milojević, Benny Sudakov, and Yuval Wigderson. “Canonical Ramsey Numbers of Sparse Graphs.” <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial &#38; Applied Mathematics, 2025. <a href=\"https://doi.org/10.1137/24m1714964\">https://doi.org/10.1137/24m1714964</a>.","ieee":"L. Gishboliner, A. Milojević, B. Sudakov, and Y. Wigderson, “Canonical Ramsey numbers of sparse graphs,” <i>SIAM Journal on Discrete Mathematics</i>, vol. 39, no. 3. Society for Industrial &#38; Applied Mathematics, pp. 1491–1519, 2025.","mla":"Gishboliner, Lior, et al. “Canonical Ramsey Numbers of Sparse Graphs.” <i>SIAM Journal on Discrete Mathematics</i>, vol. 39, no. 3, Society for Industrial &#38; Applied Mathematics, 2025, pp. 1491–519, doi:<a href=\"https://doi.org/10.1137/24m1714964\">10.1137/24m1714964</a>.","ista":"Gishboliner L, Milojević A, Sudakov B, Wigderson Y. 2025. Canonical Ramsey numbers of sparse graphs. SIAM Journal on Discrete Mathematics. 39(3), 1491–1519."},"status":"public","oa":1,"date_published":"2025-09-01T00:00:00Z","OA_place":"repository","intvolume":"        39","author":[{"full_name":"Gishboliner, Lior","last_name":"Gishboliner","first_name":"Lior"},{"last_name":"Milojević","full_name":"Milojević, Aleksa","first_name":"Aleksa"},{"last_name":"Sudakov","full_name":"Sudakov, Benny","first_name":"Benny"},{"first_name":"Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","last_name":"Wigderson","full_name":"Wigderson, Yuval"}],"mathsc":["05D10"],"publisher":"Society for Industrial & Applied Mathematics","date_created":"2026-06-29T10:49:48Z","doi":"10.1137/24m1714964","OA_type":"green","scopus_import":"1","_id":"22155","abstract":[{"lang":"eng","text":"The canonical Ramsey theorem of Erdős and Rado implies that for any graph 𝐻, any edge-coloring (with an arbitrary number of colors) of a sufficiently large complete graph 𝐾𝑁 contains a monochromatic, lexicographic, or rainbow copy of 𝐻. The least such 𝑁 is called the Erdős–Rado number of 𝐻, denoted by 𝐸⁢𝑅⁡(𝐻). Erdős–Rado numbers of cliques have received considerable attention, and in this paper we extend this line of research by studying Erdős–Rado numbers of sparse graphs. For example, we prove that if 𝐻 has bounded degree, then 𝐸⁢𝑅⁡(𝐻) is polynomial in |𝑉⁡(𝐻)| if 𝐻 is bipartite but exponential in general. We also study the closely related problem of constrained Ramsey numbers. For a given tree S and given path 𝑃𝑡, we study the minimum 𝑁 such that every edge-coloring of 𝐾𝑁 contains a monochromatic copy of S or a rainbow copy of 𝑃𝑡. We prove a nearly optimal upper bound for this problem, which differs from the best known lower bound by a function of inverse Ackermann type."}],"year":"2025","page":"1491-1519","extern":"1","article_processing_charge":"No","day":"01","volume":39,"month":"09","publication":"SIAM Journal on Discrete Mathematics","language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1095-7146"],"issn":["0895-4801"]},"oa_version":"Preprint","quality_controlled":"1","date_updated":"2026-07-08T07:38:44Z","article_type":"original","arxiv":1,"external_id":{"arxiv":["2410.08644"]},"title":"Canonical Ramsey numbers of sparse graphs","type":"journal_article","issue":"3"},{"acknowledgement":"The second author is partially supported by the Alexander von Humboldt Foundation. The sixth author is supported by the European Union's Horizon 2020 research and innovation programme under Marie Sklodowska-Curie grant agreement 754411, and by Austrian Science Fund(FWF) grant M-3073. All other authors are supported by European Research Council (ERC) grant 788183, by the Wittgenstein Prize, by Austrian Science Fund (FWF) grant Z 342-N31, and by the DFG Collaborative Research Center TRR 109, Austrian Science Fund (FWF) grant I 02979-N35.","_id":"17190","scopus_import":"1","page":"1784-1807","year":"2024","abstract":[{"lang":"eng","text":"For a locally finite set, 𝐴⊆ℝ𝑑\r\n, the 𝑘\r\nth Brillouin zone of 𝑎∈𝐴\r\n is the region of points 𝑥∈ℝ𝑑\r\n for which ‖𝑥−𝑎‖\r\n is the 𝑘\r\nth smallest among the Euclidean distances between 𝑥\r\n and the points in 𝐴\r\n. If 𝐴\r\n is a lattice, the 𝑘\r\nth Brillouin zones of the points in 𝐴\r\n are translates of each other, and together they tile space. Depending on the value of 𝑘\r\n, they express medium- or long-range order in the set. We study fundamental geometric and combinatorial properties of Brillouin zones, focusing on the integer lattice and its perturbations. Our results include the stability of a Brillouin zone under perturbations, a linear upper bound on the number of chambers in a zone for lattices in ℝ2\r\n, and the convergence of the maximum volume of a chamber to zero for the integer lattice."}],"day":"07","article_processing_charge":"No","oa":1,"status":"public","publication_status":"published","citation":{"short":"H. Edelsbrunner, A. Garber, M. Ghafaris, T. Heiss, M. Saghafiant, M. Wintraecken, SIAM Journal on Discrete Mathematics 38 (2024) 1784–1807.","ama":"Edelsbrunner H, Garber A, Ghafaris M, Heiss T, Saghafiant M, Wintraecken M. Brillouin zones of integer lattices and their perturbations. <i>SIAM Journal on Discrete Mathematics</i>. 2024;38(2):1784-1807. doi:<a href=\"https://doi.org/10.1137/22M1489071\">10.1137/22M1489071</a>","apa":"Edelsbrunner, H., Garber, A., Ghafaris, M., Heiss, T., Saghafiant, M., &#38; Wintraecken, M. (2024). Brillouin zones of integer lattices and their perturbations. <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/22M1489071\">https://doi.org/10.1137/22M1489071</a>","ieee":"H. Edelsbrunner, A. Garber, M. Ghafaris, T. Heiss, M. Saghafiant, and M. Wintraecken, “Brillouin zones of integer lattices and their perturbations,” <i>SIAM Journal on Discrete Mathematics</i>, vol. 38, no. 2. Society for Industrial and Applied Mathematics, pp. 1784–1807, 2024.","chicago":"Edelsbrunner, Herbert, Alexey Garber, Mohadese Ghafaris, Teresa Heiss, Morteza Saghafiant, and Mathijs Wintraecken. “Brillouin Zones of Integer Lattices and Their Perturbations.” <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial and Applied Mathematics, 2024. <a href=\"https://doi.org/10.1137/22M1489071\">https://doi.org/10.1137/22M1489071</a>.","mla":"Edelsbrunner, Herbert, et al. “Brillouin Zones of Integer Lattices and Their Perturbations.” <i>SIAM Journal on Discrete Mathematics</i>, vol. 38, no. 2, Society for Industrial and Applied Mathematics, 2024, pp. 1784–807, doi:<a href=\"https://doi.org/10.1137/22M1489071\">10.1137/22M1489071</a>.","ista":"Edelsbrunner H, Garber A, Ghafaris M, Heiss T, Saghafiant M, Wintraecken M. 2024. Brillouin zones of integer lattices and their perturbations. SIAM Journal on Discrete Mathematics. 38(2), 1784–1807."},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2204.01077"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_published":"2024-06-07T00:00:00Z","corr_author":"1","date_created":"2024-06-30T22:01:05Z","doi":"10.1137/22M1489071","publisher":"Society for Industrial and Applied Mathematics","author":[{"full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Garber, Alexey","last_name":"Garber","first_name":"Alexey"},{"last_name":"Ghafaris","full_name":"Ghafaris, Mohadese","first_name":"Mohadese"},{"full_name":"Heiss, Teresa","last_name":"Heiss","orcid":"0000-0002-1780-2689","first_name":"Teresa","id":"4879BB4E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Morteza","last_name":"Saghafiant","full_name":"Saghafiant, Morteza"},{"full_name":"Wintraecken, Mathijs","last_name":"Wintraecken","orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","first_name":"Mathijs"}],"intvolume":"        38","quality_controlled":"1","department":[{"_id":"HeEd"}],"project":[{"call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships"},{"grant_number":"788183","call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","name":"Alpha Shape Theory Extended"},{"_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","name":"Learning and triangulating manifolds via collapses","grant_number":"M03073"},{"name":"Persistence and stability of geometric complexes","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","grant_number":"I02979-N35","call_identifier":"FWF"},{"_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"Mathematics, Computer Science","grant_number":"Z00342","call_identifier":"FWF"}],"article_type":"original","date_updated":"2025-09-08T08:06:04Z","ec_funded":1,"title":"Brillouin zones of integer lattices and their perturbations","arxiv":1,"external_id":{"isi":["001292728600001"],"arxiv":["2204.01077"]},"issue":"2","type":"journal_article","publication":"SIAM Journal on Discrete Mathematics","month":"06","isi":1,"volume":38,"language":[{"iso":"eng"}],"publication_identifier":{"issn":["0895-4801"]},"oa_version":"Preprint"},{"article_processing_charge":"No","day":"11","page":"951-957","year":"2022","abstract":[{"text":"We introduce a new variant of quantitative Helly-type theorems: the minimal homothetic distance of the intersection of a family of convex sets to the intersection of a subfamily of a fixed size. As an application, we establish the following quantitative Helly-type result for the diameter. If $K$ is the intersection of finitely many convex bodies in $\\mathbb{R}^d$, then one can select $2d$ of these bodies whose intersection is of diameter at most $(2d)^3{diam}(K)$. The best previously known estimate, due to Brazitikos [Bull. Hellenic Math. Soc., 62 (2018), pp. 19--25], is $c d^{11/2}$. Moreover, we confirm that the multiplicative factor $c d^{1/2}$ conjectured by Bárány, Katchalski, and Pach [Proc. Amer. Math. Soc., 86 (1982), pp. 109--114] cannot be improved. The bounds above follow from our key result that concerns sparse approximation of a convex polytope by the convex hull of a well-chosen subset of its vertices: Assume that $Q \\subset {\\mathbb R}^d$ is a polytope whose centroid is the origin. Then there exist at most 2d vertices of $Q$ whose convex hull $Q^{\\prime \\prime}$ satisfies $Q \\subset - 8d^3 Q^{\\prime \\prime}.$","lang":"eng"}],"acknowledgement":"G.I. acknowledges the financial support from the Ministry of Educational and Science of the Russian Federation in the framework of MegaGrant no 075-15-2019-1926. M.N. was supported by the National Research, Development and Innovation Fund (NRDI) grants K119670 and\r\nKKP-133864 as well as the Bolyai Scholarship of the Hungarian Academy of Sciences and the New National Excellence Programme and the TKP2020-NKA-06 program provided by the NRDI.","_id":"11435","scopus_import":"1","doi":"10.1137/21M1403308","date_created":"2022-06-05T22:01:50Z","publisher":"Society for Industrial and Applied Mathematics","author":[{"first_name":"Grigory","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","full_name":"Ivanov, Grigory","last_name":"Ivanov"},{"first_name":"Marton","full_name":"Naszodi, Marton","last_name":"Naszodi"}],"intvolume":"        36","date_published":"2022-04-11T00:00:00Z","status":"public","oa":1,"citation":{"apa":"Ivanov, G., &#38; Naszodi, M. (2022). A quantitative Helly-type theorem: Containment in a homothet. <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/21M1403308\">https://doi.org/10.1137/21M1403308</a>","short":"G. Ivanov, M. Naszodi, SIAM Journal on Discrete Mathematics 36 (2022) 951–957.","ama":"Ivanov G, Naszodi M. A quantitative Helly-type theorem: Containment in a homothet. <i>SIAM Journal on Discrete Mathematics</i>. 2022;36(2):951-957. doi:<a href=\"https://doi.org/10.1137/21M1403308\">10.1137/21M1403308</a>","mla":"Ivanov, Grigory, and Marton Naszodi. “A Quantitative Helly-Type Theorem: Containment in a Homothet.” <i>SIAM Journal on Discrete Mathematics</i>, vol. 36, no. 2, Society for Industrial and Applied Mathematics, 2022, pp. 951–57, doi:<a href=\"https://doi.org/10.1137/21M1403308\">10.1137/21M1403308</a>.","ista":"Ivanov G, Naszodi M. 2022. A quantitative Helly-type theorem: Containment in a homothet. SIAM Journal on Discrete Mathematics. 36(2), 951–957.","ieee":"G. Ivanov and M. Naszodi, “A quantitative Helly-type theorem: Containment in a homothet,” <i>SIAM Journal on Discrete Mathematics</i>, vol. 36, no. 2. Society for Industrial and Applied Mathematics, pp. 951–957, 2022.","chicago":"Ivanov, Grigory, and Marton Naszodi. “A Quantitative Helly-Type Theorem: Containment in a Homothet.” <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial and Applied Mathematics, 2022. <a href=\"https://doi.org/10.1137/21M1403308\">https://doi.org/10.1137/21M1403308</a>."},"publication_status":"published","main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2103.04122"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"2","type":"journal_article","title":"A quantitative Helly-type theorem: Containment in a homothet","arxiv":1,"external_id":{"arxiv":["2103.04122"],"isi":["000793158200002"]},"article_type":"original","date_updated":"2023-10-18T06:58:03Z","department":[{"_id":"UlWa"}],"quality_controlled":"1","oa_version":"Preprint","publication_identifier":{"issn":["0895-4801"]},"language":[{"iso":"eng"}],"publication":"SIAM Journal on Discrete Mathematics","isi":1,"month":"04","volume":36},{"oa_version":"Preprint","publication_identifier":{"issn":["0895-4801"]},"isi":1,"month":"05","publication":"SIAM Journal on Discrete Mathematics","volume":35,"language":[{"iso":"eng"}],"ec_funded":1,"external_id":{"isi":["000674142200022"],"arxiv":["2001.06053"]},"arxiv":1,"title":"Extending drawings of complete graphs into arrangements of pseudocircles","issue":"2","type":"journal_article","quality_controlled":"1","department":[{"_id":"UlWa"}],"article_type":"original","project":[{"name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411"}],"date_updated":"2025-04-14T07:43:46Z","doi":"10.1137/20M1313234","date_created":"2021-06-06T22:01:30Z","publisher":"Society for Industrial and Applied Mathematics","author":[{"first_name":"Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","last_name":"Arroyo Guevara","orcid":"0000-0003-2401-8670","full_name":"Arroyo Guevara, Alan M"},{"first_name":"R. Bruce","full_name":"Richter, R. Bruce","last_name":"Richter"},{"first_name":"Matthew","full_name":"Sunohara, Matthew","last_name":"Sunohara"}],"intvolume":"        35","status":"public","oa":1,"publication_status":"published","citation":{"short":"A.M. Arroyo Guevara, R.B. Richter, M. Sunohara, SIAM Journal on Discrete Mathematics 35 (2021) 1050–1076.","ama":"Arroyo Guevara AM, Richter RB, Sunohara M. Extending drawings of complete graphs into arrangements of pseudocircles. <i>SIAM Journal on Discrete Mathematics</i>. 2021;35(2):1050-1076. doi:<a href=\"https://doi.org/10.1137/20M1313234\">10.1137/20M1313234</a>","apa":"Arroyo Guevara, A. M., Richter, R. B., &#38; Sunohara, M. (2021). Extending drawings of complete graphs into arrangements of pseudocircles. <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/20M1313234\">https://doi.org/10.1137/20M1313234</a>","chicago":"Arroyo Guevara, Alan M, R. Bruce Richter, and Matthew Sunohara. “Extending Drawings of Complete Graphs into Arrangements of Pseudocircles.” <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial and Applied Mathematics, 2021. <a href=\"https://doi.org/10.1137/20M1313234\">https://doi.org/10.1137/20M1313234</a>.","ieee":"A. M. Arroyo Guevara, R. B. Richter, and M. Sunohara, “Extending drawings of complete graphs into arrangements of pseudocircles,” <i>SIAM Journal on Discrete Mathematics</i>, vol. 35, no. 2. Society for Industrial and Applied Mathematics, pp. 1050–1076, 2021.","ista":"Arroyo Guevara AM, Richter RB, Sunohara M. 2021. Extending drawings of complete graphs into arrangements of pseudocircles. SIAM Journal on Discrete Mathematics. 35(2), 1050–1076.","mla":"Arroyo Guevara, Alan M., et al. “Extending Drawings of Complete Graphs into Arrangements of Pseudocircles.” <i>SIAM Journal on Discrete Mathematics</i>, vol. 35, no. 2, Society for Industrial and Applied Mathematics, 2021, pp. 1050–76, doi:<a href=\"https://doi.org/10.1137/20M1313234\">10.1137/20M1313234</a>."},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2001.06053"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2021-05-20T00:00:00Z","day":"20","article_processing_charge":"No","_id":"9468","scopus_import":"1","page":"1050-1076","year":"2021","abstract":[{"lang":"eng","text":"Motivated by the successful application of geometry to proving the Harary--Hill conjecture for “pseudolinear” drawings of $K_n$, we introduce “pseudospherical” drawings of graphs. A spherical drawing of a graph $G$ is a drawing in the unit sphere $\\mathbb{S}^2$ in which the vertices of $G$ are represented as points---no three on a great circle---and the edges of $G$ are shortest-arcs in $\\mathbb{S}^2$ connecting pairs of vertices. Such a drawing has three properties: (1) every edge $e$ is contained in a simple closed curve $\\gamma_e$ such that the only vertices in $\\gamma_e$ are the ends of $e$; (2) if $e\\ne f$, then $\\gamma_e\\cap\\gamma_f$ has precisely two crossings; and (3) if $e\\ne f$, then $e$ intersects $\\gamma_f$ at most once, in either a crossing or an end of $e$. We use properties (1)--(3) to define a pseudospherical drawing of $G$. Our main result is that for the complete graph, properties (1)--(3) are equivalent to the same three properties but with “precisely two crossings” in (2) replaced by “at most two crossings.” The proof requires a result in the geometric transversal theory of arrangements of pseudocircles. This is proved using the surprising result that the absence of special arcs (coherent spirals) in an arrangement of simple closed curves characterizes the fact that any two curves in the arrangement have at most two crossings. Our studies provide the necessary ideas for exhibiting a drawing of $K_{10}$ that has no extension to an arrangement of pseudocircles and a drawing of $K_9$ that does extend to an arrangement of pseudocircles, but no such extension has all pairs of pseudocircles crossing twice.\r\n"}]},{"type":"journal_article","issue":"1","arxiv":1,"external_id":{"arxiv":["1702.01136"]},"title":"Improved guarantees for vertex sparsification in planar graphs","article_type":"original","date_updated":"2024-11-06T11:57:54Z","quality_controlled":"1","oa_version":"Preprint","publication_identifier":{"eissn":["1095-7146"],"issn":["0895-4801"]},"related_material":{"record":[{"relation":"earlier_version","id":"11831","status":"public"}]},"language":[{"iso":"eng"}],"volume":34,"month":"01","publication":"SIAM Journal on Discrete Mathematics","article_processing_charge":"No","day":"01","year":"2020","abstract":[{"text":"Graph sparsification aims at compressing large graphs into smaller ones while preserving important characteristics of the input graph. In this work we study vertex sparsifiers, i.e., sparsifiers whose goal is to reduce the number of vertices. We focus on the following notions: (1) Given a digraph 𝐺=(𝑉,𝐸) and terminal vertices 𝐾⊂𝑉 with |𝐾|=𝑘, a (vertex) reachability sparsifier of 𝐺 is a digraph 𝐻=(𝑉𝐻,𝐸𝐻), 𝐾⊂𝑉𝐻 that preserves all reachability information among terminal pairs. Let |𝑉𝐻| denote the size of 𝐻. In this work we introduce the notion of reachability-preserving minors (RPMs), i.e., we require 𝐻 to be a minor of 𝐺. We show any directed graph 𝐺 admits an RPM 𝐻 of size 𝑂(𝑘3), and if 𝐺 is planar, then the size of 𝐻 improves to 𝑂(𝑘2log𝑘). We complement our upper bound by showing that there exists an infinite family of grids such that any RPM must have Ω(𝑘2) vertices. (2) Given a weighted undirected graph 𝐺=(𝑉,𝐸) and terminal vertices 𝐾 with |𝐾|=𝑘, an exact (vertex) cut sparsifier of 𝐺 is a graph 𝐻 with 𝐾⊂𝑉𝐻 that preserves the value of minimum cuts separating any bipartition of 𝐾. We show that planar graphs with all the 𝑘 terminals lying on the same face admit exact cut sparsifiers of size 𝑂(𝑘2) that are also planar. Our result extends to flow and distance sparsifiers. It improves the previous best-known bound of 𝑂(𝑘222𝑘) for cut and flow sparsifiers by an exponential factor and matches an Ω(𝑘2) lower-bound for this class of graphs.","lang":"eng"}],"page":"130-162","extern":"1","_id":"11894","scopus_import":"1","author":[{"last_name":"Goranci","full_name":"Goranci, Gramoz","first_name":"Gramoz"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","full_name":"Henzinger, Monika H"},{"first_name":"Pan","full_name":"Peng, Pan","last_name":"Peng"}],"intvolume":"        34","doi":"10.1137/17m1163153","date_created":"2022-08-17T08:50:24Z","publisher":"Society for Industrial & Applied Mathematics","date_published":"2020-01-01T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/1702.01136","open_access":"1"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"status":"public","publication_status":"published","citation":{"ama":"Goranci G, Henzinger M, Peng P. Improved guarantees for vertex sparsification in planar graphs. <i>SIAM Journal on Discrete Mathematics</i>. 2020;34(1):130-162. doi:<a href=\"https://doi.org/10.1137/17m1163153\">10.1137/17m1163153</a>","apa":"Goranci, G., Henzinger, M., &#38; Peng, P. (2020). Improved guarantees for vertex sparsification in planar graphs. <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial &#38; Applied Mathematics. <a href=\"https://doi.org/10.1137/17m1163153\">https://doi.org/10.1137/17m1163153</a>","short":"G. Goranci, M. Henzinger, P. Peng, SIAM Journal on Discrete Mathematics 34 (2020) 130–162.","chicago":"Goranci, Gramoz, Monika Henzinger, and Pan Peng. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial &#38; Applied Mathematics, 2020. <a href=\"https://doi.org/10.1137/17m1163153\">https://doi.org/10.1137/17m1163153</a>.","ieee":"G. Goranci, M. Henzinger, and P. Peng, “Improved guarantees for vertex sparsification in planar graphs,” <i>SIAM Journal on Discrete Mathematics</i>, vol. 34, no. 1. Society for Industrial &#38; Applied Mathematics, pp. 130–162, 2020.","mla":"Goranci, Gramoz, et al. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” <i>SIAM Journal on Discrete Mathematics</i>, vol. 34, no. 1, Society for Industrial &#38; Applied Mathematics, 2020, pp. 130–62, doi:<a href=\"https://doi.org/10.1137/17m1163153\">10.1137/17m1163153</a>.","ista":"Goranci G, Henzinger M, Peng P. 2020. Improved guarantees for vertex sparsification in planar graphs. SIAM Journal on Discrete Mathematics. 34(1), 130–162."}},{"title":"On the optimality of the FCC lattice for soft sphere packing","external_id":{"isi":["000428958900038"]},"type":"journal_article","issue":"1","department":[{"_id":"HeEd"}],"quality_controlled":"1","date_updated":"2026-07-06T14:00:50Z","project":[{"name":"Persistence and stability of geometric complexes","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","grant_number":"I02979-N35","call_identifier":"FWF"}],"article_type":"original","oa_version":"Submitted Version","publication_identifier":{"issn":["0895-4801"]},"volume":32,"isi":1,"publication":"SIAM J Discrete Math","month":"03","language":[{"iso":"eng"}],"article_processing_charge":"No","day":"29","scopus_import":"1","_id":"312","acknowledgement":"This work was partially supported by the DFG Collaborative Research Center TRR 109, “Discretization in Geometry and Dynamics,” through grant I02979-N35 of the Austrian Science Fund (FWF).","abstract":[{"text":"Motivated by biological questions, we study configurations of equal spheres that neither pack nor cover. Placing their centers on a lattice, we define the soft density of the configuration by penalizing multiple overlaps. Considering the 1-parameter family of diagonally distorted 3-dimensional integer lattices, we show that the soft density is maximized at the FCC lattice.","lang":"eng"}],"year":"2018","page":"750 - 782","intvolume":"        32","author":[{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert"},{"last_name":"Iglesias Ham","full_name":"Iglesias Ham, Mabel","id":"41B58C0C-F248-11E8-B48F-1D18A9856A87","first_name":"Mabel"}],"das_tickbox":"1","publisher":"Society for Industrial and Applied Mathematics","date_created":"2018-12-11T11:45:46Z","doi":"10.1137/16M1097201","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"http://pdfs.semanticscholar.org/d2d5/6da00fbc674e6a8b1bb9d857167e54200dc6.pdf"}],"citation":{"ama":"Edelsbrunner H, Iglesias Ham M. On the optimality of the FCC lattice for soft sphere packing. <i>SIAM J Discrete Math</i>. 2018;32(1):750-782. doi:<a href=\"https://doi.org/10.1137/16M1097201\">10.1137/16M1097201</a>","apa":"Edelsbrunner, H., &#38; Iglesias Ham, M. (2018). On the optimality of the FCC lattice for soft sphere packing. <i>SIAM J Discrete Math</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/16M1097201\">https://doi.org/10.1137/16M1097201</a>","short":"H. Edelsbrunner, M. Iglesias Ham, SIAM J Discrete Math 32 (2018) 750–782.","ieee":"H. Edelsbrunner and M. Iglesias Ham, “On the optimality of the FCC lattice for soft sphere packing,” <i>SIAM J Discrete Math</i>, vol. 32, no. 1. Society for Industrial and Applied Mathematics, pp. 750–782, 2018.","chicago":"Edelsbrunner, Herbert, and Mabel Iglesias Ham. “On the Optimality of the FCC Lattice for Soft Sphere Packing.” <i>SIAM J Discrete Math</i>. Society for Industrial and Applied Mathematics, 2018. <a href=\"https://doi.org/10.1137/16M1097201\">https://doi.org/10.1137/16M1097201</a>.","mla":"Edelsbrunner, Herbert, and Mabel Iglesias Ham. “On the Optimality of the FCC Lattice for Soft Sphere Packing.” <i>SIAM J Discrete Math</i>, vol. 32, no. 1, Society for Industrial and Applied Mathematics, 2018, pp. 750–82, doi:<a href=\"https://doi.org/10.1137/16M1097201\">10.1137/16M1097201</a>.","ista":"Edelsbrunner H, Iglesias Ham M. 2018. On the optimality of the FCC lattice for soft sphere packing. SIAM J Discrete Math. 32(1), 750–782."},"publication_status":"published","oa":1,"status":"public","publist_id":"7553","date_published":"2018-03-29T00:00:00Z"},{"date_created":"2021-06-22T12:26:25Z","doi":"10.1137/15m1032910","publisher":"Society for Industrial & Applied Mathematics","author":[{"first_name":"Michael","full_name":"Krivelevich, Michael","last_name":"Krivelevich"},{"orcid":"0000-0002-4003-7567","last_name":"Kwan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","first_name":"Matthew Alan"},{"first_name":"Benny","last_name":"Sudakov","full_name":"Sudakov, Benny"}],"intvolume":"        31","oa":1,"status":"public","citation":{"ama":"Krivelevich M, Kwan MA, Sudakov B. Bounded-degree spanning trees in randomly perturbed graphs. <i>SIAM Journal on Discrete Mathematics</i>. 2017;31(1):155-171. doi:<a href=\"https://doi.org/10.1137/15m1032910\">10.1137/15m1032910</a>","apa":"Krivelevich, M., Kwan, M. A., &#38; Sudakov, B. (2017). Bounded-degree spanning trees in randomly perturbed graphs. <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial &#38; Applied Mathematics. <a href=\"https://doi.org/10.1137/15m1032910\">https://doi.org/10.1137/15m1032910</a>","short":"M. Krivelevich, M.A. Kwan, B. Sudakov, SIAM Journal on Discrete Mathematics 31 (2017) 155–171.","chicago":"Krivelevich, Michael, Matthew Alan Kwan, and Benny Sudakov. “Bounded-Degree Spanning Trees in Randomly Perturbed Graphs.” <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial &#38; Applied Mathematics, 2017. <a href=\"https://doi.org/10.1137/15m1032910\">https://doi.org/10.1137/15m1032910</a>.","ieee":"M. Krivelevich, M. A. Kwan, and B. Sudakov, “Bounded-degree spanning trees in randomly perturbed graphs,” <i>SIAM Journal on Discrete Mathematics</i>, vol. 31, no. 1. Society for Industrial &#38; Applied Mathematics, pp. 155–171, 2017.","ista":"Krivelevich M, Kwan MA, Sudakov B. 2017. Bounded-degree spanning trees in randomly perturbed graphs. SIAM Journal on Discrete Mathematics. 31(1), 155–171.","mla":"Krivelevich, Michael, et al. “Bounded-Degree Spanning Trees in Randomly Perturbed Graphs.” <i>SIAM Journal on Discrete Mathematics</i>, vol. 31, no. 1, Society for Industrial &#38; Applied Mathematics, 2017, pp. 155–71, doi:<a href=\"https://doi.org/10.1137/15m1032910\">10.1137/15m1032910</a>."},"publication_status":"published","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1507.07960"}],"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","date_published":"2017-01-12T00:00:00Z","article_processing_charge":"No","day":"12","_id":"9590","scopus_import":"1","page":"155-171","extern":"1","year":"2017","abstract":[{"lang":"eng","text":"We show that for any fixed dense graph G and bounded-degree tree T on the same number of vertices, a modest random perturbation of G will typically contain a copy of T . This combines the viewpoints of the well-studied problems of embedding trees into fixed dense graphs and into random graphs, and extends a sizeable body of existing research on randomly perturbed graphs. Specifically, we show that there is c=c(α,Δ) such that if G is an n-vertex graph with minimum degree at least αn, and T is an n-vertex tree with maximum degree at most Δ , then if we add cn uniformly random edges to G, the resulting graph will contain T asymptotically almost surely (as n→∞ ). Our proof uses a lemma concerning the decomposition of a dense graph into super-regular pairs of comparable sizes, which may be of independent interest."}],"oa_version":"Preprint","publication_identifier":{"issn":["0895-4801"],"eissn":["1095-7146"]},"month":"01","publication":"SIAM Journal on Discrete Mathematics","volume":31,"language":[{"iso":"eng"}],"arxiv":1,"title":"Bounded-degree spanning trees in randomly perturbed graphs","external_id":{"arxiv":["1507.07960"]},"issue":"1","type":"journal_article","quality_controlled":"1","article_type":"original","date_updated":"2023-02-23T14:02:05Z"}]