First Edition · Chennai
Takes a minute. Helps us plan seating and lunch.
Click the poster for the full-size image
Total positivity and statistical mechanics
Tea
On the smallest antichain that generates an ideal of a given size
Lunch
Matching minors: a sequel to the results of Lovász and Plummer
Skeleton ideals, spherical parking functions and uprooted trees
Tea
Recent developments on the bichromatic triangle conjecture
TIFR-CAM
09:30–10:45
Total positivity and statistical mechanics
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.
IISc Bengaluru
11:15–12:30
On the smallest antichain that generates an ideal of a given size
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.
IIT Madras
14:00–14:45
Matching minors: a sequel to the results of Lovász and Plummer
A connected graph is matching covered if each edge lies in some perfect matching. There is extensive literature on this class; one may refer to the recent monograph Perfect Matchings: A Theory of Matching Covered Graphs by Lucchesi and Murty (2024). One of the fundamental pillars of this subject is the tight cut decomposition theory. In particular, Lovász (JCT-B, 1987) established that every matching covered graph $G$ admits a unique decomposition into special ones called bricks (nonbipartite) and braces (bipartite); we use $b(G)$ to denote its number of bricks. We remark that $G$ is bipartite if and only if $b(G) = 0$.
Certain containment notions such as minors and topological minors play a key role in graph theory. Likewise, there are containment notions that preserve the property of being matching covered. One of them, ‘conformal minors’, is intrinsically related to the ear decomposition theory of matching covered graphs; Lovász and Plummer showed that every such graph, except $K_2$ and cycles, contains either $\theta$ or $K_4$ as a conformal minor, where $\theta$ is the 3-regular graph on two vertices. Moreover, Lovász proved that every nonbipartite matching covered graph (or equivalently, those with $b \geq 1$) contains either $K_4$ or the triangular prism $\overline{C_6}$ as a conformal minor. It is worth noting that, in the case of nonbipartite matching covered graphs, Lovász’s result implies the aforementioned result of Lovász and Plummer; in this sense, the former may be viewed as a refinement of the latter that is applicable to a smaller class of graphs.
In the same spirit, we present a further refinement of Lovász’s result that is applicable to those matching covered graphs that satisfy $b \geq 2$. For technical reasons, it is imperative to use a weaker notion of containment, ‘matching minors’. In a joint work with Nishad Kothari, we prove that every such graph contains one of 20 graphs as a matching minor; each of these 20 graphs has the (desired) properties that $b = 2$ whereas every proper matching minor satisfies $b \leq 1$. As a corollary of our main result, we establish Dalwadi’s conjecture (2024), which states that every matching covered graph with $b \geq 2$ contains a bisubdivision of $K_{2,3}$ as a subgraph.
In this talk, we shall discuss the above, and also mention some applications if time permits. The talk will be self-contained, and only basic knowledge of graph theory will be assumed.
CMI
14:50–15:35
Skeleton ideals, spherical parking functions and uprooted trees
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.
Krea University
16:00–17:00
Recent developments on the bichromatic triangle conjecture
In this talk, we discuss recent developments on the bichromatic triangle conjecture, after some preliminaries and old results. In particular we introduce block bicolored arrangements and prove that the bichromatic 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.
Attendance is free and open to anyone interested — students and researchers alike. Fill the registration form so we can plan seating and catering.