Chennai Combinatorics Day
First Edition
Speakers: Terrence George (TIFR-CAM), CP Anil Kumar (Krea), Sunil Chandran (IISc), Ravindra Pawar (IIT-M), Gargi Lather (CMI)
Date: 29 July (Wednesday) Time: 09:30 AM - 5:30 PM
Venue: FC Kohli Center (near CMI)
Registration
Please fill this form to register
Titles and Abstracts
Ravindra Pawar
Title: Matching Minors: a sequel to the results of Lovsz and Plummer
Abstract: TBA
Sunil Chandran
Title: On the smallest antichain that generates an ideal of a given size.
Abstract: Model counting is a fundamental problem that consists of determining the number of satisfying assignments for a given Boolean formula. The weighted variant, which computes the weighted sum of satisfying assignments, has extensive applications in probabilistic reasoning, network reliability, statistical physics, and formal verification. A common approach for solving weighted model counting is to reduce it to unweighted model counting, which raises an important question: What is the minimum number of terms (or clauses) required to construct a DNF (or CNF) formula with exactly $k$ satisfying assignments? We show that this problem is equivalent to finding the smallest antichain that generates an ideal of a given size. In this paper, we establish both upper and lower bounds on this question. We prove that for any natural number $k$, one can construct a monotone DNF formula with exactly $k$ satisfying assignments using at most $O(\sqrt{\log k}\log\log k)$ terms. This construction represents the first $o(\log k)$ upper bound for this problem. We complement this result by showing that there exist infinitely many values of $k$ for which any DNF or CNF representation requires at least $\Omega(\log\log k)$ terms or clauses. These results have significant implications for the efficiency of model counting algorithms based on formula transformations. Recently we improved the upper bound to $O((\log\log k)^2/\log\log\log k)$. This result is not yet published.
CP Anil Kumar
Title: Recent Developments on Bichromatic Triangle Conjecture
Abstract: In this talk, we discuss recent developments on Bichromatic Triangle Conjecture and after some preliminaries and old results. In particular we introduce block bicolored arrangements and prove that the bichormatic triangle conjecture holds for them. We also show that any bicoloring with at most five of one color has a bichromatic triangle. Then we prove the latest result proved in January 2026 by Y.A.Radtke, B. Keszegh and R. Lauff that in every simple Euclidean pseudoline arrangement colored by two colors red and blue, either there exists a bichromatic triangle or a red-red-blue-blue quadrangle. After this, if time permits I will mention some more recent results by the same three authors on the maximum sizes of independence numbers of the (pseudo)line-face hypergraphs and (pseudo)line-triangle hypergraphs.
Terrence George
Title: Total positivity and statistical mechanics
Abstract: A real matrix is called totally positive if all of its minors are positive. Total positivity is closely related to certain statistical mechanical models on planar graphs. In this talk, I will give an overview of this area and then discuss joint work with Sunita Chepuri and David Speyer relating spanning trees to a symplectic analog of total positivity.
Gargi Lather
Title: Skeleton Ideals, Spherical Parking Functions and Uprooted Trees
Abstract: Graphical parking functions form a natural generalization of classical parking functions and arise algebraically as the standard monomials of the G-parking function ideal introduced by Postnikov and Shapiro. For a rooted graph G, this ideal is defined in a polynomial ring whose variables correspond to the non-root vertices of G and its standard monomials are in bijection with the spanning trees of G. Skeleton ideals form a natural family of subideals of the G-parking function ideal and lead to the notion of spherical G-parking functions. In this talk, I will discuss spherical parking functions from a combinatorial point of view, with emphasis on their relationship with uprooted trees. I will explain how these objects arise from skeleton ideals and describe some enumerative results for certain classes of graphs.