Science Talk

Guest · Posted: Sun Jul 13, 2008 6:51 pm Post subject: Combinatorial covers

I've had a little trouble with one aspect of combinatorial covers
recently, and I'd be grateful if anyone could help me.

Let R be a cover of (U x V), where for some Boolean function f, U =
f^{-1}(0) and V = f^{-1}(1). Then, alpha(R) is defined as the smallest
disjoint cover of (U x V) embedded in R.

However, I have not been able to find out whether, in the situation
described, a disjoint cover is always embedded in R. In addition, I
can't tell whether, should no disjoint cover be embedded, alpha(R) is
defined as zero, infinity, or simply "undefined". Can anyone help me
out?

Thanks,

James McLaughlin.

Guest · Posted: Sun Jul 13, 2008 7:48 pm Post subject: Re: Combinatorial covers

After reading a paper by Razborov, I realise that that question may
have been a bit ambiguous. All covers need to be sets of combinatorial
rectangles.

(I'm pretty sure this is part of the defintion anyway, but the way one
proof was phrased made me think I'd better specify this.)