---
OA_place: repository
OA_type: green
_id: '22168'
abstract:
- lang: eng
  text: "Let us say that a graph G is Ramsey for a tuple (H1, ... , Hr) of graphs
    if every r-colouring\r\nof the edges of G contains a monochromatic copy of Hi
    in colour i, for some i ∈ [[r]].\r\nA famous conjecture of Kohayakawa and Kreuter,
    extending seminal work of Rödl and\r\nRucinski, predicts the threshold at which
    the binomial random graph ´ Gn,p becomes Ramsey\r\nfor (H1, ... , Hr) asymptotically
    almost surely.\r\nIn this paper, we resolve the Kohayakawa–Kreuter conjecture
    for almost all tuples of\r\ngraphs. Moreover, we reduce its validity to the truth
    of a certain deterministic statement,\r\nwhich is a clear necessary condition
    for the conjecture to hold. All of our results actually hold in greater generality,
    when one replaces the graphs H1, ... , Hr by finite families\r\nH1, ... , Hr.
    Additionally, we pose a natural (deterministic) graph-partitioning conjecture,\r\nwhich
    we believe to be of independent interest, and whose resolution would imply the\r\nKohayakawa–Kreuter
    conjecture."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: EDEN
  full_name: KUPERWASSER, EDEN
  last_name: KUPERWASSER
- first_name: WOJCIECH
  full_name: SAMOTIJ, WOJCIECH
  last_name: SAMOTIJ
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: KUPERWASSER E, SAMOTIJ W, Wigderson Y. On the Kohayakawa–Kreuter conjecture.
    <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>. 2025;178(3):293-320.
    doi:<a href="https://doi.org/10.1017/s0305004125000143">10.1017/s0305004125000143</a>
  apa: KUPERWASSER, E., SAMOTIJ, W., &#38; Wigderson, Y. (2025). On the Kohayakawa–Kreuter
    conjecture. <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>.
    Cambridge University Press. <a href="https://doi.org/10.1017/s0305004125000143">https://doi.org/10.1017/s0305004125000143</a>
  chicago: KUPERWASSER, EDEN, WOJCIECH SAMOTIJ, and Yuval Wigderson. “On the Kohayakawa–Kreuter
    Conjecture.” <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>.
    Cambridge University Press, 2025. <a href="https://doi.org/10.1017/s0305004125000143">https://doi.org/10.1017/s0305004125000143</a>.
  ieee: E. KUPERWASSER, W. SAMOTIJ, and Y. Wigderson, “On the Kohayakawa–Kreuter conjecture,”
    <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>, vol. 178,
    no. 3. Cambridge University Press, pp. 293–320, 2025.
  ista: KUPERWASSER E, SAMOTIJ W, Wigderson Y. 2025. On the Kohayakawa–Kreuter conjecture.
    Mathematical Proceedings of the Cambridge Philosophical Society. 178(3), 293–320.
  mla: KUPERWASSER, EDEN, et al. “On the Kohayakawa–Kreuter Conjecture.” <i>Mathematical
    Proceedings of the Cambridge Philosophical Society</i>, vol. 178, no. 3, Cambridge
    University Press, 2025, pp. 293–320, doi:<a href="https://doi.org/10.1017/s0305004125000143">10.1017/s0305004125000143</a>.
  short: E. KUPERWASSER, W. SAMOTIJ, Y. Wigderson, Mathematical Proceedings of the
    Cambridge Philosophical Society 178 (2025) 293–320.
date_created: 2026-06-29T10:55:00Z
date_published: 2025-04-28T00:00:00Z
date_updated: 2026-07-14T08:38:08Z
day: '28'
doi: 10.1017/s0305004125000143
extern: '1'
external_id:
  arxiv:
  - '2307.16611'
fulldoi: https://doi.org/10.1017/s0305004125000143
intvolume: '       178'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2307.16611
mathsc:
- 05C80
- 05C55
- 05D10
month: '04'
oa: 1
oa_version: Preprint
page: 293-320
publication: Mathematical Proceedings of the Cambridge Philosophical Society
publication_identifier:
  eissn:
  - 1469-8064
  issn:
  - 0305-0041
publication_status: published
publisher: Cambridge University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the Kohayakawa–Kreuter conjecture
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 178
year: '2025'
...
---
_id: '9364'
abstract:
- lang: eng
  text: 'Let t : Fp → C be a complex valued function on Fp. A classical problem in
    analytic number theory is bounding the maximum M(t) := max 0≤H<p ∣ 1/√p ∑ 0≤n<H
    t (n) ∣ of the absolute value of the incomplete sums(1/√p)∑0≤n<H t (n). In this
    very general context one of the most important results is the Pólya–Vinogradov
    bound M(t)≤IIˆtII∞ log 3p, where ˆt : Fp → C is the normalized Fourier transform
    of t. In this paper we provide a lower bound for certain incomplete Kloosterman
    sums, namely we prove that for any ε > 0 there exists a large subset of a ∈ F×p
    such that for kl a,1,p : x → e((ax+x) / p) we have M(kla,1,p) ≥ (1−ε/√2π + o(1))
    log log p, as p→∞. Finally, we prove a result on the growth of the moments of
    {M (kla,1,p)}a∈F×p. 2020 Mathematics Subject Classification: 11L03, 11T23 (Primary);
    14F20, 60F10 (Secondary).'
acknowledgement: I am most thankful to my advisor, Emmanuel Kowalski, for suggesting
  this problem and for his guidance during these years. I also would like to thank
  Youness Lamzouri for informing me about his work on sum of incomplete Birch sums
  and Tal Horesh for her suggestions on a previous version of the paper. Finally,
  I am very grateful to the anonymous referee for their careful reading of the manuscript
  and their valuable comments.
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Dante
  full_name: Bonolis, Dante
  id: 6A459894-5FDD-11E9-AF35-BB24E6697425
  last_name: Bonolis
citation:
  ama: Bonolis D. On the size of the maximum of incomplete Kloosterman sums. <i>Mathematical
    Proceedings of the Cambridge Philosophical Society</i>. 2022;172(3):563-590. doi:<a
    href="https://doi.org/10.1017/S030500412100030X">10.1017/S030500412100030X</a>
  apa: Bonolis, D. (2022). On the size of the maximum of incomplete Kloosterman sums.
    <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>. Cambridge
    University Press. <a href="https://doi.org/10.1017/S030500412100030X">https://doi.org/10.1017/S030500412100030X</a>
  chicago: Bonolis, Dante. “On the Size of the Maximum of Incomplete Kloosterman Sums.”
    <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>. Cambridge
    University Press, 2022. <a href="https://doi.org/10.1017/S030500412100030X">https://doi.org/10.1017/S030500412100030X</a>.
  ieee: D. Bonolis, “On the size of the maximum of incomplete Kloosterman sums,” <i>Mathematical
    Proceedings of the Cambridge Philosophical Society</i>, vol. 172, no. 3. Cambridge
    University Press, pp. 563–590, 2022.
  ista: Bonolis D. 2022. On the size of the maximum of incomplete Kloosterman sums.
    Mathematical Proceedings of the Cambridge Philosophical Society. 172(3), 563–590.
  mla: Bonolis, Dante. “On the Size of the Maximum of Incomplete Kloosterman Sums.”
    <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>, vol. 172,
    no. 3, Cambridge University Press, 2022, pp. 563–90, doi:<a href="https://doi.org/10.1017/S030500412100030X">10.1017/S030500412100030X</a>.
  short: D. Bonolis, Mathematical Proceedings of the Cambridge Philosophical Society
    172 (2022) 563–590.
das_tickbox: '0'
date_created: 2021-05-02T22:01:29Z
date_published: 2022-05-01T00:00:00Z
date_updated: 2026-08-06T11:08:12Z
day: '01'
ddc:
- '510'
department:
- _id: TiBr
doi: 10.1017/S030500412100030X
external_id:
  arxiv:
  - '1811.10563'
  isi:
  - '000784421500001'
file:
- access_level: open_access
  checksum: 614d2e9b83a78100408e4ee7752a80a8
  content_type: application/pdf
  creator: cchlebak
  date_created: 2021-12-01T14:01:54Z
  date_updated: 2021-12-01T14:01:54Z
  file_id: '10395'
  file_name: 2021_MathProcCamPhilSoc_Bonolis.pdf
  file_size: 334064
  relation: main_file
  success: 1
file_date_updated: 2021-12-01T14:01:54Z
fulldoi: https://doi.org/10.1017/S030500412100030X
has_accepted_license: '1'
intvolume: '       172'
isi: 1
issue: '3'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '05'
oa: 1
oa_version: Published Version
page: 563 - 590
publication: Mathematical Proceedings of the Cambridge Philosophical Society
publication_identifier:
  eissn:
  - 1469-8064
  issn:
  - 0305-0041
publication_status: published
publisher: Cambridge University Press
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: On the size of the maximum of incomplete Kloosterman sums
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 172
year: '2022'
...