Open Problems

This webpage is experimental. Let's see whether it turns out to be a good idea in a few years.

This page lists a few open problems that I encounter at some time, and which I think are interesting enough for me to share on a webpage. And:

These problems seem beyond my expertise, and currently I don't have any idea on how to make progress in them.
As far as I know, there are relatively few literature on these problems. (But in some cases I just didn't find the right paper…)
By putting them at this page doesn't mean I encourage you to solve (nor discourage you from solving) them.
Please feel free to drop me an email if you find or make some progress on them!

Covering a clique by smaller cliques

Given positive integers \(m>n\), e.g. \(m=2,000\) and \(n=500\), what is the smallest number of cliques \(K_n\) that are needed to cover the edges of \(K_m\)?
Equivalently, we have \(m\) people, and we want to create groups over these people. Each group should have size exactly \(n\), and any two people should be in some common group. How many group at minimum should we create?
Source: see a tweet of mine.
See also this mathoverflow question. I suspect this problem is very difficult.

Deterministic construction of \((x,y)\)-families

Let \(x,y\) be small integers, and \({\cal U}\) be a universe of \(n\) elements. A collection of subsets \({\cal S}\) of \({\cal U}\) is an \((x,y)\)-family if for every \(X,Y\subseteq {\cal U}\) where \(|X|=x,|Y|=y\) and \(X\cap Y=\varnothing\), there is a set \(S\in{\cal S}\) such that \(X\subseteq S\) and \(Y\cap S=\varnothing\).
Let \(q=O\hspace{-2pt}\left(\frac{(x+y)^{x+y+1}}{x^xy^y}\log n\right)\), then there are \((x,y)\)-families of size \(q\). Actually, consider a subset \(S\) of \({\cal U}\) where every element is in \(S\) w.p. \(\frac{x}{x+y}\) independently. If we sample \(q\) such sets \(S_1,\dots,S_q\) and form a collection, then this collection is an \((x,y)\)-family with high probability.
The question is: Can we construct small \((x,y)\)-families deterministically? So it's essentially a derandomization question.
Motivation: Lemma 5.3 of [DGR’20]. Also see Theorem 2.1 of [DK’11].
I believe that the concept of \((x,y)\)-family could be very useful in algorithm design that tolerates multiple failures.

Update

Section 3 of this exciting paper constructs deterministically an \([n, x, y, \ell]\)-Hit and Miss Hash Family where \(\ell=O(xy)^{y+2}\log n\) (assuming \(y\le x\le \log n\)). In our terminology it is an \((x, y)\)-family of size \(2\ell\). In addition they derandomized many important fault-tolerant graph algorithms. Wow!