English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Size-Ramsey numbers are a central notion in combinatorics and have beenwidely studied since their introduction by Erd\H{o}s, Faudree, Rousseau andSchelp in 1978. Research has mainly focused on the size-Ramsey numbers of$n$-vertex graphs with constant maximum degree $\Delta$. For example, graphswhich also have constant treewidth are known to have linear size-Ramseynumbers. On the other extreme, the canonical examples of graphs of unboundedtreewidth are the grid graphs, for which the best known bound has only veryrecently been improved from $O(n^{3/2})$ to $O(n^{5/4})$ by Conlon, Nenadov andTruji\'c. In this paper, we prove a common generalization of these results byestablishing new bounds on the size-Ramsey numbers in terms of treewidth (whichmay grow as a function of $n$). As a special case, this yields a bound of$\tilde{O}(n^{3/2 - 1/2\Delta})$ for proper minor-closed classes of graphs. Inparticular, this bound applies to planar graphs, addressing a question ofKamcev, Liebenau, Wood and Yepremyan.  Our proof combines methods from structural graph theory and classicRamsey-theoretic embedding techniques, taking advantage of the productstructure exhibited by graphs with bounded treewidth.

Size-Ramsey numbers of structurally sparse graphs