The Institute of Mathematical Sciences

Order in Chaos: Inevitable patterns in coloured networks

Speaker: Narayanan N, Department of Mathematics, IIT Madras

Date: 20 March (Friday)   Time: 15:30

Venue: Seminar Hall, CMI

Talk Description

Suppose the connections in a large network are colored arbitrarily. Must any recognizable pattern inevitably appear? Ramsey theory, initiated by Frank P. Ramsey, is based on a striking philosophical principle: complete disorder is impossible. No matter how one colors the edges of a sufficiently large graph/network, large structured patterns must inevitably appear. Classical Ramsey theory studies the unavoidable emergence of monochromatic subgraphs in edge-colored graphs, leading to some of the most famous problems and results in combinatorics.
In this talk, we begin with the fundamental ideas of Ramsey theory and explore how order emerges from arbitrary colorings. We survey the progress of this very hard problem and will briefly touch upon the recent remarkable breakthrough where the $4^n$ ceiling given by Erdős and Szekeres in 1935 was finally broken. We then turn to an interesting variant known as Gallai colorings, where total chaos in triangles (i.e. rainbow triangles) is forbidden. A theorem of Tibor Gallai reveals that such colorings possess an unexpected hierarchical structure, dramatically simplifying the possible configurations.
This structural perspective has led to a rapidly developing area known as Gallai–Ramsey theory, which blends classical Ramsey theory with structural graph theory. We survey the results and see some surprises along the way.The talk is intended to be accessible to a broad audience. We will highlight sketches of elegant proofs, startling phenomena, and some intriguing open problems.

On Uniformly Sampled Integer valued Lipschitz Functions on regular Trees

Speaker: Kesav Krishnan, IIT Madras

Date: 27 February (Friday)   Time: 15:30

Venue: ECG Sudarshan Hall, IMSc

Talk Description

The problem of studying uniformly sampled Lipschitz functions on graphs, i.e. functions whose values differ by at most 1 at adjacent sites with prescribed boundary conditions, has attracted a great deal of interest recently in both the probability and combinatorics communities. In particular, one seeks to establish limiting properties for such functions on families of graphs that grow. On trees and expanders, it is known that the value of a randomly sampled function at the root is tight, that is the corresponding sequence of probability measures on the integer line concentrate on a given compact set. In the case of regular trees, we are able to go one step further, and explicitly characterize when the distribution of this random variable converges, in particular convergence holds if and only if the branching number is strictly less than 8. When the branching number is greater than or equal to 8, we demonstrate how the non convergence follows from an alternating pattern which holds with high probability.

On the average-case complexity of the word problem in subgroups of $GL_d(\mathbb{Z})$

Speaker: Pascal Weil, CNRS, LIPN and ReLaX (Paris and Chennai)

Date: 30 January (Friday)   Time: 15:30

Venue: CS 36 (CSB @IIT Madras)

Talk Description

This is joint work with Frédérique Bassino (Paris Nord) and Cyril Nicaud (Paris Est). The Word Problem in finitely generated subgroups of $GL_d(\mathbb{Z})$ is the following: given a word on a fixed finite alphabet of invertible matrices with integer coefficients, decide whether this word evaluates to the identity matrix. The Word Problem is trivially decidable, in polynomial time. Its worst-case complexity is known to be $\mathcal{O}(n \log^2 n)$. We give an algorithm which solves it with linear average-case complexity. This is done under the bit-complexity model, which accounts for the fact that large integers are handled, and under the assumption that the input words are chosen uniformly at random among words of a given length. See https://arxiv.org/abs/2506.00948

An introduction to GCT - from the earlier conjectures to recent work.

Speaker: K. V. Subrahmanyam, CMI

Date: 24 October 2025    Time: 15:30

Venue: ECG Sudarshan Hall, IMSc

Talk Description

Valiant[1979] conjectured that expressing the permanent polynomial perm(X), of an m x m matrix of variables X, as the determinant of an n x n matrix with entries affine linear functions in the variables X will force n to be exponential in m. Mulmuley and Sohoni[2001] proposed Geometric Complexity Theory as an approach to settle this conjecture. They believed that the lower bound will come from an understanding of the stabilizers of the permanent polynomial (under the group of invertible m^2 by m^2 matrices) and the determinant polynomial (under the group of invertible n^2 by n^2 matrices). Towards this, they formulated certain conjectures. These were shown to be inadequate to prove Valiant's conjecture by Burgisser, Ikenmeyer and Panova [2019]. By contrast, Landsberg and Ressayre [2017] proved Valiant's conjecture when the "implementation of the permanent as a determinant" is also constrained to be "equivariant".

In recent work with Adsul, Sohoni (both in IIT Mumbai) we develop a Lie algebraic approach to the problem, which allows a more geometric analysis. Our study is based on the Lie algebras of the stabilizers of the permanent and the determinant. We introduce the notion of "initial terms of a Lie algebra" which allows us to connect the Lie algebras of the two stabilizers. We also introduce "alignment", and observe that Landsberg and Ressayre's result assumes an extreme form of alignment. This gives us hope that a more nuanced understanding of alignment and of leading term Lie algebras will result in progress towards the conjecture. I hope to convey all this without assuming much background.

What you can Count with a Character Table

Speaker: Amritanshu Prasad (IMSc)

Date: 26 September 2025    Time: 15:30

Venue: NKN Hall, CMI

Talk Description

To every finite group is associated a table called its character table. The Monster group has 808017424794512875886459904961710757005754368000000000 elements, but its character table is a mere 194 x 194 array. The ATLAS of Finite Groups contains the character tables of many interesting finite groups (including the Monster). An ATLAS table contains other supplementary information such as centralizer sizes and power maps.

In this talk I will show you some things that you can count in the group using such a table. Most are well-known, and one or two, perhaps, are new.

Induced paths vs bicliques: a Ramsey-type problem

Speaker: Mathew Francis (ISI Chennai)

Date: 22 August 2025    Time: 16:00

Venue: CS 36, CSB, IIT Madras

Talk Description

Given a graph H, we say that another graph G is H-free if no subgraph of G is isomorphic to H. An induced path, or chordless path, in a graph is a path such that there is no edge in the graph between any two vertices on the path unless they appear consecutively on the path. A natural question is the following: what is the maximum integer f(n) such that every graph that has a path on n vertices contains an induced path on f(n) vertices? If no restrictions are placed on the graphs under consideration, then f(n) = 2, since complete graphs on n vertices contain Hamiltonian paths but not even an induced path on 3 or more vertices. If we consider only K_s,s-free graphs, for some fixed constant s, then f(n) = 3 since complete bipartite graphs with equal number of vertices in both partite sets also contain Hamiltonian paths but no induced paths on 4 or more vertices. Thus it makes sense to restrict our attention to K_s,s-free graphs, where s is some fixed constant (note that this class of graphs is also K_2s-free).

A classical result of Galvin, Rival and Sands (JCT-B 1982) implies that for any fixed positive integer s, every K_s,s-free graph that has a path on n vertices contains an induced path on Ω((\log\log n)^{1/3}) vertices. A spate of recent results has established that every K_s,s-free graph having a path on n vertices contains an induced path on Ω((\log\log n)^{1-δ}) vertices, and that there exist K_s,s-free graphs that contain paths on n vertices in which every induced path contains O((\log\log n)^2) vertices. This talk will attempt to give a short self-contained survey of these developments and the different kinds of techniques that were used in achieving these results.

An elementary proof of Ramanujan’s famous congruences

Speaker: Gaurav Bhatnagar

Date: 25 July 2025    Time: 16:00 – 17:30

Venue: Ramanujan Auditorium, IMSc

Talk Description

The recurrence
\( np(n) = \sum_{i=1}^n \sigma(i) p(n-i) \)
has been used by Erdős and credited to Ford (1931) but appears in Ramanujan’s notebooks. Here the divisor function \(\sigma(n)\) is related to the partition function \(p(n)\). We show how Ramanujan could have obtained this result, and show some evidence that this was one of Ramanujan’s standard tricks.

Using a slight modification of this trick, we obtain an elementary proof of Ramanujan’s famous congruences \(p(5n+4) \equiv 0 \pmod{5}\) and \(\tau(5n+5) \equiv 0 \pmod{5}\). The proof requires no more than what Euler and Jacobi (and Ramanujan) knew. The proof extends to embed the congruences into 4 infinite families of congruences for rational powers of the eta function. Many congruences of this nature have been found by Chan and Wang (2019); seven of their assertions are covered in our list.

The result may be number-theoretic in nature, but the technique is part of the combinatorial toolkit involving generating functions. This is joint work with Hartosh Singh Bal.

Factorization of classical characters twisted by roots of unity

Speaker: Arvind Ayyer (IISc Bangalore)

Date: 4 July 2025    Time: 15:30 – 17:00

Venue: Seminar Hall, CMI

Talk Description

Schur polynomials are an important family of symmetric polynomials arising as characters of the general linear group. I will begin by explaining their importance in the theory of symmetric polynomials and various formulas for them. I will then explain a classical result of Littlewood -- rediscovered many times -- about the factorization of the Schur polynomial

\( s_\lambda(x_1, \ldots, x_n, \omega x_1, \ldots, \omega x_n, \ldots, \omega^{t-1} x_1, \ldots, \omega^{t-1} x_n) \)

where \(\omega\) is a primitive \(t\)th root of unity. Time permitting, I will explain joint work with N. Kumari (J. Alg., 2022), where we extend this work to other classical characters. No background will be assumed.

Partially commutative algebraic structures and graph invariants

Speaker: R Venkatesh (IISc Bangalore)

Date: 2 May 2025    Time: 15:00 – 17:00

Venue: ECG Sudarshan Hall, IMSc

Talk Description

Various algebraic structures can be associated with graphs. In this lecture, we focus on several such structures defined by simple graphs:

• Partially commutative - monoids (Cartier-Foata monoids), associative algebras, and Lie (super) algebras
• Right-angled Artin and Coxeter groups

We will explore the connections between these algebraic structures and key graph invariants such as acyclic orientations, independence and matching polynomials, chromatic polynomials. Of particular interest is the Hilbert series of these structures. For instance, the Hilbert series of the partially commutative associative algebra \(A(G)\) associated with a graph \(G\) satisfies the identity

\( H_{A(G)}(x) = \frac{1}{I_G(x)} \)

where \(I_G(x)\) denotes the multivariate independence polynomial of \(G\). This result is well known in the Lie algebra community and can be derived as a special case of the denominator identity for Borcherds-Kac-Moody Lie algebras (see Borcherds, J Algebra, 1988; Arunkumar et al., J. Algebra, 2018). A more direct proof is provided by Duchamp and Krob (Adv. Math., 1992), and the result also follows from Viennot’s theory of heaps as a special case of the inversion lemma (see Viennot, Ann. New York Acad. Sci., 1989).

A straightforward computation using the binomial series expansion yields (see Arunkumar et al., J. Algebra, 2018):

\( I_G(x) = \sum_{m \geq 0} \prod_{q} (q)^{zm} \)

where \(\prod_{q}(q)\) denotes the generalized chromatic polynomial, which counts proper vertex multicolorings of \(G\). This identity admits generalizations to the superalgebra setting (see Chaitra et al., arXiv:2503.11320, 2025) and to the hypergraph setting (see Shushma et al., in preparation), leading to several new extensions of classical chromatic polynomials. As an independent example, we obtain an explicit formula for the Hilbert series of the right-angled Coxeter group associated with \(G\):

\( H_{W(G)}(x) = \frac{1}{1 + I_G(x)} \)

where \(W(G)\) denotes the right-angled Coxeter group of the graph \(G\). This talk is based on a series of collaborative works with several coauthors.

Machine Checked Proof of Dilworth's Theorem in Isabelle/HOL

Speaker: T. V. H. Prathamesh (Krea University)

Date: 28 March 2025    Time: 16:30

Venue: SSB 134 (GF), CSE Dept, IIT Madras

Talk Description

Interactive Theorem Provers or Proof Assistants, can be (in simplistic terms) thought of as digital proof readers. These proof readers come with the guarantee of freedom from human error and with a bare minimal degree of automation to assist in proof writing, and with the caveat that the language of these proofs is in a rigid formal language and in a system of logic amenable to machine checkability (more often than not - a type theory). The process of translating mathematical proofs originally intended for human readers into machine checked proofs is called formalisation. This translation entails reworking proofs within the constraints of language and logic, working through often missed formal details in proofs, and paying close attention to how we represent mathematical objects.

Dilworth’s theorem (1950) states that in a finite partially ordered set the largest antichain has the same cardinality as the smallest chain decomposition. In this talk, we will explore the formalisation of Dilworth’s theorem, in the proof assistant Isabelle/HOL.

We will begin with a brief survey of Interactive Theorem Proving and machine checked proofs: How did it begin? Why does it matter? Why is it relevant to combinatorics? How does a logical foundation like type theory make a difference? What role does (and can) an AI play? We will subsequently dive into both the formalisation and the process of formalisation of Dilworth’s theorem, and the challenges it entailed. Finally, we will situate this work within the broader context of the ongoing IsaConvex project, which aims to rigorously verify key results in combinatorial geometry.

This talk is based on the joint work with Vivek Soorya Maadoori, Syed M. Meesum, Shiv Pillai and Aditya Swami.

A walk through the history and present of Perfect Matchings

Speaker: Nishad Kothari (IIT Madras)

Date: 28 February 2025    Time: 15:30

Venue: Seminar Hall, Chennai Mathematical Institute

Talk Description

The study of perfect matchings goes back all the way to the Four Color Conjecture (1852) and related developments due to Tait (1880) and Petersen (1891). Since then, there have been lots of advances in the theory of perfect matchings, and during this talk, I intend to walk you through some of the major milestones.

In particular, I will discuss the seminal contribution of Tutte (1947) characterizing those graphs that have a perfect matching, and that paved the way for Edmonds’ (1965) algorithmic as well as polyhedral advances. Thereafter, I will describe the notion of pfaffian orientations introduced by theoretical physicists (1960s), to count the number of perfect matchings, and walk you through the major contributions of Little (1975), of McCuaig(2004), and independently, of Robertson, Seymour and Thomas (1999) pertaining to characterizing bipartite pfaffian graphs -- thus solving Polya’s Permanent Problem (amongst many other equivalent formulations).

Finally, I will discuss the breakthrough contributions of Lovász (1987) who characterized the matching lattice. In doing so, not only did Lovász once again establish the importance and elusive nature of the Petersen graph, but also provided the subject with solid theoretical foundations. One of Lovász’s notoriously difficult conjectures was proved by Carvalho, Lucchesi and Murty(2002), and this set the three of them on a long journey (two decades or so) of laying further theoretical foundations that they used to solve open problems and also to simplify many of the existing proofs -- including the aforementioned ones due to Little and Lovász. Their work has culminated in the recently published book “Perfect Matchings: A Theory of Matching Covered Graphs” by Lucchesi and Murty (2024). This talk is inspired by, and based on, their book.

Topology of graph properties: a gateway to topological combinatorics

Speaker: Priyavrat Deshpande (CMI)

Date: 24 January 2025    Time: 15:00 – 16:00

Venue: Chandrasekhar Hall, IMSc

Talk Description

Topological combinatorics is a very young and exciting field of mathematical research at the crossroads of algebraic topology and discrete mathematics. Over the last forty years, it has gained popularity due to growing applications in math, computer science, and other applied areas. To be precise, this field is concerned with solutions to combinatorial problems related to fair division, graph coloring, evasiveness of graph properties etc., by applying sophisticated topological tools such as the Borsuk-Ulam theorem, characteristic classes, Morse theory and spectral sequences.

In this talk, I will focus mainly on the topological spaces that arise in the context of various graph properties and their applications. I will start from the origins of this subject, i.e., Lovász’s striking proof of Kneser’s conjecture from 1978. Then, I will describe the neighborhood complexes, independence and matching complexes, also mention some of the important applications. I plan to end with some recent work on newly discovered complexes.