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.
The first 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,
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.
Finally, 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 generalisation 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).