---
OA_place: publisher
OA_type: hybrid
_id: '19418'
abstract:
- lang: eng
  text: The size-Ramsey number r^(H) of a graph H is the smallest number of edges
    a (host) graph G can have, such that for any red/blue colouring of G, there is
    a monochromatic copy of H in G. Recently, Conlon, Nenadov and Trujić showed that
    if H is a graph on n vertices and maximum degree three, then r^(H)=O(n8/5), improving
    upon the upper bound of n5/3+o(1) by Kohayakawa, Rödl, Schacht and Szemerédi.
    In this paper we show that r^(H)≤n3/2+o(1). While the previously used host graphs
    were vanilla binomial random graphs, we prove our result using a novel host graph
    construction. Our bound hits a natural barrier of the existing methods.
acknowledgement: 'We would like to thank Rajko Nenadov and Miloš Trujić for helpful
  comments and discussions, as well as the anonymous referees for their very useful
  feedback, which improved the paper considerably. This research was supported by
  SNSF Project 217926. Part of this research was conducted while Nemanja Draganić
  was at ETH Zürich, Switzerland, and partially supported by SNSF Grant 200021_196965.
  This project has received funding from the European Union''s Horizon 2020 research
  and innovation programme under the Marie Skłodowska-Curie Grant Agreement Number:
  101034413. Part of this research was conducted while Kalina Petrova was at the Department
  of Computer Science, ETH Zürich, Switzerland, supported by SNSF Grant CRSII5 173721.'
article_number: e70116
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Nemanja
  full_name: Draganić, Nemanja
  last_name: Draganić
- first_name: Kalina H
  full_name: Petrova, Kalina H
  id: 554ff4e4-f325-11ee-b0c4-a10dbd523381
  last_name: Petrova
citation:
  ama: Draganić N, Petrova KH. Size‐Ramsey numbers of graphs with maximum degree three.
    <i>Journal of the London Mathematical Society</i>. 2025;111(3). doi:<a href="https://doi.org/10.1112/jlms.70116">10.1112/jlms.70116</a>
  apa: Draganić, N., &#38; Petrova, K. H. (2025). Size‐Ramsey numbers of graphs with
    maximum degree three. <i>Journal of the London Mathematical Society</i>. Wiley.
    <a href="https://doi.org/10.1112/jlms.70116">https://doi.org/10.1112/jlms.70116</a>
  chicago: Draganić, Nemanja, and Kalina H Petrova. “Size‐Ramsey Numbers of Graphs
    with Maximum Degree Three.” <i>Journal of the London Mathematical Society</i>.
    Wiley, 2025. <a href="https://doi.org/10.1112/jlms.70116">https://doi.org/10.1112/jlms.70116</a>.
  ieee: N. Draganić and K. H. Petrova, “Size‐Ramsey numbers of graphs with maximum
    degree three,” <i>Journal of the London Mathematical Society</i>, vol. 111, no.
    3. Wiley, 2025.
  ista: Draganić N, Petrova KH. 2025. Size‐Ramsey numbers of graphs with maximum degree
    three. Journal of the London Mathematical Society. 111(3), e70116.
  mla: Draganić, Nemanja, and Kalina H. Petrova. “Size‐Ramsey Numbers of Graphs with
    Maximum Degree Three.” <i>Journal of the London Mathematical Society</i>, vol.
    111, no. 3, e70116, Wiley, 2025, doi:<a href="https://doi.org/10.1112/jlms.70116">10.1112/jlms.70116</a>.
  short: N. Draganić, K.H. Petrova, Journal of the London Mathematical Society 111
    (2025).
date_created: 2025-03-19T09:03:37Z
date_published: 2025-03-01T00:00:00Z
date_updated: 2025-09-30T11:05:07Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1112/jlms.70116
ec_funded: 1
external_id:
  arxiv:
  - '2207.05048'
  isi:
  - '001450645400019'
file:
- access_level: open_access
  checksum: d8e0a03286a44c4f672709e3c829206e
  content_type: application/pdf
  creator: dernst
  date_created: 2025-03-20T09:46:20Z
  date_updated: 2025-03-20T09:46:20Z
  file_id: '19427'
  file_name: 2025_JournLondonMath_Draganic.pdf
  file_size: 625974
  relation: main_file
  success: 1
file_date_updated: 2025-03-20T09:46:20Z
has_accepted_license: '1'
intvolume: '       111'
isi: 1
issue: '3'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
publication: Journal of the London Mathematical Society
publication_identifier:
  eissn:
  - 1469-7750
  issn:
  - 0024-6107
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Size‐Ramsey numbers of graphs with maximum degree three
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: 111
year: '2025'
...