A majority coloring of a graph is a vertex coloring in which each vertex has at most half of its neighbors sharing its color; Lovász showed in 1966 that two colors always suffice for any finite graph. In the majority coloring game, two players alternately color vertices from a fixed palette while maintaining the majority condition, and the least number of colors for which the first player has a winning strategy is the majority game chromatic number \(\mu_g(G)\). While \(\mu_g(G)\) is unbounded in general, it is at most \(4\) for trees. Yash Chawda, Saraswati Girish Nanoti, and I study \(\mu_g(T)\) for binary and ternary trees using a configuration-based strategy, in which the first player aims to prevent a small family of local obstruction patterns from arising.

An interactive Tree Coloring Explorer built by Yash is available for experimenting with majority colorings on trees.

Given a graph \(G\), a set \(S\) of vertices is \(\triangle\)-convex if every vertex that forms a triangle with two vertices of \(S\) already belongs to \(S\). This gives rise to natural analogues of classical convexity parameters, among them the Carathéodory number \(c_\triangle(G)\), defined as the size of a largest Carathéodory-independent set, where a set \(S\) is Carathéodory-independent if \[ \operatorname{Hull}(S) \setminus \bigcup_{a \in S} \operatorname{Hull}(S \setminus \{a\}) \neq \emptyset. \] Vishnu and I study the bound \(c_\triangle(G) \leq t + 1\) for graphs with \(t\) triangles, providing a new proof via a component-counting argument: given a Carathéodory-independent set \(S\), we partition the triangles of \(G\) according to the connected components of the induced subgraph \(G[S]\) and count them directly. The same method is expected to extend to exchange numbers and to extremal characterizations.

An interactive \(\triangle\)-Convexity Explorer (based on a graph explorer built by Yash) is available for experimenting with Carathéodory (in)dependence in \(\triangle\)-convexity spaces.

The classical Turán-type extremal problem asks for the maximum number of edges in an \(F\)-free graph on \(n\) vertices, along with a characterization of the extremal graphs, where \(F\) is a fixed graph (or class of graphs). The spectral version, introduced by Nikiforov, asks for bounds on the maximum spectral radius of an \(F\)-free graph on \(n\) vertices. One can also pose analogous questions for \(F\)-free graphs on \(m\) edges; this is the Brualdi–Hoffman-type variant.

The triangle case (\(F = K_3\)) has received considerable attention in the recent literature. M. Rajesh Kannan and I focus on the case \(F = K_4\), the next case in the complete-graph progression.

The problem of representing a graph as the intersection graph of a collection of geometric or combinatorial objects is well studied — both theoretically and from computational and practical standpoints. Our focus was on representing a given graph optimally (in a precise sense) as the vertex-intersection graph of a collection of paths.

Such representations always exist, but finding optimal ones, or even tight bounds on their order, does not seem to be an easy problem. Several questions in this area remain open. See Balachandran et al. (in preparation).

A classical problem in extremal set theory asks for the maximum size of a family \(\mathcal{F}\) of subsets of \([n]\) subject to a prescribed intersection condition. A fractional \(\theta\)-intersecting family is a collection \(\mathcal{F}\) of subsets of \([n]\) such that for every \(A, B \in \mathcal{F}\), the ratio \(|A \cap B|\,/\,|A \cup B|\) belongs to a prescribed set \(\theta \subseteq [0,1]\). Balachandran, Mathew, and Mishra conjectured a tight upper bound on the maximum size of such families. I am continuing work toward a resolution of this conjecture, building on earlier partial results for special cases. See Balachandran et al. (2023b) and Balachandran et al. (2025).

My doctoral work spanned three threads in extremal and algebraic combinatorics.

Graph colorings. I studied the gap between the chromatic and list chromatic numbers for graphs embeddable on a surface. In particular, I completed the classification of the colorability of the \(6\)-regular triangulations of the torus and gave a linear-time \(5\)-list-coloring algorithm for a large class of these triangulations. See Sankarnarayanan (2022), Balachandran–Sankarnarayanan (2021), and Balachandran–Sankarnarayanan (2026).

Extremal set theory. I studied a fractional variant of \(L\)-intersecting set systems and made progress on tight upper bounds for the sizes of such families. See Balachandran et al. (2023b) and Balachandran et al. (2025).

Combinatorial matrix theory. I studied the ranks of a class of symmetric, zero-diagonal matrices that arise from tournaments on \([n]\). These matrices have rank at least linear in \(n\) with high probability, and I characterized their rank in several extremal cases. The constructions also yield bisection-closed families that improve previous bounds, connecting back to extremal set theory. See Balachandran et al. (2023a), Balachandran et al. (2024), and Balachandran–Sankarnarayanan (2024).

Full thesis: Some problems in combinatorics: Excursions in graph colorings and extremal set theory.

Prior to my PhD, I briefly worked as a project assistant with Kumar Balasubramanian at IISER Bhopal, studying a small amount of \(p\)-adic representation theory; see Balasubramanian et al. (2019). My Master's thesis, also at IISER Bhopal, was on automorphic forms and Tate's thesis, guided by Karam Deo Shankhadhar. During my undergraduate studies, I also explored some number theory under Brundaban Sahu at NISER Bhubaneswar.