No label defined (Q4669841)

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 2157260
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 2157260

      Statements

      0 references
      0 references
      0 references
      15 April 2005
      0 references
      bipartite graphs
      0 references
      norm-graphs
      0 references
      Ramsey numbers
      0 references
      For two graphs \(F, H\), the Ramsey number \(r(F, H)\) is the minimum number \(n\) such that if a graph \(G\) has \(n\) vertices, then either \(G\) has a subgraph isomorphic to \(F\) or the complement of \(G\) has a subgraph isomorphic to \(H\). The authors observe that the projective \(K_{3,3}\)-free norm-graph \(H(q, 3)\) defined by \textit{N. Alon, L. Rónyai} and \textit{T. Szabó} [J. Comb. Theory, Ser. B 76, 280--290 (1999; Zbl 0935.05054)] is also \(K_{2,q+2}\)-free. Since \(H(q, 3)\) is \(r=(q^2-1)\)-regular on \(n=q^3-q^2\) vertices, the authors obtain that \(r(F, H) \geq n + 1\), where \(F = K_{3,3}\) or \(K_{2,q+2}\), and \(H = K_{2, t}\), \(K_{3, s}\) or \(K_{1, m}\), \(t = n-2r+q+2\), \(s = n -3r+3q+4\), \(m = n -r+1\), \(q\) is a prime power. The authors recall the \(K_{2, t+1}\)-free graph \(G\) on \(n = (q^2-1)/t\) vertices defined by \textit{Z. Füredi} [J. Comb. Theory, Ser. A 75, 141--144 (1996; Zbl 0858.05064)]. Since every vertex in \(G\) is adjacent to \(q\) or \(q-1\) vertices, they conclude that \(r(K_{2, t+1}, K_{2, s+1}) \geq n +1\), where \(s = n-2(q-1)+t\), and \(q\) is a prime power. Finally, by applying \(2\text{ex}(n, K_{2, t+1}) \leq z(n, n, 2, t+1) \leq n \sqrt{tn-t+1/4} +n/2\), where the Turán number ex\((n, K_{2, t+1})\) is the maximum number of edges of a \(K_{2, t+1}\)-free graph on \(n\) vertices, \(z(n, n, 2, t+1)\) is the maximum number \(z\) such that there exists an \(n \times n\) \(0, 1\) matrix containing \(z\) \(1\)'s without a \(2 \times (t+1)\) submatrix consisting of entirely \(1\)'s, the authors conclude that \(r(K_{2, t+1}, K_{2, s+1}) \leq \lceil (\sqrt{t} + \sqrt{s} + \sqrt{(\sqrt{t} + \sqrt{s})^2+5})^2/4 \rceil\).
      0 references

      Identifiers