Globally sparse vertex‐ramsey graphs (Q4277989)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 490728
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Globally sparse vertex‐ramsey graphs |
scientific article; zbMATH DE number 490728 |
Statements
Globally sparse vertex‐ramsey graphs (English)
0 references
22 June 1994
0 references
monochromatic
0 references
global density
0 references
critical Ramsey density
0 references
complete graphs
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0.8918209
0 references
0 references
0.86918956
0 references
The ``arrow'' notation from Ramsey Theory writes \(F\to(G)^ 1_ r\) if every \(r\)-coloring of the vertices of a graph \(F\) contains a (not necessarily induced) copy of \(G\) whose vertices are monochromatic. If \(F\) has relatively few edges and these edges are uniformly distributed, it may be impossible to force a monochromatic \(G\). Specifically, define the global density of \(F\), \(m(F)\), as the maximum over all subgraphs of the ratio \(\#\text{edges}/\#\text{vertices}\). The critical Ramsey density of \(G\) with \(r\) colors, \(m_{cr}(G,r)\), is the \(\inf\{m(F):F\to(G)^ 1_ r\}\). That is, the global density of \(F\) must be at least \(m_{cr}(G,r)\) to have any possibility that every \(r\)-coloring of \(F\) contains a monochromatic \(G\). The authors prove that \(r\delta_ M/2\leq m_{cr}(G,r)<r\delta_ M\), where \(\delta_ M=\max\{\delta(H):H\subset G\}\) and \(\delta(H)\) is the minimum degree of \(H\). The lower bound is achieved by complete graphs. The complete bipartite graphs \(K_{1,k}\) have \(m_{cr}(K_{1,k},r)>r- \varepsilon\) for sufficiently large \(k\), so the upper bound cannot be improved.
0 references