---
_id: '17190'
abstract:
- lang: eng
  text: "For a locally finite set, \U0001D434⊆ℝ\U0001D451\r\n, the \U0001D458\r\nth
    Brillouin zone of \U0001D44E∈\U0001D434\r\n is the region of points \U0001D465∈ℝ\U0001D451\r\n
    for which ‖\U0001D465−\U0001D44E‖\r\n is the \U0001D458\r\nth smallest among the
    Euclidean distances between \U0001D465\r\n and the points in \U0001D434\r\n. If
    \U0001D434\r\n is a lattice, the \U0001D458\r\nth Brillouin zones of the points
    in \U0001D434\r\n are translates of each other, and together they tile space.
    Depending on the value of \U0001D458\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."
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.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Alexey
  full_name: Garber, Alexey
  last_name: Garber
- first_name: Mohadese
  full_name: Ghafaris, Mohadese
  last_name: Ghafaris
- first_name: Teresa
  full_name: Heiss, Teresa
  id: 4879BB4E-F248-11E8-B48F-1D18A9856A87
  last_name: Heiss
  orcid: 0000-0002-1780-2689
- first_name: Morteza
  full_name: Saghafiant, Morteza
  last_name: Saghafiant
- first_name: Mathijs
  full_name: Wintraecken, Mathijs
  id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
  last_name: Wintraecken
  orcid: 0000-0002-7472-2220
citation:
  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>
  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>.
  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.
  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.
  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>.
  short: H. Edelsbrunner, A. Garber, M. Ghafaris, T. Heiss, M. Saghafiant, M. Wintraecken,
    SIAM Journal on Discrete Mathematics 38 (2024) 1784–1807.
corr_author: '1'
date_created: 2024-06-30T22:01:05Z
date_published: 2024-06-07T00:00:00Z
date_updated: 2025-09-08T08:06:04Z
day: '07'
department:
- _id: HeEd
doi: 10.1137/22M1489071
ec_funded: 1
external_id:
  arxiv:
  - '2204.01077'
  isi:
  - '001292728600001'
intvolume: '        38'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2204.01077
month: '06'
oa: 1
oa_version: Preprint
page: 1784-1807
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '788183'
  name: Alpha Shape Theory Extended
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
  grant_number: M03073
  name: Learning and triangulating manifolds via collapses
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: I02979-N35
  name: Persistence and stability of geometric complexes
- _id: 268116B8-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z00342
  name: Mathematics, Computer Science
publication: SIAM Journal on Discrete Mathematics
publication_identifier:
  issn:
  - 0895-4801
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Brillouin zones of integer lattices and their perturbations
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 38
year: '2024'
...
---
_id: '11435'
abstract:
- lang: eng
  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}.$'
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."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Grigory
  full_name: Ivanov, Grigory
  id: 87744F66-5C6F-11EA-AFE0-D16B3DDC885E
  last_name: Ivanov
- first_name: Marton
  full_name: Naszodi, Marton
  last_name: Naszodi
citation:
  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>'
  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>'
  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>.'
  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.'
  ista: 'Ivanov G, Naszodi M. 2022. A quantitative Helly-type theorem: Containment
    in a homothet. SIAM Journal on Discrete Mathematics. 36(2), 951–957.'
  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>.'
  short: G. Ivanov, M. Naszodi, SIAM Journal on Discrete Mathematics 36 (2022) 951–957.
date_created: 2022-06-05T22:01:50Z
date_published: 2022-04-11T00:00:00Z
date_updated: 2023-10-18T06:58:03Z
day: '11'
department:
- _id: UlWa
doi: 10.1137/21M1403308
external_id:
  arxiv:
  - '2103.04122'
  isi:
  - '000793158200002'
intvolume: '        36'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: ' https://doi.org/10.48550/arXiv.2103.04122'
month: '04'
oa: 1
oa_version: Preprint
page: 951-957
publication: SIAM Journal on Discrete Mathematics
publication_identifier:
  issn:
  - 0895-4801
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'A quantitative Helly-type theorem: Containment in a homothet'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 36
year: '2022'
...
---
_id: '9468'
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"
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Alan M
  full_name: Arroyo Guevara, Alan M
  id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
  last_name: Arroyo Guevara
  orcid: 0000-0003-2401-8670
- first_name: R. Bruce
  full_name: Richter, R. Bruce
  last_name: Richter
- first_name: Matthew
  full_name: Sunohara, Matthew
  last_name: Sunohara
citation:
  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>.
  short: A.M. Arroyo Guevara, R.B. Richter, M. Sunohara, SIAM Journal on Discrete
    Mathematics 35 (2021) 1050–1076.
date_created: 2021-06-06T22:01:30Z
date_published: 2021-05-20T00:00:00Z
date_updated: 2025-04-14T07:43:46Z
day: '20'
department:
- _id: UlWa
doi: 10.1137/20M1313234
ec_funded: 1
external_id:
  arxiv:
  - '2001.06053'
  isi:
  - '000674142200022'
intvolume: '        35'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2001.06053
month: '05'
oa: 1
oa_version: Preprint
page: 1050-1076
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: SIAM Journal on Discrete Mathematics
publication_identifier:
  issn:
  - 0895-4801
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Extending drawings of complete graphs into arrangements of pseudocircles
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 35
year: '2021'
...
---
_id: '11894'
abstract:
- lang: eng
  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 \U0001D43A=(\U0001D449,\U0001D438)
    and terminal vertices \U0001D43E⊂\U0001D449 with |\U0001D43E|=\U0001D458, a (vertex)
    reachability sparsifier of \U0001D43A is a digraph \U0001D43B=(\U0001D449\U0001D43B,\U0001D438\U0001D43B),
    \U0001D43E⊂\U0001D449\U0001D43B that preserves all reachability information among
    terminal pairs. Let |\U0001D449\U0001D43B| denote the size of \U0001D43B. In this
    work we introduce the notion of reachability-preserving minors (RPMs), i.e., we
    require \U0001D43B to be a minor of \U0001D43A. We show any directed graph \U0001D43A
    admits an RPM \U0001D43B of size \U0001D442(\U0001D4583), and if \U0001D43A is
    planar, then the size of \U0001D43B improves to \U0001D442(\U0001D4582log\U0001D458).
    We complement our upper bound by showing that there exists an infinite family
    of grids such that any RPM must have Ω(\U0001D4582) vertices. (2) Given a weighted
    undirected graph \U0001D43A=(\U0001D449,\U0001D438) and terminal vertices \U0001D43E
    with |\U0001D43E|=\U0001D458, an exact (vertex) cut sparsifier of \U0001D43A is
    a graph \U0001D43B with \U0001D43E⊂\U0001D449\U0001D43B that preserves the value
    of minimum cuts separating any bipartition of \U0001D43E. We show that planar
    graphs with all the \U0001D458 terminals lying on the same face admit exact cut
    sparsifiers of size \U0001D442(\U0001D4582) that are also planar. Our result extends
    to flow and distance sparsifiers. It improves the previous best-known bound of
    \U0001D442(\U0001D458222\U0001D458) for cut and flow sparsifiers by an exponential
    factor and matches an Ω(\U0001D4582) lower-bound for this class of graphs."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Gramoz
  full_name: Goranci, Gramoz
  last_name: Goranci
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Pan
  full_name: Peng, Pan
  last_name: Peng
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>
  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.
  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.
  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>.
  short: G. Goranci, M. Henzinger, P. Peng, SIAM Journal on Discrete Mathematics 34
    (2020) 130–162.
date_created: 2022-08-17T08:50:24Z
date_published: 2020-01-01T00:00:00Z
date_updated: 2024-11-06T11:57:54Z
day: '01'
doi: 10.1137/17m1163153
extern: '1'
external_id:
  arxiv:
  - '1702.01136'
intvolume: '        34'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1702.01136
month: '01'
oa: 1
oa_version: Preprint
page: 130-162
publication: SIAM Journal on Discrete Mathematics
publication_identifier:
  eissn:
  - 1095-7146
  issn:
  - 0895-4801
publication_status: published
publisher: Society for Industrial & Applied Mathematics
quality_controlled: '1'
related_material:
  record:
  - id: '11831'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Improved guarantees for vertex sparsification in planar graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2020'
...
---
_id: '312'
abstract:
- lang: eng
  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.
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).
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Mabel
  full_name: Iglesias Ham, Mabel
  id: 41B58C0C-F248-11E8-B48F-1D18A9856A87
  last_name: Iglesias Ham
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>
  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>.
  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.
  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.
  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>.
  short: H. Edelsbrunner, M. Iglesias Ham, SIAM J Discrete Math 32 (2018) 750–782.
date_created: 2018-12-11T11:45:46Z
date_published: 2018-03-29T00:00:00Z
date_updated: 2026-04-16T09:53:02Z
day: '29'
department:
- _id: HeEd
doi: 10.1137/16M1097201
external_id:
  isi:
  - '000428958900038'
intvolume: '        32'
isi: 1
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://pdfs.semanticscholar.org/d2d5/6da00fbc674e6a8b1bb9d857167e54200dc6.pdf
month: '03'
oa: 1
oa_version: Submitted Version
page: 750 - 782
project:
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: I02979-N35
  name: Persistence and stability of geometric complexes
publication: SIAM J Discrete Math
publication_identifier:
  issn:
  - 0895-4801
publication_status: published
publisher: 'Society for Industrial and Applied Mathematics '
publist_id: '7553'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the optimality of the FCC lattice for soft sphere packing
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 32
year: '2018'
...
---
_id: '9590'
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.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Michael
  full_name: Krivelevich, Michael
  last_name: Krivelevich
- first_name: Matthew Alan
  full_name: Kwan, Matthew Alan
  id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
  last_name: Kwan
  orcid: 0000-0002-4003-7567
- first_name: Benny
  full_name: Sudakov, Benny
  last_name: Sudakov
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>
  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>.
  short: M. Krivelevich, M.A. Kwan, B. Sudakov, SIAM Journal on Discrete Mathematics
    31 (2017) 155–171.
date_created: 2021-06-22T12:26:25Z
date_published: 2017-01-12T00:00:00Z
date_updated: 2023-02-23T14:02:05Z
day: '12'
doi: 10.1137/15m1032910
extern: '1'
external_id:
  arxiv:
  - '1507.07960'
intvolume: '        31'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1507.07960
month: '01'
oa: 1
oa_version: Preprint
page: 155-171
publication: SIAM Journal on Discrete Mathematics
publication_identifier:
  eissn:
  - 1095-7146
  issn:
  - 0895-4801
publication_status: published
publisher: Society for Industrial & Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Bounded-degree spanning trees in randomly perturbed graphs
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 31
year: '2017'
...