[{"month":"08","date_published":"2017-08-01T00:00:00Z","article_type":"original","publisher":"Elsevier","scopus_import":"1","language":[{"iso":"eng"}],"date_created":"2021-06-21T06:31:10Z","day":"01","type":"journal_article","intvolume":"        61","status":"public","publication":"Electronic Notes in Discrete Mathematics","page":"93-99","doi":"10.1016/j.endm.2017.06.025","year":"2017","title":"Resilience for the Littlewood-Offord problem","external_id":{"arxiv":["1609.08136"]},"main_file_link":[{"url":"https://arxiv.org/abs/1609.08136","open_access":"1"}],"publication_status":"published","citation":{"ama":"Bandeira AS, Ferber A, Kwan MA. Resilience for the Littlewood-Offord problem. <i>Electronic Notes in Discrete Mathematics</i>. 2017;61:93-99. doi:<a href=\"https://doi.org/10.1016/j.endm.2017.06.025\">10.1016/j.endm.2017.06.025</a>","mla":"Bandeira, Afonso S., et al. “Resilience for the Littlewood-Offord Problem.” <i>Electronic Notes in Discrete Mathematics</i>, vol. 61, Elsevier, 2017, pp. 93–99, doi:<a href=\"https://doi.org/10.1016/j.endm.2017.06.025\">10.1016/j.endm.2017.06.025</a>.","ista":"Bandeira AS, Ferber A, Kwan MA. 2017. Resilience for the Littlewood-Offord problem. Electronic Notes in Discrete Mathematics. 61, 93–99.","short":"A.S. Bandeira, A. Ferber, M.A. Kwan, Electronic Notes in Discrete Mathematics 61 (2017) 93–99.","ieee":"A. S. Bandeira, A. Ferber, and M. A. Kwan, “Resilience for the Littlewood-Offord problem,” <i>Electronic Notes in Discrete Mathematics</i>, vol. 61. Elsevier, pp. 93–99, 2017.","apa":"Bandeira, A. S., Ferber, A., &#38; Kwan, M. A. (2017). Resilience for the Littlewood-Offord problem. <i>Electronic Notes in Discrete Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.endm.2017.06.025\">https://doi.org/10.1016/j.endm.2017.06.025</a>","chicago":"Bandeira, Afonso S., Asaf Ferber, and Matthew Alan Kwan. “Resilience for the Littlewood-Offord Problem.” <i>Electronic Notes in Discrete Mathematics</i>. Elsevier, 2017. <a href=\"https://doi.org/10.1016/j.endm.2017.06.025\">https://doi.org/10.1016/j.endm.2017.06.025</a>."},"abstract":[{"lang":"eng","text":"Consider the sum X(ξ)=∑ni=1aiξi, where a=(ai)ni=1 is a sequence of non-zero reals and ξ=(ξi)ni=1 is a sequence of i.i.d. Rademacher random variables (that is, Pr[ξi=1]=Pr[ξi=−1]=1/2). The classical Littlewood-Offord problem asks for the best possible upper bound on the concentration probabilities Pr[X=x]. In this paper we study a resilience version of the Littlewood-Offord problem: how many of the ξi is an adversary typically allowed to change without being able to force concentration on a particular value? We solve this problem asymptotically, and present a few interesting open problems."}],"author":[{"first_name":"Afonso S.","last_name":"Bandeira","full_name":"Bandeira, Afonso S."},{"first_name":"Asaf","full_name":"Ferber, Asaf","last_name":"Ferber"},{"first_name":"Matthew Alan","orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan","last_name":"Kwan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3"}],"arxiv":1,"volume":61,"date_updated":"2023-02-23T14:01:26Z","oa":1,"article_processing_charge":"No","_id":"9574","extern":"1","publication_identifier":{"issn":["1571-0653"]},"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","oa_version":"Preprint","quality_controlled":"1"},{"month":"11","article_type":"original","date_published":"2015-11-01T00:00:00Z","scopus_import":"1","publisher":"Elsevier","language":[{"iso":"eng"}],"date_created":"2021-06-21T06:40:34Z","day":"01","type":"journal_article","intvolume":"        49","status":"public","publication":"Electronic Notes in Discrete Mathematics","page":"181-187","doi":"10.1016/j.endm.2015.06.027","year":"2015","title":"Cycles and matchings in randomly perturbed digraphs and hypergraphs","external_id":{"arxiv":["1501.04816"]},"main_file_link":[{"url":"https://arxiv.org/abs/1501.04816","open_access":"1"}],"citation":{"ista":"Krivelevich M, Kwan MA, Sudakov B. 2015. Cycles and matchings in randomly perturbed digraphs and hypergraphs. Electronic Notes in Discrete Mathematics. 49, 181–187.","short":"M. Krivelevich, M.A. Kwan, B. Sudakov, Electronic Notes in Discrete Mathematics 49 (2015) 181–187.","ama":"Krivelevich M, Kwan MA, Sudakov B. Cycles and matchings in randomly perturbed digraphs and hypergraphs. <i>Electronic Notes in Discrete Mathematics</i>. 2015;49:181-187. doi:<a href=\"https://doi.org/10.1016/j.endm.2015.06.027\">10.1016/j.endm.2015.06.027</a>","mla":"Krivelevich, Michael, et al. “Cycles and Matchings in Randomly Perturbed Digraphs and Hypergraphs.” <i>Electronic Notes in Discrete Mathematics</i>, vol. 49, Elsevier, 2015, pp. 181–87, doi:<a href=\"https://doi.org/10.1016/j.endm.2015.06.027\">10.1016/j.endm.2015.06.027</a>.","chicago":"Krivelevich, Michael, Matthew Alan Kwan, and Benny Sudakov. “Cycles and Matchings in Randomly Perturbed Digraphs and Hypergraphs.” <i>Electronic Notes in Discrete Mathematics</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.endm.2015.06.027\">https://doi.org/10.1016/j.endm.2015.06.027</a>.","apa":"Krivelevich, M., Kwan, M. A., &#38; Sudakov, B. (2015). Cycles and matchings in randomly perturbed digraphs and hypergraphs. <i>Electronic Notes in Discrete Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.endm.2015.06.027\">https://doi.org/10.1016/j.endm.2015.06.027</a>","ieee":"M. Krivelevich, M. A. Kwan, and B. Sudakov, “Cycles and matchings in randomly perturbed digraphs and hypergraphs,” <i>Electronic Notes in Discrete Mathematics</i>, vol. 49. Elsevier, pp. 181–187, 2015."},"publication_status":"published","abstract":[{"text":"We give several results showing that different discrete structures typically gain certain spanning substructures (in particular, Hamilton cycles) after a modest random perturbation. First, we prove that adding linearly many random edges to a dense k-uniform hypergraph ensures the (asymptotically almost sure) existence of a perfect matching or a loose Hamilton cycle. The proof involves an interesting application of Szemerédi's Regularity Lemma, which might be independently useful. We next prove that digraphs with certain strong expansion properties are pancyclic, and use this to show that adding a linear number of random edges typically makes a dense digraph pancyclic. Finally, we prove that perturbing a certain (minimum-degree-dependent) number of random edges in a tournament typically ensures the existence of multiple edge-disjoint Hamilton cycles. All our results are tight.","lang":"eng"}],"author":[{"last_name":"Krivelevich","full_name":"Krivelevich, Michael","first_name":"Michael"},{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","last_name":"Kwan","full_name":"Kwan, Matthew Alan","orcid":"0000-0002-4003-7567","first_name":"Matthew Alan"},{"first_name":"Benny","last_name":"Sudakov","full_name":"Sudakov, Benny"}],"arxiv":1,"article_processing_charge":"No","oa":1,"volume":49,"date_updated":"2023-02-23T14:01:28Z","extern":"1","publication_identifier":{"issn":["1571-0653"]},"_id":"9575","quality_controlled":"1","oa_version":"Preprint","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf"}]