On some Zarankiewicz numbers and bipartite Ramsey numbers for quadrilateral.

Abstract: The Zarankiewicz number

z (m, n; s, t)

is the maximum number of edges in a subgraph of

K_{m, n}

that does not contain

K_{s, t}

as a subgraph. The bipartite Ramsey number

b (n_{1}, c d o t s, n_{k})

is the least positive integer

b

such that any coloring of the edges of

K_{b, b}

with

k

colors will result in a monochromatic copy of

K_{n_{i}, n_{i}}

in the

i

-th color, for some

i

,

1 l e i l e k

. If

n_{i} = m

for all

i

, then we denote this number by

b_{k} (m)

. In this paper we obtain the exact values of some Zarankiewicz numbers for quadrilateral (

s = t = 2

), and we derive new bounds for diagonal multicolor bipartite Ramsey numbers avoiding quadrilateral. In particular, we prove that

b_{4} (2) = 19

, and establish new general lower and upper bounds on

b_{k} (2)

.

Recommendations

Cited In (3)

This page was built for publication: On some Zarankiewicz numbers and bipartite Ramsey numbers for quadrilateral.