IISc Alg Comb 2018-19

Algebra & Combinatorics Seminar

The Algebra & Combinatorics Seminar meets on Fridays from 3–4 pm, in Lecture Hall LH-1 of the IISc Mathematics Department. The organizers are Apoorva Khare and R. Venkatesh.

Hassain M. (IISc Mathematics) Jan 4, 2019
Representation growth of Special Compact Linear Groups of Order Two

Abstract. Let $\mathfrak{O}$ be the ring of integers of a non-Archimedean local field such that the residue field has characteristic $p$. Then the abscissa of convergence of representation zeta function of Special Linear group $\mathrm{SL}_2(\mathfrak{O})$ is $1.$ The case $p\neq 2$ is already known in the literature. For $p=2$ we need more tools to prove the result. In this talk I will discuss the difference between those cases and give an outline of the proof for $p=2.$

Let $\mathfrak{p}$ be the maximal ideal of $\mathfrak{O}$ and $|\mathfrak{O}/\mathfrak{p}|=q.$ It is already shown in literature that for $r \geq 1,$ the group algebras $\mathbb C[\mathrm{GL}_2(\mathfrak{O}/\mathfrak{p}^{r})]$ and $\mathbb C[\mathrm{GL}_2(\mathbb F_q[t]/(t^{r}))]$ are isomorphic. Also for $2\nmid q,$ the group algebras $\mathbb C[\mathrm{SL}_2(\mathfrak{O}/\mathfrak{p}^{r})]$ and $\mathbb C[\mathrm{SL}_2(\mathbb F_q[t]/(t^{r}))]$ are isomorphic. In this talk I will also show that if $2\mid q$ and $\mathrm{char}(\mathfrak{O})=0$ then, the group algebras, $\mathbb C[\mathrm{SL}_2(\mathfrak{O}/\mathfrak{p}^{2\ell})]$ and $\mathbb C[\mathrm{SL}_2(\mathbb F_q[t]/(t^{2\ell}))]$ are not isomorphic for $\ell > \mathrm{e}$, where $\mathrm{e}$ is the ramification index of $\mathfrak{O}.$

Apoorva Khare (IISc Mathematics) Jan 11, 2019
From word games to a Polymath project

Abstract. Consider the following three properties of a general group $G$:

1. Algebra: $G$ is abelian and torsion-free.
2. Analysis: $G$ is a metric space that admits a "norm", namely, a translation-invariant metric $d(.,.)$ satisfying: $d(1,g^n) = |n| d(1,g)$ for all $g \in G$ and integers $n$.
3. Geometry: $G$ admits a length function with "saturated" subadditivity for equal arguments: $\ell(g^2) = 2 \; \ell(g)$ for all $g \in G$.

While these properties may a priori seem different, in fact they turn out to be equivalent. The nontrivial implication amounts to saying that there does not exist a non-abelian group with a "norm".

We will discuss motivations from analysis, probability, and geometry; then the proof of the above equivalences; and if time permits, the logistics of how the problem was solved, via a PolyMath project that began on a blogpost of Terence Tao.
(Joint – as D.H.J. PolyMath – with Tobias Fritz, Siddhartha Gadgil, Pace Nielsen, Lior Silberman, and Terence Tao.)

Sanjay Ramassamy (École Normale Supériure, Paris, France) Jan 18, 2019
Extensions of partial cyclic orders, boustrophedons and polytopes (11 am – note: unusual time)

Abstract. While the enumeration of linear extensions of a given poset is a well-studied question, its cyclic counterpart (enumerating extensions to total cyclic orders of a given partial cyclic order) has been subject to very little investigation. In this talk I will introduce some classes of partial cyclic orders for which this enumeration problem is tractable. Some cases require the use of a multidimensional version of the classical boustrophedon construction (a.k.a. Seidel–Entringer–Arnold triangle). The integers arising from these enumerative questions also appear as the normalized volumes of certain polytopes.

This is partly joint work with Arvind Ayyer (Indian Institute of Science) and Matthieu Josuat-Vergès (Laboratoire d'Informatique Gaspard Monge / CNRS).

Ramesh Gangolli (University of Washington, Seattle, USA) Jan 18, 2019
Some unpublished work of Harish-Chandra
(speaking in / subsumed by the Eigenfunctions Seminar)

Niranjan Balachandran (IIT, Bombay) Jan 30, 2019
(note: two talks, unusual day+times)

Talk 1: The Polynomial Method in Combinatorics – Two illustrative theorems 2:30 pm

Abstract. Since Dvir proved the Finite Kakeya Conjecture in 2008, the Polynomial Method has become a new and powerful tool and a new paradigm for approaching extremal questions in combinatorics (and other areas too). We shall take a look at the main philosophical principle that underlies this method via two recent (2017) theorems. One is the upper bound for Cap-sets by Ellenberg–Gijswijt, and the other, a function field analogue of a theorem of Sarkozy, due to Ben Green.

Talk 2: Bisections and bicolorings of hypergraphs 4 pm

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

Ved Datar (IISc Mathematics) Feb 1, 2019
Positive mass theorem and the Yamabe problem
(speaking in the Eigenfunctions Seminar; no Alg–Comb today)

Mohan R. (Indian Statistical Institute, Bangalore) Feb 8, 2019
Leavitt path algebras of weighted Cayley graphs $C_n(S,w)$

Abstract. We say a unital ring $R$ has the Invariant Basis Number (IBN) property in case, for each pair of positive integers $i,j$ if the left $R$-modules $R^i$ and $R^j$ are isomorphic, then $i=j$. The first examples of non IBN rings were studied by William Leavitt in the 1950s and he defined (what are now known as) Leavitt algebras which are 'universal' with non IBN property. In 2004 the algebraic structures arising from directed (multi)graphs known as Leavitt path algebras (LPA for short) were initially developed as algebraic analogues of graph $C^*$ algebras. LPAs generalize a particular class of Leavitt algebras.
During the intervening decade, these algebras have attracted significant interest and attention, not only from ring theorists, but from analysts working in $C^*$-algebras, and symbolic dynamicists as well. The goal of this talk is to introduce the notion of Leavitt path algebras and to present some results on LPAs arising from weighted Cayley graphs of finite cyclic groups.

Nishad Kothari (University of Campinas, São Paulo, Brazil) Feb 13, 2019
Pfaffian Orientations and Conformal Minors (note: unusual day)

Abstract. Valiant (1979) showed that unless P = N P, there is no polynomial-time algorithm to compute the number of perfect matchings of a given graph – even if the input graph is bipartite. Earlier, the physicist Kasteleyn (1963) introduced the notion of a special type of orientation of a graph, and we refer to graphs that admit such an orientation as Pfaffian graphs. Kasteleyn showed that the number of perfect matchings is easy to compute if the input graph is Pfaffian, and he also proved that every planar graph is Pfaffian. The complete bipartite graph $K_{3,3}$ is the smallest graph that is not Pfaffian. In general, the problem of deciding whether a given graph is Pfaffian is not known to be in N P.

Special types of minors, known as conformal minors, play a key role in the theory of Pfaffian orientations. In particular, a graph is Pfaffian if and only if each of its conformal minors is Pfaffian. It was shown by Little (1975) that a bipartite graph $G$ is Pfaffian if and only if $G$ does not contain $K_{3,3}$ as a conformal minor (or, in other words, if and only if $G$ is $K_{3,3}$-free); this places the problem of deciding whether a bipartite graph is Pfaffian in co – N P. Several years later, a structural characterization of $K_{3,3}$-free bipartite graphs was obtained by Robertson, Seymour and Thomas (1999), and independently by McCuaig (2004), and this led to a polynomial-time algorithm for deciding whether a given bipartite graph is Pfaffian.

Norine and Thomas (2008) showed that, unlike the bipartite case, it is not possible to characterize all Pfaffian graphs by excluding a finite number of graphs as conformal minors. In light of everything that has been done so far, it would be interesting to even identify rich classes of Pfaffian graphs (that are nonplanar and nonbipartite).

Inspired by a theorem of Lovasz (1983), we took on the task of characterizing graphs that do not contain $K_4$ as a conformal minor – that is, $K_4$-free graphs. In a joint work with U. S. R. Murty (2016), we provided a structural characterization of planar $K_4$-free graphs. The problem of characterizing nonplanar $K_4$-free graphs is much harder, and we have evidence to believe that it is related to the problem of recognizing Pfaffian graphs. In particular, we conjecture that every graph that is $K_4$-free and $K_{3,3}$-free is also Pfaffian. The talk will be mostly self-contained. I will assume only basic knowledge of graph theory. For more details, see: https://onlinelibrary.wiley.com/doi/full/10.1002/jgt.21882.

Subhajit Ghosh (IISc Mathematics) Feb 15, 2019
Total Variation Cutoff for the Transpose top-$2$ with random shuffle

Abstract. We investigate the properties of a random walk on the alternating group $A_n$ generated by $3$-cycles of the form $(i,n-1,n)$ and $(i,n,n-1)$. We call this the transpose top-$2$ with random shuffle. We find the spectrum of the transition matrix for this shuffle. We mainly use the representation theory of alternating group. We show that the mixing time is of order $\left(n-\frac{3}{2}\right)\log n$ and prove that there is a total variation cutoff for this shuffle.

Samarpita Ray (IISc Mathematics) Feb 22, 2019
Cohomology of modules over H-categories and co-H-categories

Abstract. An ordinary ring may be expressed as a preadditive category with a single object. Accordingly, as introduced by B. Mitchel, an arbitrary small preadditive category may be understood as a "ring with several objects". In this respect, for a Hopf algebra H, an H-category will denote an "H-module algebra with several objects" and a co-H-category will denote an "H-comodule algebra with several objects". Modules over such Hopf categories were first considered by Cibils and Solotar. In this talk, we present a study of cohomology in such module categories.

In particular, we consider H-equivariant modules over a Hopf module category C as modules over the smash extension C#H. We construct Grothendieck spectral sequences for the cohomologies as well as the H-locally finite cohomologies of these objects. We also introduce relative (D,H)-Hopf modules over a Hopf comodule category D. These generalize relative (A,H)-Hopf modules over an H-comodule algebra A. We construct Grothendieck spectral sequences for their cohomologies by using their rational Hom objects and higher derived functors of coinvariants.

(Joint work with Abhishek Banerjee and Mamta Balodi.)

Parthanil Roy (Indian Statistical Institute, Bangalore) Mar 1, 2019
Continued fractions, Stein–Chen method and extreme value theory
(speaking in the Eigenfunctions Seminar; no Alg–Comb today)

Xavier Viennot (CNRS and LaBRI, France) Mar 7, 2019
A survey of the combinatorial theory of orthogonal polynomials and continued fractions (2:15 pm – note: unusual time and day)

Abstract. The theory of orthogonal polynomials started with analytic continued fractions going back to Euler, Gauss, Jacobi, Stieltjes... The combinatorial interpretations started in the late 70's and is an active research domain. I will give the basis of the theory interpreting the moments of general (formal) orthogonal polynomials, Jacobi continued fractions and Hankel determinants with some families of weighted paths. In a second part I will give some examples of interpretations of classical orthogonal polynomials and of their moments (Hermite, Laguerre, Jacobi, ...) with their connection to theoretical physics.

Xavier Viennot (CNRS and LaBRI, France) Mar 8, 2019
Laguerre heaps of segments for the PASEP

Abstract. The PASEP (partially asymmetric exclusion process) is a toy model in the physics of dynamical systems strongly related to the moments of some classical orthogonal polynomials (Hermite, Laguerre, Askey–Wilson). The partition function has been interpreted with various combinatorial objects such as permutations, alternative and tree-like tableaux, etc. We introduce a new one called "Laguerre heaps of segments", which seems to play a central role in the network of bijections relating all these interpretations.

Ravi A. Rao (TIFR, Bombay) Mar 13, 2019
Talk 1: Suslin completion and set-theoretic complete intersections (note: unusual day)

Abstract. We describe how a completion of the factorial row by Suslin led to showing some ideals in a polynomial ring are set-theoretic complete intersections.

Ravi A. Rao (TIFR, Bombay) Mar 15, 2019
Talk 2: The study of projective modules over an affine algebra (2:30 pm – note: unusual time)

Abstract. The study of projective modules along the lines initiated by J.-P. Serre, H. Bass is outlined; the impetus given by A. Suslin in that direction is described, and recent progress made along the vision of A. Suslin on it by Fasel–Rao–Swan is shared briefly.

Soumya Bhattacharya (IISER Kolkata) Mar 20, 2019
Finiteness results on a certain class of modular forms and applications (note: unusual day)

Abstract. 'Holomorphic eta quotients' are certain explicit classical modular forms on suitable Hecke subgroups of the full modular group. We call a holomorphic eta quotient $f$ 'reducible' if for some holomorphic eta quotient $g$ (other than $1$ and $f$), the eta quotient $f/g$ is holomorphic. An eta quotient or a modular form in general has two parameters: weight and level. We shall show that for any positive integer $N$, there are only finitely many irreducible holomorphic eta quotients of level $N$. In particular, the weights of such eta quotients are bounded above by a function of $N$. We shall provide such an explicit upper bound. This is an analog of a conjecture of Zagier which says that for any positive integer $k$, there are only finitely many irreducible holomorphic eta quotients of weight $k/2$ which are not integral rescalings of some other eta quotients. This conjecture was established in 1991 by Mersmann. We shall sketch a short proof of Mersmann's theorem and we shall show that these results have their applications in factorizing holomorphic eta quotient. In particular, due to Zagier and Mersmann's work, holomorphic eta quotients of weight $1/2$ have been completely classified. We shall see some applications of this classification and we shall discuss a few seemingly accessible yet longstanding open problems about eta quotients.

This talk will be suitable also for non-experts: We shall define all the relevant terms and we shall clearly state the classical results which we use.

In-House Symposium Mar 28–29, 2019
(no Alg–Comb today)

Sudip Bera (IISc Mathematics) Apr 5, 2019

Abstract. TBA

Apoorva Khare and Gautam Bharali (IISc Mathematics) Apr 12, 2019
(speaking in the Eigenfunctions Seminar; no Alg–Comb today)

Apoorva Khare (IISc Mathematics) Sep 7, 2018
The Diamond Lemma in ring theory

Abstract. I will give a gentle introduction to the Diamond Lemma. This is a useful technique to prove that certain "PBW-type" bases exist of algebras given by generators and relations. In particular, we will see the PBW theorem for usual Lie algebras.

R. Venkatesh (IISc Mathematics) Sep 14, 2018
Graphs vs. Lie algebras

Abstract. Let $G$ be a finite simple graph. The Lie algebra $\mathfrak{g}$ of $G$ is defined as follows: $\mathfrak{g}$ is generated by the vertices of $G$ modulo the relations $[u, v]=0$ if there is no edge between the vertices $u$ and $v$. Many properties of $\mathfrak{g}$ can be obtained from the properties of $G$ and vice versa. The Lie algebra $\mathfrak{g}$ of $G$ is naturally graded and the graded dimensions of the Lie algebra $\mathfrak{g}$ of $G$ have some deep connections with the vertex colorings of $G$. In this talk, I will explain how to get the generalized chromatic polynomials of $G$ in terms of graded dimensions of the Lie algebra of $G$. We will use this connection to give a Lie theoretic proof of of Stanley's reciprocity theorem of chromatic polynomials.

Bharatram Rangarajan (Hebrew University, Jerusalem, Israel) Sep 26, 2018
Expanders: From Graphs to Complexes (note: unusual day)

Abstract. The aim of this talk is to give a high-level overview of the theory of expander graphs and introduce motivations and possible approaches to generalizing it to higher dimensions. I shall begin with three perspectives on expansion in graphs- discrepancy, isoperimetry and mixing time, and show a qualitative equivalence of these notions in defining expansion for graphs. Next I shall briefly discuss upper and lower bounds on expansion, and sketch the Lubotzky-Phillips-Sarnak construction of Ramanujan graphs. Finally, I hope to motivate high-dimensional expanders using two interesting topics- the overlapping problem, and the threshold problem.

Amritanshu Prasad (IMSc, Chennai) Sep 28, 2018
The words that describe symmetric polynomials
(speaking in / subsumed by the Eigenfunctions Seminar)

G.V.K. Teja (IISc Mathematics) Oct 5, 2018
Patterns in recurring decimals

Abstract. We will study recurrence patterns in decimal expansions of rational numbers (in any integer base for this talk). After making some initial observations, we will compute the length of the repeating part of any fraction. We conclude by explaining this result over a Euclidean domain.

Pooja Singla (IISc Mathematics) Oct 12, 2018
Gelfand's criterion and multiplicity one results

Abstract. We will describe Gelfand's criterion for the commutativity of associative algebras and discuss some of its applications towards the multiplicity one theorems for the representations of finite groups.

Arvind Ayyer (IISc Mathematics) Oct 19, 2018
Factorization theorems for classical group characters (2:30 pm – note: unusual time)

Abstract. Characters of classical groups appear in the enumeration of many interesting combinatorial problems. We show that, for a wide class of partitions, and for an even number of variables of which half are reciprocals of the other half, Schur functions (i.e., characters of the general linear group) factorize into a product of two characters of other classical groups. Time permitting, we will present similar results involving sums of two Schur functions. All the proofs will involve elementary applications of ideas from linear algebra.

This is joint work with Roger Behrend.

Dhruv Ranganathan (IAS (Princeton), MIT (Boston), USA; CMI (Chennai); Cambridge, UK) Oct 31, 2018
Tropical geometry of moduli spaces
(speaking in / subsumed by the Eigenfunctions Seminar)

(Note: The following Seminar on Nov 2 may be of related interest to those attending this talk.)

Dhruv Ranganathan (IAS (Princeton), MIT (Boston), USA; CMI (Chennai); Cambridge, UK) Nov 2, 2018
Curve counting and tropical geometry

Abstract. The counts of algebraic curves in projective space (and other toric varieties) has been intensely studied for over a century. The subject saw a major advance in the 1990s, due to groundbreaking work of Kontsevich in the 1990s. Shortly after, considerations from high energy physics led to an entirely combinatorial approach to these curve counts, via piecewise linear embeddings of graphs, pioneered by Mikahlkin. I will give an introduction to the surrounding ideas, outlining new results and new proofs that the theory enables. Time permitting I will discuss generalizations, difficulties, and future directions for the subject.

(Organizer's note: It may help to attend the preceding Eigenfunctions Seminar on Oct 31, before this talk.)

K.N. Raghavan (IMSc, Chennai) Nov 9, 2018
A refinement of the Littlewood–Richardson rule
(speaking in / subsumed by the Eigenfunctions Seminar)

Abhishek Banerjee (IISc Mathematics) Nov 16, 2018
Rings with several objects

Abstract. An ordinary ring may be seen as a preadditive category with just one object. This leads to the powerful analogy, first formulated explicitly by Mitchell in 1975, that a small preadditive category should be seen as a "ring with several objects". We will trace the history and development of the category of modules over a preadditive category.

Katharina Jochemko (KTH, Stockholm, Sweden) Dec 12, 2018
Combinatorial positive valuations (note: unusual day)

Abstract. Valuations are a classical topic in convex geometry. The volume plays an important role in many structural results, such as Hadwiger's famous characterization of continuous, rigid-motion invariant valuations on convex bodies. Valuations whose domain is restricted to lattice polytopes are less well-studied. The Betke–Kneser Theorem establishes a fascinating discrete analog of Hadwiger's Theorem for lattice-invariant valuations on lattice polytopes in which the number of lattice points – the discrete volume – plays a fundamental role. In this talk, we explore striking parallels, analogies and also differences between the world of valuations on convex bodies and those on lattice polytopes with a focus on positivity questions and links to Ehrhart theory.

Thorsten Heidersdorf (Max-Planck-Institut für Mathematik, Bonn, Germany) Dec 20, 2018
Tensor product decomposition for the general linear supergroup $GL(m|n)$ (11 am – note: unusual time and day)

Abstract. Let $\mathfrak{gl}(n)$ denote the Lie algebra of the general linear group $GL(n)$. Given two finite dimensional irreducible representations $L(\lambda), L(\mu)$ of $\mathfrak{gl}(n)$, its tensor product decomposition $L(\lambda) \otimes L(\mu)$ is given by the Littlewood-Richardson rule. The situation becomes much more complicated when one replaces $\mathfrak{gl}(n)$ by the general linear Lie superalgebra $\mathfrak{gl}(m|n)$. The analogous decomposition $L(\lambda) \otimes L(\mu)$ is largely unknown. Indeed many aspects of the representation theory of $\mathfrak{gl}(m|n)$ are more akin to the study of Lie algebras and their representations in prime characteristic or to the BGG category $\mathcal{O}$. I will give a survey talk about this problem and explain why some approaches don't work and what can be done about it. This will give me the chance to speak about a) the character formula for an irreducible representation $L(\lambda)$, b) Deligne's interpolating category $Rep(GL_t)$ for $t \in \mathbb{C}$ and c) the process of semisimplification of a tensor category.