[{"department":[{"_id":"UlWa"}],"date_created":"2022-06-05T22:01:50Z","article_type":"original","date_published":"2022-04-11T00:00:00Z","month":"04","language":[{"iso":"eng"}],"publisher":"Society for Industrial and Applied Mathematics","scopus_import":"1","page":"951-957","issue":"2","publication":"SIAM Journal on Discrete Mathematics","type":"journal_article","day":"11","status":"public","intvolume":"        36","main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2103.04122"}],"isi":1,"doi":"10.1137/21M1403308","year":"2022","external_id":{"arxiv":["2103.04122"],"isi":["000793158200002"]},"title":"A quantitative Helly-type theorem: Containment in a homothet","oa":1,"volume":36,"date_updated":"2023-10-18T06:58:03Z","article_processing_charge":"No","arxiv":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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.","oa_version":"Preprint","quality_controlled":"1","_id":"11435","publication_identifier":{"issn":["0895-4801"]},"publication_status":"published","citation":{"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>.","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>","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.","short":"G. Ivanov, M. Naszodi, SIAM Journal on Discrete Mathematics 36 (2022) 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>.","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>"},"author":[{"id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","full_name":"Ivanov, Grigory","last_name":"Ivanov","first_name":"Grigory"},{"full_name":"Naszodi, Marton","last_name":"Naszodi","first_name":"Marton"}],"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"}]},{"date_created":"2022-08-17T08:50:24Z","article_type":"original","date_published":"2020-01-01T00:00:00Z","month":"01","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Society for Industrial & Applied Mathematics","page":"130-162","publication":"SIAM Journal on Discrete Mathematics","issue":"1","type":"journal_article","day":"01","status":"public","intvolume":"        34","main_file_link":[{"url":"https://arxiv.org/abs/1702.01136","open_access":"1"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"11831"}]},"doi":"10.1137/17m1163153","year":"2020","external_id":{"arxiv":["1702.01136"]},"title":"Improved guarantees for vertex sparsification in planar graphs","article_processing_charge":"No","volume":34,"date_updated":"2023-02-21T16:29:44Z","oa":1,"arxiv":1,"quality_controlled":"1","oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["0895-4801"],"eissn":["1095-7146"]},"extern":"1","_id":"11894","citation":{"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>","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.","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>.","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>.","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>","short":"G. Goranci, M.H. Henzinger, P. Peng, SIAM Journal on Discrete Mathematics 34 (2020) 130–162.","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."},"publication_status":"published","author":[{"first_name":"Gramoz","full_name":"Goranci, Gramoz","last_name":"Goranci"},{"full_name":"Henzinger, Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Pan","last_name":"Peng","full_name":"Peng, Pan"}],"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 𝐺=(𝑉,𝐸) 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."}]},{"day":"12","type":"journal_article","intvolume":"        31","status":"public","issue":"1","publication":"SIAM Journal on Discrete Mathematics","page":"155-171","month":"01","date_published":"2017-01-12T00:00:00Z","article_type":"original","publisher":"Society for Industrial & Applied Mathematics","scopus_import":"1","language":[{"iso":"eng"}],"date_created":"2021-06-22T12:26:25Z","publication_status":"published","citation":{"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.","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.","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>.","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>"},"abstract":[{"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.","lang":"eng"}],"author":[{"full_name":"Krivelevich, Michael","last_name":"Krivelevich","first_name":"Michael"},{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567","last_name":"Kwan","full_name":"Kwan, Matthew Alan","first_name":"Matthew Alan"},{"first_name":"Benny","full_name":"Sudakov, Benny","last_name":"Sudakov"}],"arxiv":1,"oa":1,"date_updated":"2023-02-23T14:02:05Z","volume":31,"article_processing_charge":"No","_id":"9590","extern":"1","publication_identifier":{"issn":["0895-4801"],"eissn":["1095-7146"]},"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","quality_controlled":"1","oa_version":"Preprint","doi":"10.1137/15m1032910","year":"2017","external_id":{"arxiv":["1507.07960"]},"title":"Bounded-degree spanning trees in randomly perturbed graphs","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1507.07960"}]}]