# A note on $k$-wise oddtown problems

Jason O’Neill 111Research supported by NSF award DMS-1800332
Department of Mathematics,
University of California, San Diego
<EMAIL_ADDRESS>Jacques Verstraëte 11footnotemark: 1
Department of Mathematics,
University of California, San Diego
<EMAIL_ADDRESS>
###### Abstract

For integers $2\leq t\leq k$, we consider a collection of $k$ set families
$\mathcal{A}_{j}:1\leq j\leq k$ where
$\mathcal{A}_{j}=\\{A_{j,i}\subseteq[n]:1\leq i\leq m\\}$ and
$|A_{1,i_{1}}\cap\cdots\cap A_{k,i_{k}}|$ is even if and only if at least $t$
of the $i_{j}$ are distinct. In this paper, we prove that $m=O(n^{1/\lfloor
k/2\rfloor})$ when $t=k$ and $m=O(n^{1/(t-1)})$ when $2t-2\leq k$ and prove
that both of these bounds are best possible. Specializing to the case where
$\mathcal{A}=\mathcal{A}_{1}=\cdots=\mathcal{A}_{k}$, we recover a variation
of the classical oddtown problem.

##  1 Introduction

Given a collection $\mathcal{A}$ of subsets of an $n$ element set,
$\mathcal{A}$ follows oddtown rules if the sizes of all sets in $\mathcal{A}$
are odd and distinct pairs of sets from $\mathcal{A}$ have even sized
intersections. Berlekemp [4] proved that the size of a family which satisfies
oddtown rules is at most $n$ which is easily seen to be best possible. One
generalization of this classical result is the skew oddtown theorem which
appears in Babai and Frankl [3]:

######  Theorem 1 (Babai, Frankl [3]).

Let $\mathcal{A}=\\{A_{1},A_{2},\dots,A_{m}\\}$ and
$\mathcal{B}=\\{B_{1},B_{2},\dots,B_{m}\\}$ be families of subsets of an $n$
element set where $|A_{i}\cap B_{i}|$ is odd for all $i\in[m]$ and $|A_{i}\cap
B_{j}|$ is even for all $i<j\in[m]$. Then $m\leq n$.

In this paper, we give analogs of Theorem 1 for $k\geq 3$ families. Our main
result is as follows:

######  Theorem 2.

Let $(\mathcal{A}_{1},\mathcal{A}_{2},\dots,\mathcal{A}_{k})$ be set families
of an $n$ element set with $\mathcal{A}_{j}=\\{A_{j,i}:1\leq i\leq m\\}$ where
$|\bigcap_{j=1}^{k}A_{j,i_{j}}|$ is even if and only if
$i_{1},\ldots,i_{k}\in[m]$ are all distinct. Then $m=O(n^{1/\lfloor
k/2\rfloor})$.

By employing a connection to a hypergraph covering problem and a hypergraph
extension (see Alon [2], Cioabă-Kündgen-Verstraëte [5], and Leader-Milićević-
Tan [11]) of the Graham-Pollak Theorem [10], we also show that Theorem 2 is
best possible. Moreover, we prove the following:

######  Theorem 3.

Let $t,k$ be integers with $t\geq 2$ and $2t-2\leq k$. If
$(\mathcal{A}_{1},\mathcal{A}_{2},\dots,\mathcal{A}_{k})$ are set families of
an $n$ element set with $\mathcal{A}_{j}=\\{A_{j,i}:1\leq i\leq m\\}$ where
$|\bigcap_{j=1}^{k}A_{j,i_{j}}|$ is even if and only if at least $t$ of the
$i_{j}$ are distinct, then $m=O(n^{1/(t-1)})$.

Theorem 3 is seen to be best possible by again using a connection to a
hypergraph covering problem. In the case where
$\mathcal{A}=\mathcal{A}_{1}=\cdots=\mathcal{A}_{k}$, we recover a variation
of the classical oddtown problem. For integers $t<k$, a family
$\mathcal{A}\subseteq 2^{[n]}$ is said to follow $(k,t)$-oddtown rules if the
intersection of any $d$ distinct sets in $\mathcal{A}$ is odd if $d<t$ and
even if $t\leq d\leq k$.

######  Corollary 1.

Let $t,k\in\mathbb{N}$ be so that $2\leq t\leq k$ and $2t-2\leq k$. If
$\mathcal{A}\subset 2^{[n]}$ follows $(k,t)$-oddtown rules, then
$|\mathcal{A}|=O(n^{1/(t-1)})$.

Corollary 1 is best possible by considering
$\mathcal{A}_{i}=\\{A\in\binom{[n]}{t-1}:i\in A\\}$ for $i\in[n]$ for $n$ so
that the binomial coefficients corresponding to the size of the $d$-wise
intersections are odd for $d<t$. The first open case is $(3,3)$-oddtown for
which the above construction has size $\Theta(n^{1/2})$. If
$\mathcal{A}=\\{A_{1},\ldots,A_{m}\\}$ satisfies $(3,3)$-oddtown rules, then
$\mathcal{A}^{\prime}=\\{A_{1}\cap A_{i}:2\leq i\leq m\\}$ satisfies oddtown
rules and thus $|\mathcal{A}|\leq n+1$. This is unlikely to be best possible
as this holds replacing $A_{1}$ with any $A_{j}\in\mathcal{A}$.

When $t<k$ and $2t-2>k$, we are able to show that $m=O(n^{1/(k-t+1)})$ (see
Section 4), and conjecture that a stronger bound holds:

######  Conjecture 1.

Let $t,k$ be integers with $t\geq 2$ and $2t-2>k$. If
$(\mathcal{A}_{1},\mathcal{A}_{2},\dots,\mathcal{A}_{k})$ are set families of
an $n$ element set with $\mathcal{A}_{j}=\\{A_{j,i}:1\leq i\leq m\\}$ where
$|\bigcap_{j=1}^{k}A_{j,i_{j}}|$ is even if and only if at least $t$ of the
$i_{j}$ are distinct, then $m=O(n^{1/\lfloor k/2\rfloor})$.

The bound $m=O(n^{1/\lfloor k/2\rfloor})$ comes from a connection to a
hypergraph covering problem (see Section 2) and would imply that Conjecture 1
if true is tight.

Many results in extremal set theory regarding even/odd sized intersections
have been extended to arbitrary primes $p$. Given a prime $p$ and a set
$L\subset[0,p-1]$, $\mathcal{A}\subseteq 2^{[n]}$ is a $(p,L)$-intersecting
set system if for all $A\in\mathcal{A}$, $|A|\notin L\pmod{p}$, but for all
distinct $A_{1},A_{2}\in\mathcal{A}$, $|A_{1}\cap A_{2}|\in L\pmod{p}$. For
more on $(p,L)$-intersecting set systems, see Deza-Frankl-Singhi [6] as well
as Frankl and Tokushige [7]. For $k\geq 3$, Szabó and Vu [13] consider
$k$-wise oddtown problems wherein the size of the sets are odd and the sizes
of intersections of $k$ distinct sets are even. Grolmusz and Sudakov [8] study
$k$-wise $(p,L)$-intersecting set systems where the size of distinct $k$-wise
intersections are in $L\pmod{p}$. Similarly, we propose the following
extension to Theorem 2 for primes $p>2$.

######  Conjecture 2.

Let $p$ be prime and $(\mathcal{A}_{1},\mathcal{A}_{2},\dots,\mathcal{A}_{k})$
be set families of an $n$ element set with $\mathcal{A}_{j}=\\{A_{j,i}:1\leq
i\leq m\\}$ where $|\bigcap_{j=1}^{k}A_{j,i_{j}}|$ is nonzero modulo $p$ if
and only if $i_{1},\ldots,i_{k}\in[m]$ are all distinct. Then
$m=O(n^{(p-1)/\lfloor k/2\rfloor})$.

Füredi and Sudakov [8, Lemma 3.1] used multilinear polynomials to prove if
$\mathcal{A}=\\{A_{1},\ldots,A_{m}\\}$ and
$\mathcal{B}=\\{B_{1},\ldots,B_{m}\\}$ are families of subsets of an $n$
element set where $|A_{i}\cap B_{j}|$ is nonzero modulo $p$ if and only if
$i\neq j$, then

$m\leq\sum_{i=0}^{p-1}\binom{n}{i}.$ (1)

It follows that (1) is asymptotically best possible by taking
$\mathcal{A}=\binom{[n]}{p-1}$ and $\mathcal{B}$ to be the corresponding
complements. This verifies Conjecture 2 when $k=2$.

Structure and Organization: Throughout the paper, we let
$[n]:=\\{1,2,\ldots,n\\}$ and $\binom{[n]}{k}$ denote the complete $k$-uniform
hypergraph, or $k$-graph. Let $K_{n:k}$ denote the Kneser graph with
$V(K_{n:k})=\binom{[n]}{k}$ and $(A,B)\in E(K_{n:k})$ if and only if $A\cap
B=\emptyset$. Given subsets $X_{1},\ldots,X_{k}$ of $[n]$, let
$\prod_{i=1}^{k}X_{i}$ denote the complete $k$-partite $k$-graph with edges
consisting of exactly one vertex from each part $X_{1},\ldots,X_{k}$. For
$k=2$, we refer to complete bipartite graphs as bicliques. Given a subset
$A\subseteq[n]$, let $v_{X}\in\mathbb{F}_{2}^{n}$ denote its characteristic
vector and $(v_{X})_{k}$ denote its $k$th component. For a family
$\mathcal{A}=\\{A_{1},\ldots,A_{m}\\}\subseteq 2^{[n]}$, let
$\mathcal{A}^{c}=\\{A_{1}^{c},\ldots,A_{m}^{c}\\}\subseteq 2^{[n]}$ be the
corresponding complements. We denote the adjacency matrix of a graph $G$ by
$A(G)$. For functions $f,g:\mathbb{N}\rightarrow\mathbb{R}^{+}$, we write
$f\sim g$ if $\lim_{n\rightarrow\infty}f(n)/g(n)=1$, $f=o(g)$ if
$\lim_{n\rightarrow\infty}f(n)/g(n)=0$, and $f=O(g)$ and $g=\Omega(f)$ if
there exists $c>0$ such that $f(n)\leq cg(n)$ for all $n\in\mathbb{N}$. If
$f=O(g)$ and $g=O(f)$, we write $f=\Theta(g)$.

The paper is organized as follows. In Section 2, we introduce a hypergraph
covering problem which we will use to show Theorem 2 and Theorem 3 are best
possible. We prove Theorem 2 and Theorem 3 in Section 3 and Section 4
respectively.

##  2 Hypergraph Covering Problems

In this section, we relate the problem in Theorem 2 and Theorem 3 to that of a
covering problem of a particular hypergraph. We first define the corresponding
collection of set families.

######  Definition 1.

Let $\mathcal{A}_{j}=\\{A_{j,i}:1\leq i\leq m\\}$ for $j\in[k]$. Then
$(\mathcal{A}_{1},\mathcal{A}_{2},\ldots,\mathcal{A}_{k})$ forms a Bollobás
set $(k,t)$-tuple modulo $2$ if

$|\bigcap\limits_{i=1}^{k}A_{j,i_{j}}|=0\pmod{2}\iff|\\{i_{1},\ldots,i_{k}\\}|<t.$

Let $b_{k,t}(n)$ be the size of the largest Bollobás set $(k,t)$-tuple modulo
$2$ with ground set $[n]$.

In the setting where $k=t=2$, we refer to a Bollobás set $(2,2)$-tuple modulo
$2$ as a Bollobás set pair modulo $2$. Using the language of Definition 1,
Theorem 2 and Theorem 3 say $b_{k,k}(n)=\Theta(n^{1/\lfloor k/2\rfloor})$ and
$b_{k,t}(n)=\Theta(n^{1/(t-1)})$ respectively as one may add an auxiliary
element to each set in each family to interchange the parity of the sets and
their corresponding intersections. In order to determine of the asymptotics of
$b_{k,t}(n)$, we consider the following related hypergraph covering problem:

######  Definition 2.

Let $H\subseteq\binom{[n]}{k}$. A modulo $2$ cover of $H$ is a collection of
complete $k$-partite $k$-graphs which cover each edge of $H$ an odd number of
times and each non-edge an even number of times. We denote the minimum size of
a modulo $2$ cover of $H$ by $f^{\prime}_{k}(H)$.

Setting $X_{i}=\\{x_{i,j}:j\in[n]\\}$ for $i\in[k]$, let $H_{k,t}(n)$ be the
subhypergraph of $\prod_{i\in[k]}X_{i}$ consisting of hyperedges
$\\{x_{1,i_{1}},x_{2,i_{2}},\dots,x_{k,i_{k}}\\}$ such that at least $t$ of
the indices $i_{1},i_{2},\dots,i_{k}$ are distinct. Then there is a one to one
correspondence between a modulo $2$ cover of $H_{k,t}(n)$ with $m$ complete
$k$-partite $k$-graphs and a Bollobás set $(k,t)$-tuple modulo $2$ consisting
of subsets of $[m]$. Hence,

$f_{k,t}(n):=f^{\prime}_{k}(H_{k,t}(n))=\min\\{m:b_{k,t}(m)\geq n\\}.$ (2)

The problem in Definition 2 is closely related to the hypergraph extension of
the Graham-Pollak [10] problem. Given a hypergraph $H\subseteq\binom{[n]}{k}$,
let $f_{k}(H)$ denote minimum number of complete $k$-partite $k$-graphs needed
to cover each edge of $H$ exactly once and let
$f_{k}(n)=f_{k}(\binom{[n]}{k})$.

Graham and Pollak [10] proved for all $n\geq 1$, $f_{2}(n)=n-1$. Alon [2]
proved that $f_{3}(n)=n-2$ for $n\geq 2$ and proved that
$f_{k}(n)=\Theta(n^{\lfloor k/2\rfloor})$. Relating the problem to that of a
minimal biclique cover of the Kneser graph $K_{n:k}$, Cioabă et al. [5]
improved the bounds on $f_{k}(n)$ to:

$\frac{2\binom{n-1}{k}}{\binom{2k}{k}}\leq f_{2k}(n)\leq\binom{n-k}{k}.$ (3)

Currently Leader, Milićević, and Tan [11] have the best general bounds. A key
ingredient in our proof of Theorem 2 is to similarly relate this hypergraph
covering problem to a graph covering problem as in Cioabă et al. [5]. To this
end, define the ordered Kneser graph $OK_{n:k}$ as follows:

$\displaystyle V(OK_{n:k})$ $\displaystyle=$
$\displaystyle\\{(i_{1},i_{2},\ldots,i_{k}):\\{i_{1},\ldots,i_{k}\\}\in\binom{[n]}{k}\\}$
$\displaystyle E(OK_{n:k})$ $\displaystyle=$
$\displaystyle\\{((i_{1},\ldots,i_{k}),(j_{1},\ldots,j_{k})):\\{i_{1},\ldots,i_{k}\\}\cap\\{j_{1},\ldots,j_{k}\\}=\emptyset\\}.$

The following lemma relates modulo $2$ covers of $H_{2k,2k}(n)$ and biclique
covers of $OK_{n:k}$.

######  Lemma 4.

Let $\\{\mathcal{C}_{i}:i\in[t]\\}$ be a modulo $2$ cover of $H_{2k,2k}(n)$.
Then, there exists a modulo $2$ biclique cover
$\\{\mathcal{C}_{i}^{\prime}:i\in[t]\\}$ of $OK_{n:k}$ and in particular
$f_{2k,2k}(n)\geq f^{\prime}_{2}(OK_{n:k})$.

###### Proof.

For each complete $2k$-partite $2k$-graph
$\mathcal{C}_{i}:=\prod_{j=1}^{2k}X_{i,j}$ in a modulo $2$ cover of
$H_{2k,2k}(n)$, define the complete bipartite graph $\mathcal{C}_{i}^{\prime}$
with parts $\prod_{j=1}^{k}X_{i,j}\cap V(OK_{n:k})$, and
$\prod_{j=k+1}^{2k}X_{i,j}\cap V(OK_{n:k})$.

Observe that $\\{\mathcal{C}_{i}^{\prime}\\}$ is a modulo $2$ biclique cover
of $OK_{n:k}$. $\Box$

Our next lemma shows a connection between the $k$-graphs $H_{k,k}(n)$ and
$\binom{[n]}{k}$.

######  Lemma 5.

Let $k\geq 2$. Then $f_{k}(H_{k,k}(n))\leq k!f_{k}(n)$.

###### Proof.

Let $m=f_{k}(n)$ and $\\{\mathcal{C}_{i}:i\in[m]\\}$ be such a minimal
$k$-partite, $k$-uniform cover of $\binom{[n]}{k}$. Then, given
$\mathcal{C}_{i}=\prod_{i\in[k]}X_{i}$ and a bijection $\pi:[k]\to[k]$, define

$\mathcal{C}_{i,\pi}=\prod_{i\in[k]}X_{\pi(i)}\subset H_{k,k}(n).$

It then follows that $\\{\mathcal{C}_{i,\pi}\\}$ forms a decomposition of
$H_{k,k}(n)$ and thus implies the bound. $\Box$

##  3 Proof of Theorem 2

### 3.1 The case $k=2$

In the setting where $t=k=2$, it is straightforward to show:

######  Proposition 1.

For all $n\geq 1$,

$f_{2,2}(n)=\begin{cases}n&n\text{ is odd}\\\ n-1&n\text{ is even}\\\
\end{cases}$

###### Proof.

As a result of (2), it suffices to show $b_{2,2}(n)=n+1$ for $n$ even and
$b_{2,2}(n)=n$ for $n$ odd.

For $n$ even, and $i\in[n]$ consider $A_{i}=\\{i\\}$ with $B_{i}=\\{i\\}^{c}$
and $B_{n+1}=A_{n+1}=[n]$. This is a Bollobás set pair modulo $2$ of size
$n+1$ and thus $b_{2,2}(n)=n+1$ for even $n$ by the bounds in (1).

For $n$ odd, let $m=b_{2,2}(n)$ and $(\mathcal{A},\mathcal{B})$ be a Bollobás
set pair modulo $2$ of size $m$. If $\\{v_{A_{i}}:A_{i}\in\mathcal{A}\\}$ is
linearly independent in $\mathbb{F}_{2}^{n}$, then $m\leq n$. Thus, we may
assume that there exists a non-trivial solution to
$\sum_{i=1}^{m}\epsilon_{i}v_{A_{i}}=0$ in $\mathbb{F}_{2}^{n}$. For all
$j\in[m]$, it follows that

$0=\bigg{\langle}\sum_{i=1}^{m}\epsilon_{i}v_{A_{i}},v_{B_{j}}\bigg{\rangle}=\sum_{\epsilon_{i}=1;i\neq
j}\langle v_{A_{i}},v_{B_{j}}\rangle=\sum_{\epsilon_{i}=1;i\neq j}|A_{i}\cap
B_{j}|=|\\{i:\epsilon_{i}=1,i\neq j\\}|\pmod{2}.$

Since this is true for all $j\in[m]$, the existence of one non-zero
$\epsilon_{i}$ implies they are all equal to one. In particular, $(m-1)$ is
even and hence $m\in\\{n,n+1\\}$ is odd and thus $m=n$. $\Box$

### 3.2 The case $k\geq 3$

In this section, we will prove that

$\displaystyle\Bigl{(}\frac{1}{2}+o(1)\Bigr{)}\binom{n}{k}$
$\displaystyle\leq$ $\displaystyle f_{2k,2k}(n)\leq(2k)!\binom{n}{k}$ (4)
$\displaystyle\Bigl{(}\frac{1}{2}+o(1)\Bigr{)}\binom{n}{k-1}$
$\displaystyle\leq$ $\displaystyle f_{2k-1,2k-1}(n)\leq(2k-1)!\binom{n}{k-1}$
(5)

which imply Theorem 2 by (2) and that the bound in the theorem is the correct
order of magnitude. Using Lemma 5 with the upper bound in (3), we recover the
upper bounds in (4) and (5).

Next, by considering the link hypergraph of a vertex, it follows that
$f_{k,k}(n)\geq f_{k-1,k-1}(n-1)$ and hence the lower bound in (5) follows by
the corresponding lower bound in (4). As such, it suffices to prove the lower
bound in (4).

To this end, let $\\{\mathcal{C}_{i}:i\in[t]\\}$ be a modulo $2$ cover of
$H_{2k,2k}(n)$ with $t=f_{2k,2k}(n)$. Lemma 4 then yields that $t\geq
f^{\prime}_{2}(OK_{n:k})$ and as such we will prove a lower bound on
$f^{\prime}_{2}(OK_{n:k})$.

As the adjacency matrix of each biclique has rank at most $2$, the
subadditivity of matrix rank and taking the minor of $OK_{n:k}$ which
corresponds to the Kneser graph $K_{n:k}$ give

$f^{\prime}_{2}(OK_{n:k})\geq\frac{1}{2}\text{rank}(A(OK_{n:k}))\geq\frac{1}{2}\text{rank}(A(K_{n:k}))$
(6)

where the rank of the matrices is over $\mathbb{F}_{2}$. Let
$M_{n,k,l}\in\\{0,1\\}^{\binom{n}{k}\times\binom{n}{l}}$ where the $(K,L)$
entry for $K\in\binom{[n]}{k}$ and $L\in\binom{[n]}{l}$ is the indicator of
$K\subseteq L$ and note that $M_{n,k,n-k}=A(K_{n:k})$.

Wilson [14, Theorem 1] determined the rank for matrices $M_{n,k,l}$ over
$\mathbb{F}_{p}$ for $k\leq\min\\{l,n-l\\}$:

$\text{rank}(M_{n,k,l})=\sum_{i:\;p\nmid\binom{n-k-i}{k-i}}\binom{n}{i}-\binom{n}{i-1}.$
(7)

Since the corresponding binomial coefficients when $i\in[k-3,k]$ are odd when
$n-2k=24\pmod{36}$, applying (7) when $p=2$ gives the following for the rank
over $\mathbb{F}_{2}$:

$\text{rank}(A(K_{n:k}))\geq\binom{n}{k}-\binom{n}{k-4}.$ (8)

Hence, standard binomial estimates and using (6) and (8) give

$f_{2k,2k}(n)\geq
f^{\prime}_{2}(OK_{n:k})\geq\Bigl{(}\frac{1}{2}+o(1)\Bigr{)}\binom{n}{k}.$

Taking the bounds from (4) and (5) and noting in (2) that
$f_{k,k}(n)=\min\\{m:b_{k,k}(m)\geq n\\}$, we recover the following bounds on
$b_{k,k}(n)$:

$\displaystyle\Bigl{(}\frac{1}{2k}+o(1)\Bigr{)}n^{\frac{1}{k}}$
$\displaystyle\leq$ $\displaystyle
b_{2k,2k}(n)\leq\Bigl{(}k2^{\frac{1}{k}}\Bigr{)}n^{\frac{1}{k}}$
$\displaystyle\Bigl{(}\frac{1}{2k^{2}}+o(1)\Bigr{)}n^{\frac{1}{k-1}}$
$\displaystyle\leq$ $\displaystyle
b_{2k-1,2k-1}(n)\leq\Bigl{(}(k-1)2^{\frac{1}{k-1}}+o(1)\Bigr{)}n^{\frac{1}{k-1}}.$

##  4 Proof of Theorem 3

In this section, we will prove that if $2t-2\leq k$, then

$f_{k,t}(n)\leq\Bigl{(}\frac{t^{k}}{t!}+o(1)\Bigr{)}n^{t-1}\hskip
8.53581pt\text{and}\hskip
8.53581ptb_{k,t}(n)\leq\Bigl{(}t-1+o(1)\Bigr{)}n^{\frac{1}{t-1}}.$ (9)

Since $f_{k,t}(n)=\min\\{m:b_{k,t}(m)\geq n\\}$, the upper bound on
$f_{k,t}(n)$ in (9) implies a lower bound on $b_{k,t}(n)$ which together with
the upper bound on $b_{k,t}(n)$ in (9) proves Theorem 3 as they imply

$\Bigl{(}\Bigl{(}\frac{t!}{t^{k}}\Bigr{)}^{\frac{1}{t-1}}+o(1)\Bigr{)}n^{\frac{1}{t-1}}\leq
b_{k,t}(n)\leq\Bigl{(}t-1+o(1)\Bigr{)}n^{\frac{1}{t-1}}.$

### 4.1 Upper bound on $f_{k,t}(n)$

Let $\phi:H_{k,t}(n)\to\\{\pi:|\pi|\geq t\\}$ be the correspondence of an edge
of $H_{k,t}(n)$ to a set partition of $[k]$ where each part consists of the
coordinates with equal indices. For a set partition $\pi$ of $[k]$, define
$H_{k,t}^{\pi}(n)=\\{e\in H_{k,t}(n):\phi(e)=\pi\\}$ so that

$H_{k,t}(n)=\bigsqcup\limits_{|\pi|\geq t}H_{k,t}^{\pi}(n).$ (10)

It follows that
$f^{\prime}_{k}(H_{k,t}^{\pi}(n))\leq(n)_{(|\pi|-1)}=n(n-1)\cdots(n-|\pi|-2)$
by taking complete $k$-partite $k$-graphs corresponding to choosing a distinct
singleton for the parts corresponding to $|\pi|-1$ of the parts and taking the
remaining parts to be all of the remaining $(n-|\pi|+1)$ vertices. Moreover,
adding the complete $k$-partite $k$-graph $[n]^{k}$ to a minimal cover, it
follows that

$f_{k,t}(n)\leq 1+f^{\prime}_{k}([n]^{k}\setminus H_{k,t}(n)).$ (11)

Since $f^{\prime}_{k}(\cdot)$ is subadditive with respect to disjoint unions,
using (10) gives

$f^{\prime}_{k}([n]^{k}\setminus H_{k,t}(n))\leq\sum_{|\pi|\leq
t-1}f^{\prime}_{k}(H_{k,t}^{\pi}(n))\\\ \leq\sum_{|\pi|\leq
t-1}(n)_{(|\pi|-1)}=(S(k,t)+o(1))n^{t-1}$ (12)

where $S(k,t)$ is the Stirling number of the second kind. We then recover the
upper bound on $f_{k,t}(n)$ in (9) by using the bound $S(k,t)\leq t^{k}/t!$
together with (11) and (12).

### 4.2 Upper bound on $b_{k,t}(n)$

We first prove the following lemma which relates $b_{k,t}(n)$ to $b_{2,2}(n)$.

######  Lemma 6.

Given $n\geq 1$, let $\alpha=\alpha(k,t)=2t-k+2$. Then letting $m=b_{k,t}(n)$,

$b_{2,2}(n)\geq\begin{cases}{m\choose t-1}\hskip 15.0pt\text{if}\hskip
5.0pt2t-2\leq k\vspace{1mm}\\\ {m-\alpha\choose k-t+1}\hskip
15.0pt\text{if}\hskip 5.0pt2t-2>k\\\ \end{cases}$

In particular, both quantities are less than or equal to $n+1$ by (1).

###### Proof.

Let $m=b_{k,t}(n)$ for $2t-2\leq k$ and let
$(\mathcal{A}_{1},\ldots,\mathcal{A}_{k})$ be a Bollobás set $(k,t)$-tuple
modulo $2$ of size $m$ where
$\mathcal{A}_{i}=\\{A_{j,i}\subseteq[n]:i\in[m]\\}$ for all $j\in[k]$. For
each $I=\\{i_{1}<\cdots<i_{t-1}\\}\in\binom{[m]}{t-1}$, define the families
$\mathcal{A}:=\\{A_{I}\\}$ and $\mathcal{B}:=\\{B_{I}\\}$ where:

$\displaystyle A_{I}$ $\displaystyle:=$ $\displaystyle
A_{1,i_{1}}\cap\cdots\cap A_{t-1,i_{t-1}}$ $\displaystyle B_{I}$
$\displaystyle:=$ $\displaystyle A_{t,i_{1}}\cap\cdots\cap A_{2t-2,i_{t-1}}$

Note that $(\mathcal{A},\mathcal{B})$ is a Bollobás set pair modulo $2$ and
hence the result follows.

Similarly, for $2t-2>k$, let $m=b_{k,t}(n)$ and let
$(\mathcal{A}_{1},\ldots,\mathcal{A}_{k})$ be a Bollobás set $(k,t)$-tuple
modulo $2$ of size $m$ where
$\mathcal{A}_{i}:=\\{A_{j,i}\subseteq[n]:i\in[m]\\}$ for all $j\in[k]$.
Consider the index set

$\mathcal{F}:=\binom{[\alpha+1,m]}{k-t+1}.$

For $I=\\{i_{1}<\cdots<i_{k-t+1}\\}\in\mathcal{F}$, define the families
$\mathcal{A}:=\\{A_{I}\\}$ and $\mathcal{B}:=\\{B_{I}\\}$ where

$\displaystyle A_{I}$ $\displaystyle:=$ $\displaystyle A_{1,1}\cap\cdots\cap
A_{\alpha,\alpha}\cap A_{\alpha+1,i_{1}}\cap\cdots\cap A_{t-1,i_{k-t+1}}$
$\displaystyle B_{I}$ $\displaystyle:=$ $\displaystyle
A_{k-t+2,i_{1}}\cap\cdots\cap A_{k,i_{t-1}}.$

Note that $(\mathcal{A},\mathcal{B})$ is a Bollobás set pair modulo $2$ and
hence the result follows. $\Box$

We are now able to prove the upper bound on $b_{k,t}(n)$ in (9) when $2t-2\leq
k$. Letting $m=b_{k,t}(n)$, Lemma 6 yields that ${m\choose t-1}\leq n+1$.
Using the bound ${m\choose t-1}\geq(m/(t-1))^{t-1}$, it follows that

$m\leq\Bigl{(}t-1+o(1)\Bigr{)}n^{\frac{1}{t-1}}.$

##  5 Concluding Remarks

$\bullet$ Conjecture 2 involves extending Theorem 2 to primes $p>2$. For
$k\geq 3$, and $p=2$, we used a hypergraph extension of the Graham-Pollak
theorem [10] to show that Theorem 2 is best possible. For $p>2$, a promising
approach seems to be a hypergraph extension of Alon’s [1] result for bipartite
coverings of order $\ell$ of the complete graph. To this end, for an integer
$\ell\geq 1$, we say complete $k$-partite $k$-graphs $H_{1},\ldots,H_{m}$ form
a $k$-partite covering of order $\ell$ of $\binom{[n]}{k}$ if each edge of
$\binom{[n]}{k}$ lies in at least one and at most $\ell$ of the
$H_{1},\ldots,H_{m}$. The following conjecture would show that Conjecture 2 is
best possible:

######  Conjecture 3.

Let $k\geq 2$ and $\ell\geq 1$. Let $H_{1},\ldots,H_{m}$ be complete
$k$-partite $k$-graphs which form a $k$-partite covering of order $\ell$ of
$\binom{[n]}{k}$ of minimum size. Then $m=\Theta(n^{\lfloor
k/2\rfloor/\ell})$.

$\bullet$ In this paper, we used a result of Wilson [14] on the rank over
$\mathbb{F}_{2}$ of an incidence matrix to prove Theorem 2. To apply this same
argument for general primes $p$ in Conjecture 2, one would need to replace the
entries which correspond to incidences with any nonzero entry of
$\mathbb{F}_{p}$. For $p=2$, it follows that this corresponds to the classical
$\\{0,1\\}$ incidence matrix. A positive solution to the following problem
would imply Conjecture 2:

######  Problem 1.

Let $k\geq 2$ and $p$ be prime. Let $M^{\star}_{n,k,n-k}$ be any
$\binom{n}{k}\times\binom{n}{n-k}$ matrix with entries in $\mathbb{F}_{p}$
where the $(K,L)$ entry for $K\in\binom{[n]}{k}$ and $L\in\binom{[n]}{n-k}$ is
a nonzero element of $\mathbb{F}_{p}$ if $K\subseteq L$ and is zero otherwise.
Prove that $\text{rank}(M^{\star}_{n,k,n-k})=\Omega(n^{k/(p-1)})$ where the
rank is over $\mathbb{F}_{p}$.

$\bullet$ In this paper, we prove bounds on $f_{k,t}(n)$ to prove Theorem 2
and 3. These bounds imply

$\displaystyle\frac{1}{2(\lfloor k/2\rfloor!)}$ $\displaystyle\leq$
$\displaystyle\lim_{n\to\infty}\frac{f_{k,k}(n)}{n^{\lfloor
k/2\rfloor}}\leq(k)_{\lceil k/2\rceil}$ (13)
$\displaystyle\frac{1}{(t-1)^{t-1}}$ $\displaystyle\leq$
$\displaystyle\lim_{n\to\infty}\frac{f_{k,t}(n)}{n^{t-1}}\leq\frac{t^{k}}{k!}$
(14)

where we let $(k)_{r}=k(k-1)\cdots(k-r+1)$ denote the falling factorial and
assume that $2t-2\leq k$ in (14). We believe that the upper bound in (13)
might be closer to the truth. It is likely that determining the limiting value
is challenging as the problem is related to the hypergraph extension of the
Graham-Pollak problem for which asymptotically tight bounds are not known. We
also believe that the upper bound in (14) is closer to the truth.

$\bullet$ In this paper, we determined the order of magnitude for $b_{k,t}(n)$
in the case when $k=t$ and in the case when $2t-2\leq k$. For small values of
$t$ and $k$, more delicate arguments give better bounds. First, when $t=2$ and
$k\geq 2$ it is straightforward to see $n-1\leq b_{k,2}(n)\leq b_{2,2}(n)$ for
all $n\geq 1$.

Although the asymptotics of the largest Bollobás $(3,3)$-tuple222the sizes of
the intersections are zero and nonzero accordingly as opposed to zero and
nonzero modulo $2$ and the largest Bollobás $(4,3)$-tuple11footnotemark: 1 are
wide open (see [12]), in the modulo $2$ setting we are able to show:

$\displaystyle\frac{n-1}{3}$ $\displaystyle\leq$ $\displaystyle b_{3,3}(n)\leq
n+2$ (15) $\displaystyle\frac{\sqrt{3n+1}-2}{3}$ $\displaystyle\leq$
$\displaystyle b_{4,3}(n)\leq\sqrt{2n+2}+4.$ (16)

We start by sketching the proofs of the lower bounds in (15) and (16) by
proving upper bounds on $f_{3,3}(n)$ and $f_{4,3}(n)$ and using (2). For
$f_{3,3}(n)$, a modulo $2$ cover of $H_{3,3}(n)$ is given by
$\\{i\\}\times\\{i\\}\times[n]$, $\\{i\\}\times[n]\times\\{i\\}$, and
$[n]\times\\{i\\}\times\\{i\\}$ for any index $i\in[n]$ together with
$[n]^{3}$. Hence $f_{3,3}(n)\leq 3n+1$. For $f_{4,3}(n)$, a similar
construction gives $f_{4,3}(n)\leq f_{4,2}(n)+3n(n-1)+6n$. It is
straightforward to see $f_{4,2}(n)\leq n+1$ and hence $f_{4,3}(n)\leq
n+1+3n(n-1)+6n=3n^{2}+4n+1$.

We next sketch the proofs of the upper bounds in (15) and (16). The upper
bound on $b_{4,3}(n)$ follows from Lemma 6. For the upper bound on
$b_{3,3}(n)$, consider any Bollobás set triple modulo $2$ denoted by
$(\mathcal{A}_{1},\mathcal{A}_{2},\mathcal{A}_{3})$ where
$\mathcal{A}_{j}:=\\{A_{j,i}\subseteq[n]:i\in[m]\\}$ and define
$\mathcal{F}_{1}=\\{A_{1,1}\cap A_{2,i}:2\leq i\leq m\\}$ and
$\mathcal{F}_{2}=\\{A_{1,1}\cap A_{3,i}:2\leq i\leq m\\}.$ It then follows
that $(\mathcal{F}_{1},\mathcal{F}_{2})$ is a Bollobás set pair modulo $2$.

$\bullet$ Conjecture 1 involves determining the order of magnitude of
$b_{k,t}(n)$ when $2t-2>k$. Theorem 2 verifies Conjecture 1 when $t=k$. When
$(k,t)=(5,4)$, we can use a similar argument as in the upper bound in (15) to
show that $b_{5,4}(n)-1\leq b_{4,3}(n)$. Using Lemma 6 and the upper bound in
(16), it then follows that $b_{5,4}(n)=\Theta(n^{1/2})$. This verifies
Conjecture 1 in the case where $(k,t)=(5,4)$. In general, Lemma 6 gives
$b_{k,t}(n)=O(n^{1/(k-t+1)})$ and a more delicate argument similar to Lemma 5
together with (2) gives a construction of size $\Theta(n^{1/\lfloor
k/2\rfloor})$. The first open case is $(k,t)=(6,5)$ for which
$b_{6,5}(n)=\Omega(n^{1/3})$ and $b_{6,5}(n)=O(n^{1/2})$.

## References

  * [1] N. Alon, Neighborly Families of Boxes and Bipartite coverings, In: Graham R., Nes̆etr̆il J., Butler S. (eds) The Mathematics of Paul Erdős II. Springer, New York, NY, 2013.
  * [2] N. Alon, Decomposition of the Complete $r$-Graph into Complete $r$-Partite $r$-Graphs, Graphs and Combinatorics 2, 95-100, 1986.
  * [3] L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics, Preliminary Version 2, Department of Computer Science, The University of Chicago, 1992.
  * [4] E. R. Berlekamp, On subsets with intersections of even cardinality, Canad. Math. Bull, Vol. 12 (4), pp. 471–477, 1969.
  * [5] S. Cioabă, A. Kündgen,J. Verstraëte, On decompositions of complete hypergraphs, Journal of Combin. Ser. A, 1232–1234, 2009.
  * [6] M. Deza, P.Frankl, N.M. Singhi, On functions of strength $t$, Combinatorica, 3, 331–339, 1983.
  * [7] P. Frankl, N. Tokushige, Extremal problems for finite sets, American Mathematical Soc., 2018.
  * [8] Z. Füredi, B. Sudakov, Extremal set systems with restricted $k$-wise intersections, J. Combin. Theory Ser. A, 105(1), 143–159, 2004.
  * [9] V. Grolmusz, B. Sudakov, On $k$-wise set-intersections and $k$-wise hamming-distances, J. Combin.Theory Ser. A 99, 180–190, 2002.
  * [10] R. L. Graham and H. O. Pollak. On embedding graphs in squashed cubes. In: Graph Theory and Appl., Springer Lecture Notes in Math. 303, 99–110, 1972.
  * [11] I. Leader, L. Milićević, and T. S. Tan, Decomposing the complete $r$-graph, J. Combin.Theory Ser. A, 154:21–31, 2018.
  * [12] J. O’Neill, J. Verstraëte, A generalization of the Bollobás set pairs inequality, arxiv, 2018.
  * [13] T. Szabó and V. Vu Exact $k$-wise intersection theorems, Graphs and Combinatorics, Vol. 21 (2), 247–261, 2005.
  * [14] R. Wilson, A Diagonal Form for the Incidence Matrices of $t$-Subsets vs. $k$-Subsets, Europ. J. Combinatorics, 11, 609–615, 1990.