The Combinatorial Applications & Techniques (CAT) Lab
The CAT Lab is a research group at the Department of Mathematics, IIT Jodhpur, focused on extremal problems in combinatorics and graph theory, led by Brahadeesh Sankarnarayanan. Broadly, in extremal combinatorics one asks what the largest or smallest discrete structures are with respect to natural combinatorial constraints. One is also often interested in whether such extremal objects are unique, and whether objects that are close to these extremal ones have any structural constraints.
Work in the lab currently runs along five threads.
- In the majority coloring game, two players alternately color the vertices of a tree while keeping every vertex in the minority of its own neighborhood, and the lab studies properties of the resulting majority game chromatic number.
- In \(\triangle\)-convexity, the lab is studying properties of a type of graph convexity wherein a set of vertices of a graph is convex if it is closed under the formation of triangles.
- In Brualdi–Hoffman-type extremal problems, the question is how large the spectral radius of a \(G\)-free graph on \(m\) edges can be, and which graphs attain the maximum, for some nice graphs \(G\).
- On intersection graphs of paths, the aim is to represent a given graph optimally as the vertex-intersection graph of a collection of paths.
- On fractional intersecting families, the lab is working toward a conjectured tight upper bound on the size of a fractional \(\theta\)-intersecting family of subsets of \([n]\).
The lab also has a standing interest in computational and experimental approaches to combinatorial problems, and in mathematical exposition and outreach. Members organize and take part in workshops, reading groups, film screenings, and public talks.
Members currently include PhD students, and have included Executive MTech students, and summer interns. Student work from the lab has been presented at national and international conferences and has been recognized with awards.
The CAT Lab logo
Upcoming events
Upcoming events in combinatorics and related areas
-
Oct 2026
Oliver Janzer is delivering a talk On the rational exponents conjecture at the Long Talks in Combinatorics seminar series on 20 October 2026.
-
Oct 2026
The Mid-Atlantic Algebra, Geometry, and Combinatorics (MAAGC) Workshop will be held at Virginia Commonwealth University (VCU), Richmond, VA, from 23 to 25 October 2026.
-
Dec 2026
The 48th edition of the Australasian Combinatorics Conference will be held at Monash University, Melbourne, from 7 to 11 December 2026.
-
Mar 2027
The 58th edition of the Southeastern International Conference on Combinatorics, Graph Theory, and Computing will be held at Florida Atlantic University, Boca Raton, from 8 to 12 March 2027.
Other announcements
-
Ongoing
The Chennai Combinatorics Colloquium hosts a combinatorics talk once a month in Chennai, jointly organized by CMI, Krea University, IIT Madras, IMSc and ISI Chennai.
-
Sep – Nov 2026
The Fields Institute is organizing a five-session workshop Engaging with the Leiden Declaration to bring together mathematicians who have been active in the Leiden discussions for a recurring panel conversation, and to try to understand how the recommendations of the Leiden Declaration on Artificial Intelligence and Mathematics can be put into practice.
-
Oct 2026
The 2026 Fields Medal Symposium will be held at The Fields Insitute from 13 to 16 October 2026.
Updates
-
Sep 2026
Brahadeesh participated on the MATRIX side in the MATRIX-MFO Tandem Workshop: Combinatorial Interchange, held simultaneously at MATRIX in Creswick (Australia) and MFO in Oberwolfach (Germany), from 7 to 11 September 2026.
-
Aug 2026
Brahadeesh chaired a session at the Workshop on Advanced Methods in Integral Equations and Their Applications (IIT Jodhpur) on 18 August 2026.
-
July 2026
SURAJ interns Vaibhav Suvagiya and B James Mejulan presented posters on their summer projects at IIT Jodhpur on 15 July 2026. Vaibhav's poster was on RAMO: A Verified MaxSAT Repair Oracle for Tabu Search on Ramsey 2-Colouring, A De-Confounded Negative Result, and James's poster was on Generators and Relations for Discrete Groups.
-
July 2026
Brahadeesh participated in the conference on Frontiers in Combinatorics - Topology, Algebra and Data-Driven Insights at BITS Pilani, Pilani Campus, from 6 to 10 July 2026, where he led a research discussion group on Extremal problems on fractional intersecting families.
-
July 2026
PhD student Yash Chawda delivered a contributed talk, On the Majority Game Chromatic Number of Trees, based on joint work with Brahadeesh and Saraswati Girish Nanoti (IISc), on 6 July 2026 at the conference on Frontiers in Combinatorics - Topology, Algebra and Data-Driven Insights at BITS Pilani, Pilani Campus.
-
June 2026
Brahadeesh participated in the 11th edition of the Indian School on Logic and Applications (Krea University, Sri City) from 25 to 30 June 2026.
-
June 2026
Brahadeesh delivered a talk titled Teaching logical statements at the undergraduate level: Why one common definition gets in the way at the 5th edition of the Conference on the Practice of Teaching Undergraduate Mathematics (Krea University, Sri City), on 20 June 2026.
-
June 2026
Brahadeesh was a resource person for the Summer School for Women in Mathematics and Statistics (ICTS Bengaluru), from 11 to 19 June 2026.
He also delivered a popular talk there on 12 June 2026 titled What is Combinatorial Thinking? [YouTube]
-
June 2026
Brahadeesh chaired the 5th lecture in the Prof. R. Balakrishnan Endowment Lecture series, How to obtain the Tutte polynomials of graphs from representation-theoretic methods?, delivered by R. Venkatesh (IISc) at the 22nd edition of the Annual Conference of the Academy of Discrete Mathematics and Applications & International Conference on Discrete Mathematics (IIT Madras), on 7 June 2026.
He also delivered the 15th lecture in the Prof. E. Sampathkumar Memorial Endowment Lecture series, Intersection Graphs and Path Representations, on 10 June 2026, which is celebrated as Graph Theory Day in India in honor of his birth anniversary. The talk was based on joint work with Niranjan Balachandran (IIT Bombay), Shagnik Das (National Taiwan University), and Umesh Shankar (IISc).
-
June 2026
The lab's PhD students presented contributed talks at the 22nd edition of the Annual Conference of the Academy of Discrete Mathematics and Applications & International Conference on Discrete Mathematics (IIT Madras), on 7 June 2026. Yash presented his joint work with Brahadeesh and Saraswati (IISc), On the Majority Game Chromatic Number of Trees, and Vishnu spoke on Tight Bounds on the Carathéodory and Exchange Numbers in \(\triangle\)-Convexity.
The lab is delighted to add that both talks were shortlisted for the Prof. S. S. Shrikhande Memorial Endowment and Prof. R. Balakrishnan Endowment Best Paper Awards, and Yash won the Prof. S. S. Shrikhande Memorial Endowment Best Paper Award.