A Ramsey property of random regular and   k  ‐out graphs | Zendy

Anastos Michael | Zendy; Bal Deepak | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

A Ramsey property of random regular and k ‐out graphs

Author(s) -

Anastos Michael,

Bal Deepak

Publication year - 2020

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.22491

Subject(s) - mathematics , monochromatic color , combinatorics , ramsey's theorem , ramsey theory , property (philosophy) , constant (computer programming) , random graph , discrete mathematics , order (exchange) , graph , computer science , philosophy , epistemology , finance , economics , programming language , botany , biology

In this study we consider a Ramsey property of random d ‐regular graphs, G ( n , d ) . Let r ≥ 2 be fixed. Then w.h.p. the edges of G ( n , 2 r )can be colored such that every monochromatic component has order o ( n ) . On the other hand, there exists a constant γ > 0 such that w.h.p., every r ‐coloring of the edges of G ( n , 2 r + 1 )must contain a monochromatic cycle of length at least γ n . We prove an analogous result for random k ‐out graphs.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research