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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we introduce a general framework for proving lower bounds forvarious Ramsey type problems within random settings. The main idea is to viewthe problem from an algorithmic perspective: we aim at providing an algorithmthat finds the desired colouring with high probability. Our framework allows toreduce the probabilistic problem of whether the Ramsey property at hand holdsfor random (hyper)graphs with edge probability $p$ to a deterministic questionof whether there exists a finite graph that forms an obstruction.  In the second part of the paper we apply this framework to address and solvevarious open problems. In particular, we extend the result of Bohman, Frieze,Pikhurko and Smyth (2010) for bounded anti-Ramsey problems in random graphs tothe case of $2$ colors and to hypergraph cliques. As a corollary, this proves amatching lower bound for the result of Friedgut, R\"odl and Schacht (2010) and,independently, Conlon and Gowers (2014+) for the classical Ramsey problem forhypergraphs in the case of cliques. Finally, we provide matching lower boundsfor a proper-colouring version of anti-Ramsey problems introduced byKohayakawa, Konstadinidis and Mota~(2014) in the case of cliques and cycles.

An algorithmic framework for obtaining lower bounds for random Ramsey problems