Algebra & Combinatorics Seminar

Title: Bisections and bicolorings of hypergraphs
Speaker: Niranjan Balachandran (IIT, Bombay)
Date: 30 January 2019
Time: 4 pm
Venue: LH-1, Mathematics Department

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.)


Contact: +91 (80) 2293 2711, +91 (80) 2293 2265 ;     E-mail: chair.math[at]iisc[dot]ac[dot]in
Last updated: 20 Aug 2019