---
_id: '9574'
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.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Afonso S.
  full_name: Bandeira, Afonso S.
  last_name: Bandeira
- first_name: Asaf
  full_name: Ferber, Asaf
  last_name: Ferber
- first_name: Matthew Alan
  full_name: Kwan, Matthew Alan
  id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
  last_name: Kwan
  orcid: 0000-0002-4003-7567
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>
  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>.
  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.
  ista: Bandeira AS, Ferber A, Kwan MA. 2017. Resilience for the Littlewood-Offord
    problem. Electronic Notes in Discrete Mathematics. 61, 93–99.
  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>.
  short: A.S. Bandeira, A. Ferber, M.A. Kwan, Electronic Notes in Discrete Mathematics
    61 (2017) 93–99.
date_created: 2021-06-21T06:31:10Z
date_published: 2017-08-01T00:00:00Z
date_updated: 2023-02-23T14:01:26Z
day: '01'
doi: 10.1016/j.endm.2017.06.025
extern: '1'
external_id:
  arxiv:
  - '1609.08136'
intvolume: '        61'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1609.08136
month: '08'
oa: 1
oa_version: Preprint
page: 93-99
publication: Electronic Notes in Discrete Mathematics
publication_identifier:
  issn:
  - 1571-0653
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Resilience for the Littlewood-Offord problem
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 61
year: '2017'
...
---
_id: '9575'
abstract:
- lang: eng
  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.
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. 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>
  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>
  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>.
  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.
  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.
  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>.
  short: M. Krivelevich, M.A. Kwan, B. Sudakov, Electronic Notes in Discrete Mathematics
    49 (2015) 181–187.
date_created: 2021-06-21T06:40:34Z
date_published: 2015-11-01T00:00:00Z
date_updated: 2023-02-23T14:01:28Z
day: '01'
doi: 10.1016/j.endm.2015.06.027
extern: '1'
external_id:
  arxiv:
  - '1501.04816'
intvolume: '        49'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1501.04816
month: '11'
oa: 1
oa_version: Preprint
page: 181-187
publication: Electronic Notes in Discrete Mathematics
publication_identifier:
  issn:
  - 1571-0653
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Cycles and matchings in randomly perturbed digraphs and hypergraphs
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 49
year: '2015'
...