New bounds for the distance Ramsey number

In this paper we study the distance Ramsey number \(R_{{\it D}}(s,t,d)\). The \textit{distance Ramsey number} \(R_{{\it D}}(s,t,d) \) is the minimum number \(n\) such that for any graph \( G \) on \( n \) vertices, either \(G\) contains an induced \( s \)-vertex subgraph isomorphic to a distance gra...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2013-07
Main Authors: Kupavskii, Andrey, Raigorodskii, Andrei, Titova, Maria
Format: Article
Language:English
Subjects:
Apexes
Graph theory
Lower bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we study the distance Ramsey number \(R_{{\it D}}(s,t,d)\). The \textit{distance Ramsey number} \(R_{{\it D}}(s,t,d) \) is the minimum number \(n\) such that for any graph \( G \) on \( n \) vertices, either \(G\) contains an induced \( s \)-vertex subgraph isomorphic to a distance graph in \( \Real^d \) or \( \bar {G} \) contains an induced \( t \)-vertex subgraph isomorphic to the distance graph in \( \Real^d \). We obtain the upper and lower bounds on \(R_{{\it D}}(s,s,d),\) which are similar to the bounds for the classical Ramsey number \(R(\lceil \frac{s}{[d/2]} \rceil, \lceil \frac{s}{[d/2]} \rceil)\).
ISSN:2331-8422