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
15 April 2005
0 references
bipartite graphs
0 references
norm-graphs
0 references
Ramsey numbers
0 references
0 references
0.6846035
0 references
0.6835395
0 references
0.6793129
0 references
0 references
0.6749349
0 references
0.6734127
0 references
0.6717151
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