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
      0 references
      0 references
      22 June 1994
      0 references
      monochromatic
      0 references
      global density
      0 references
      critical Ramsey density
      0 references
      complete graphs
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references