Distance Ramsey numbers (Q2375971): Difference between revisions

A graph is a distance graph in \(R^d,\) the \(d\)-dimension Euclidean space, if its vertices can be associated with different points of \(R^d\) such that any pair of adjacent vertices of such a graph corresponds to a pair of points a unit distance apart. This paper studies the distance Ramsey number, \(R_{\text{NEH}}(s, t, d),\) i.e., the minimum positive number \(R\) such that, for any graph \(G\) on \(R\) vertices, either the graph itself contains an induced \(s\)-vertex subgraph isomorphic to a distance graph in \(R^d\) or the complement of the graph contains an induced \(t\)-vertex subgraph isomorphic to a distance graph in \(R^d.\) The central result as reported in this paper is a tighter lower bound of the distance Ramsey number for a fixed \(d\) as follows: for \(d\geq 4\) and \(\gamma>0,\) there exists \(s_0=s_0(d, \gamma)\) such that for all \(s \geq s_0,\) \[ R_{\text{NEH}}(s, s, d) \geq 2^{\left (\frac{1}{2 [d/2]}-\gamma \right )s}. \] Clearly, the gist of showing \(R_{\text{NEH}}(s, s, d)>n\) is to demonstrate the existence of an \(n\)-vertex graph \(G\) such that no \(s\)-vertex induced subgraph of \(G\) and its complement is isomorphic to a distance graph in \(R^d.\) This task is accomplished in this paper by showing that, for all sufficiently large \(s,\) there is an \(n\)-vertex graph \(G\) such that the number of \(k\)-cliques, where \(k=\left [ \frac{d}{2} \right ]+1,\) in any of the \(s\)-vertex induced subgraphs of both \(G\) and its complement exceeds \(s^{k-\epsilon},\) where \(\epsilon\) depends only on \(d.\) This is naturally done following a probabilistic approach, making use of the classical Erdős-Rényi model \(G(n, \frac{1}{2}).\)