In this talk we shall see three very different areas of

applications of combinatorics in mathematics and computer science,

illustrating four different flavours of combinatorial reasoning.

 

First, we shall look at Haussler's Packing Lemma from Computational

Geometry and Machine Learning, for set systems of bounded VC dimension. We

shall go through its generalization to the Shallow Packing Lemma for

systems of shallow cell complexity, and see how it can be used to prove

the existence of small representations of set systems, such as epsilon

nets, M-nets, etc. Joint works with Arijit Ghosh (IMSc, Chennai), Nabil

Mustafa (ESIEE Paris), Bruno Jartoux (ESIEE Paris) and Esther Ezra

(Georgia Inst. Tech., Atlanta).

 

Next, we consider lower bounds on the maximum size of an

independent set, as well as the number of independent sets, in k-uniform

hypergraphs, together with an extension to the maximum size of a subgraph

of bounded degeneracy in a hypergraph. Joint works with C. R. Subramanian

(IMSc, Chennai), Dhruv Mubayi (UIC, Chicago) and Jeff Cooper (UIC,

Chicago) and Arijit Ghosh (IMSc Chennai).

 

The last problem is on the decomposition, into irreducible

representations, of the Weil representation of the full symplectic group

associated to a finite module of odd order over a Dedekind domain. We

shall discuss how a poset structure defined on the orbits of finite abelian p-groups under automorphisms can be used to show the decomposition of the Weil representation is multiplicity-free, as well as parametrize

the irreducible subrepresentations, compute their dimensions in terms of p, etc. Joint works with Amritanshu Prasad (IMSc, Chennai).