Given a hypergraph $\mathcal{H}$ with vertex set $[n]:={1,\ldots,n}$, a bisecting family is a family $\mathcal{A}\subseteq\mathcal{P}([n])$ such that for every $B\in\mathcal{H}$, there exists $A\in\mathcal{A}$ with the property $|A\cap B|-|A\cap\overline{B}|\in{-1,0,1}$. Similarly, for a family of bicolorings $\mathcal{B}\subseteq {-1,1}^{[n]}$ of $[n]$ a family $\mathcal{A}\subseteq\mathcal{P}([n])$ is called a System of Unbiased Representatives for $\mathcal{B}$ if for every $b\in\mathcal{B}$ there exists $A\in\mathcal{A}$ such that $\sum_{x\in A} b(x) =0$.

The problem of optimal families of bisections and bicolorings for hypergraphs originates from what is referred to as the problem of Balancing Sets of vectors, and has been the source for a few interesting extremal problems in combinatorial set theory for about 3 decades now. We shall consider certain natural extremal functions that arise from the study of bisections and bicolorings and bounds for these extremal functions. Many of the proofs involve the use of polynomial methods (not the Polynomial Method, though!).

(Joint work with Rogers Mathew, Tapas Mishra, and Sudebkumar Prasant Pal.)

- All seminars.
- Seminars for 2019

Last updated: 24 Jun 2024