---
_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: '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 MH, 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. H., &#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 H 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. H. 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 MH, 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.H. 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: 2023-02-21T16:29:44Z
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: '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'
...