A short note on supersaturation for oddtown and eventown

Abstract: Given a collection

m a t h c a l A

of subsets of an

n

element set, let

e x t o p (m a t h c a l A)

denote the number of distinct pairs

A, B i n m a t h c a l A

for which

| A c a p B |

is odd. For

s i n 1, 2

, we prove

e x t o p (m a t h c a l A) g e q s c d o t 2^{l f l o o r n / 2 f l o o r - 1}

for any collection

m a t h c a l A

of

2^{l f l o o r n / 2 f l o o r} + s

even-sized subsets of an

n

element set. We also prove

e x t o p (m a t h c a l A) g e q 3

for any collection

m a t h c a l A

of

n + 1

odd-sized subsets of an

n

element set that. Moreover, we show that both of these results are best possible. We then consider larger collections of odd-sized and even-sized sets respectively and explore the connection to minimizing the number of pairwise intersections of size exactly

k - 2

amongst collections of size

k

subsets from an

n

element set.

Review text

Let \(n\) be a positive integer. For any family \(\mathcal{A}\) of subsets of \(\{1, \dots, n\}\), let \(\mathrm{op}(\mathcal{A})\) denote the size of the set \(\{\{A, B\} \colon A, B \in \mathcal{A}, \, A \neq B, \, |A \cap B| \mbox{ is odd}\}\). \textit{P. Erdős} [in: Proceedings of the 5th British combinatorial conference 1975. University of Aberdeen, Aberdeen, July 14--18, 1975. Winnipeg: Utilitas Mathematica Publishing Inc. 169--192 (1976; Zbl 0335.05002)] asked how large \(\mathcal{A}\) can be if the size of the intersection of every two distinct sets in \(\mathcal{A}\) is (a) even (b) odd. This was answered independently by \textit{E. R. Berlekamp} [Can. Math. Bull. 12, 471--474 (1969; Zbl 0272.05004)] and \textit{J. E. Graver} [Linear Algebra Appl. 10, 111--128 (1975; Zbl 0301.05012)]. Motivated by this, the author makes the following conjectures: \begin{itemize} \item[(1)] If \(1 \leq s \leq 2^{\lfloor n/2 \rfloor} - 2^{\lfloor n/4 \rfloor}\), \(|\mathcal{A}| \geq 2^{\lfloor n/2 \rfloor} + s\), and the sets in \(\mathcal{A}\) are of even size, then \(\mathrm{op}(\mathcal{A}) \geq 2^{\lfloor n/2 \rfloor - 1}s\). \item[(2)] If \(1 \leq s \leq n\), \(|\mathcal{A}| \geq n+s\), and the sets in \(\mathcal{A}\) are of odd size, then \(\mathrm{op}(\mathcal{A}) \geq 3s\). \end{itemize} Conjecture (1) is verified for \(s \in \{1, 2\}\), and conjecture (2) is verified for \(s = 1\). These results are shown to be the best possible.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: A short note on supersaturation for oddtown and eventown

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6157418)