On sizes of 1-cross intersecting set pair systems

Abstract: Let

{(A_{i}, B_{i})}_{i = 1}^{m}

be a set pair system. F"{u}redi, Gy'{a}rf'{a}s and Kir'{a}ly called it {em

1

-cross intersecting} if

| A_{i} c a p B_{j} |

is

1

when

i e q j

and

0

if

i = j

. They studied such systems and their generalizations, and in particular considered

m (a, b, 1)

-- the maximum size of a

1

-cross intersecting set pair system in which

| A_{i} | l e q a

and

| B_{i} | l e q b

for all

i

. F"{u}redi, Gy'{a}rf'{a}s and Kir'{a}ly proved that

m (n, n, 1) g e q 5^{(n - 1) / 2}

and asked whether there are upper bounds on

m (n, n, 1)

significantly better than the classical bound

2 n c h o o s e n

of Bollob' as for cross intersecting set pair systems. Answering one of their questions, Holzman recently proved that if

a, b g e q 2

, then

. He also conjectured that the factor

f r a c 2930

in his bound can be replaced by

f r a c 56

. The goal of this paper is to prove this bound.

Recommendations

Cites Work

Cited In (4)

This page was built for publication: On sizes of 1-cross intersecting set pair systems