Author lists are alphabetical by surname, following the standard convention in mathematics. See the AMS statement on Joint Research and Its Publication.
Journal Publications
Niranjan Balachandran and Brahadeesh Sankarnarayanan
\(5\)-list coloring toroidal \(6\)-regular triangulations in linear time
MSC 2020: 05C15, 05C85, 05C10, 05C75
· Keywords: list coloring, toroidal graph, triangulation, regular graph, linear time algorithm
We give an explicit procedure for \(5\)-list coloring a large class of toroidal \(6\)-regular
triangulations in linear time. We also show that these graphs are not \(3\)-choosable.
Niranjan Balachandran, Shagnik Das and Brahadeesh Sankarnarayanan
Bounded fractional intersecting families are linear in size
The Electronic Journal of Combinatorics 32 (2025), no. 3, #P3.34, 10 pp.
[DOI
· arXiv
· MR
· Zbl]
MSC 2020: 05D05, 05E05
· Keywords: sunflower method, intersecting families of set systems
Using the sunflower method, we show that if \(\theta \in (0,1) \cap \mathbb{Q}\) and \(\mathcal{F}\) is
a \(O(n^{1/3})\)-bounded \(\theta\)-intersecting family over \([n]\), then \(\lvert \mathcal{F} \rvert =
O(n)\), and that if \(\mathcal{F}\) is \(o(n^{1/3})\)-bounded, then \(\lvert \mathcal{F} \rvert \leq
(\frac32 + o(1))n\).
This partially solves a conjecture of Balachandran, Mathew and Mishra that any \(\theta\)-intersecting
family over \([n]\) has size at most linear in \(n\), in the regime where we have no very large sets.
Niranjan Balachandran and Brahadeesh Sankarnarayanan
Low-rank matrices, tournaments, and symmetric designs
Linear Algebra and its Applications 694 (2024), 136–147.
[DOI
· arXiv
· MR
· Zbl]
Let \(\mathbf{a} = (a_{i})_{i \geq 1}\) be a sequence in a field \(\mathbb{F}\), and \(f \colon \mathbb{F} \times \mathbb{F} \to \mathbb{F}\) be a function such that \(f(a_{i},a_{i}) \neq 0\) for all \(i \geq 1\).
For any tournament \(T\) over \([n]\), consider the \(n \times n\) symmetric matrix \(M_{T}(f, \mathbf{a})\) with zero diagonal whose \((i,j)\)th entry (for \(i < j\)) is \(f(a_{i},a_{j})\) if \(i \to j\) in \(T\), and \(f(a_{j},a_{i})\) if \(j \to i\) in \(T\).
It is known [see Balachandran et al., Linear Algebra Appl. 658 (2023), 310–318] that if \(T\) is a uniformly random tournament over \([n]\), then \(\operatorname{rank}(M_{T}(f,\mathbf{a})) \geq (\frac{1}{2}-o(1))n\) with high probability when \(\operatorname{char}(\mathbb{F}) \neq 2\) and \(f\) is a linear function.
In this paper, we investigate the other extremal question: how low can the ranks of such matrices be?
We work with sequences \(\mathbf{a}\) that take only two distinct values, so the rank of any such \(n \times n\) matrix is at least \(n/2\).
First, we show that the rank of any such matrix depends on whether an associated bipartite graph has certain eigenvalues of high multiplicity.
Using this, we show that if \(f\) is linear, then there are \(n \times n\) real matrices \(M_{T}(f;\mathbf{a})\) of rank at most \(\frac{n}{2} + O(1)\).
For rational matrices, we show that for each \(\varepsilon> 0\) we can find a sequence \(\mathbf{a}(\varepsilon)\) for which there are \(n \times n\) matrices \(M_{T}(f;\mathbf{a}(\varepsilon))\) of rank at most \((\frac{1}{2} + \varepsilon)n + O(1)\).
These matrices are constructed from symmetric designs, and we also use them to produce bisection-closed families of size greater than \(\lfloor{3n/2\rfloor} - 2\) for \(n \leq 15\), which improves the previously best known bound given in [Balachandran et al., Electron. J. Combin. 26 (2019), no. 2, #P2.40].
Niranjan Balachandran, Srimanta Bhattacharya and Brahadeesh Sankarnarayanan
Almost full rank matrices arising from transitive tournaments
Linear and Multilinear Algebra 72 (2024), no. 2, 153–161.
[DOI
· PDF
· MR
· Zbl]
Let \(\mathbb{F}\) be a field and suppose \(\mathbf{a} := (a_1, a_2, \dotsc)\) is a sequence of non-zero elements in \(\mathbb{F}\).
For a tournament \(T\) on \([n]\), associate the \(n \times n\) symmetric matrix \(M_{T}(\mathbf{a})\) (resp. skew-symmetric matrix \(M_{T, \mathrm{skew}}(\mathbf{a})\)) with zero diagonal as follows: for \(i < j\), if the edge \(ij\) is directed as \(i \to j\) in \(T\), then set \(M_{T}(\mathbf{a}) = a_i\) (resp. \(M_{T, \mathrm{skew}}(\mathbf{a}) = a_i\)), else set \(M_{T}(\mathbf{a}) = a_j\) (resp. \(M_{T, \mathrm{skew}}(\mathbf{a}) = a_j\)).
Let \(\mathcal{M}_{n}(\mathbf{a})\) (resp. \(\mathcal{M}_{n, \mathrm{skew}}(\mathbf{a})\)) be the family consisting of all the \(n \times n\) symmetric matrices \(M_{T}(\mathbf{a})\) (resp. skew-symmetric matrices \(M_{T, \mathrm{skew}}(\mathbf{a})\)) as \(T\) varies over all tournaments on \([n]\).
We show that any matrix in \(\mathcal{M}_n(\mathbf{a})\) or \(\mathcal{M}_{n, \mathrm{skew}}(\mathbf{a})\) corresponding to a transitive tournament has rank at least \(n - 1\), and this is best possible. This settles in a strong form a conjecture posed in Balachandran et al. [An ensemble of high-rank matrices arising from tournaments; Linear Algebra Appl. 2023;658:310–318].
As a corollary, any matrix in these families has rank at least \(\lfloor \log_2(n) \rfloor\).
For a set \(L\) of positive proper fractions and a positive integer \(r \geq 2\), a fractional \(r\)-closed \(L\)-intersecting family is a collection \(\mathcal{F} \subset \mathcal{P}([n])\) with the property that for any \(2 \leq t \leq r\) and \(A_1, \dotsc, A_t \in \mathcal{F}\) there exists \(\theta \in L\) such that \(\lvert A_1 \cap \dotsb \cap A_t \rvert \in \{ \theta \lvert A_1 \rvert, \dotsc, \theta \lvert A_t \rvert\}\).
In this paper we show that for \(r \geq 3\) and \(L = \{\theta\}\) any fractional \(r\)-closed \(\theta\)-intersecting family has size at most linear in \(n\), and this is best possible up to a constant factor.
We also show that in the case \(\theta = 1/2\) we have a tight upper bound of \(\lfloor \frac{3n}{2} \rfloor - 2\) and that a maximal \(r\)-closed \((1/2)\)-intersecting family is determined uniquely up to isomorphism.
Niranjan Balachandran, Srimanta Bhattacharya and Brahadeesh Sankarnarayanan
An ensemble of high-rank matrices arising from tournaments
Linear Algebra and its Applications 658 (2023), 310–318.
[DOI
· arXiv
· MR
· Zbl]
The arXiv version contains an addendum to the published paper, announced in
Richard A. Brualdi, “From the Editor-in-Chief”,
Linear Algebra and its Applications 684 (2024), 158–159.
Suppose \(\mathbb{F}\) is a field and let \(\mathbf{a} := (a_1,a_2,\dotsc)\) be a sequence of non-zero elements in \(\mathbb{F}\).
For \(\mathbf{a}_n := (a_1, \dotsc, a_n)\), we consider the family \(\mathcal{M}_n(\mathbf{a})\) of \(n\times n\) symmetric matrices \(M\) over \(\mathbb{F}\) with all diagonal entries zero and the \((i, j)\)th element of \(M\) either \(a_i\) or \(a_j\) for \(i < j\).
In this short paper, we show that all matrices in a certain subclass of \(\mathcal{M}_n(\mathbf{a})\)—which can be naturally associated with transitive tournaments—have rank at least \(\lfloor 2n/3 \rfloor - 1\).
We also show that if \(\operatorname{char}(\mathbb{F})\neq 2\) and \(M\) is a matrix chosen uniformly at random from \(\mathcal{M}_n(\mathbf{a})\), then with high probability \(\operatorname{rank}(M) \geq \bigl(\frac{1}{2} - o(1)\bigr)n\).
Brahadeesh Sankarnarayanan
Note on \(4\)-coloring \(6\)-regular triangulations on the torus
§4.1, last sentence: “\(k \geq 4\)” should be “\(k \geq 3\)”.
§4.2: “\(T(1, 2s, \lfloor (s-1)/2 \rfloor)\)” should be “\(T(1, 2s, s-1)\)”.
§4.3: “\(T(1, 2r, \lfloor (r-1)/2 \rfloor)\)” should be “\(T(1, 2r, r-1)\)”.
§4.4, second paragraph: “\(5\)-chromatic” should be “\(5\)-colorable”.
Altshuler (Discrete Math 4(3):201–217, 1973) characterized the \(6\)-regular triangulations on the torus to be precisely those that are obtained from a regular triangulation of the \(r \times s\) toroidal grid where the vertices in the first and last column are connected by a shift of \(t\) vertices.
Such a graph is denoted \(T(r, s, t)\).
Collins and Hutchinson (Graph colouring and applications. CRM proceedings and lecture notes, vol 23. American Mathematical Society, Providence, pp 21–34, 1999) classified the \(4\)-colorable graphs \(T(r, s, t)\) with \(r, s \geq 3\).
In this paper, we point out a gap in their classification and show how it can be fixed.
Combined with the classification of the \(4\)-colorable graphs \(T(1, s, t)\) by Yeh and Zhu (Discrete Math 273(1–3):261–274, 2003), this completes the characterization of the colorability of all the \(6\)-regular triangulations on the torus.
Niranjan Balachandran and Brahadeesh Sankarnarayanan
The choice number versus the chromatic number for graphs embeddable on orientable surfaces
The Electronic Journal of Combinatorics 28 (2021), no. 4, #P4.50, 20 pp.
[DOI
· arXiv
· MR
· Zbl]
We show that for loopless \(6\)-regular triangulations on the torus the gap between the choice number and chromatic number is at most \(2\).
We also show that the largest gap for graphs embeddable in an orientable surface of genus \(g\) is of the order \(\Theta(\sqrt{g})\), and moreover for graphs with chromatic number of the order \(o(\sqrt{g}/\log_{2}(g))\) the largest gap is of the order \(o(\sqrt{g})\).
Kumar Balasubramanian, K. S. Senthil Raani and Brahadeesh Sankarnarayanan
Self-dual representations of \(\mathrm{SL}(2,F)\): an approach using the Iwahori–Hecke algebra
Communications in Algebra 47 (2019), no. 10, 4210–4215.
[DOI
· PDF
· MR
· Zbl]
Let \(F\) be a non-Archimedean local field and \(G = \mathrm{SL}(2,F)\).
Let \((\pi, V)\) be an irreducible smooth Iwahori-spherical representation of \(G\).
It is easy to see that such representations are always self-dual.
The space \(V\) of \(\pi\) admits a non-degenerate \(G\)-invariant bilinear form \((\;,\;)\) which is unique up to scaling.
It can be shown that the form \((\;,\;)\) is either symmetric or skew-symmetric and we set \(\varepsilon(\pi) = \pm 1\) accordingly.
In this article, we use the Bernstein–Lusztig presentation of the Iwahori–Hecke algebra of \(G\) and show that \(\varepsilon(\pi) = 1\).
Conference Publications
Niranjan Balachandran and Brahadeesh Sankarnarayanan
\(5\)-list coloring toroidal \(6\)-regular triangulations in linear time
CALDAM 2023. In: Amitabha Bagchi, Rahul Muthu (eds.), Algorithms and Discrete Applied Mathematics, Lecture Notes in Computer Science, vol. 13947, pp. 134–146, Springer (2023). Extended abstract.
[DOI
· PDF
· MR
· Zbl]
MSC 2020: 68WXX
· Keywords: list coloring, toroidal graph, triangulation, regular graph, linear time algorithm
We give an explicit procedure for \(5\)-list coloring a large class of toroidal \(6\)-regular triangulations in linear time.
We also show that these graphs are not \(3\)-choosable.
Manuscripts in Preparation
Niranjan Balachandran, Shagnik Das, Brahadeesh Sankarnarayanan and Umesh Shankar
An extremal problem for vertex intersection graphs of paths
2026.
A path representation of a simple graph \(G\) is a simple graph \(H\) along with an edge partition \(\mathcal{P} = \{P_u : u \in V(G)\}\) of \(H\) into non-trivial paths such that \(\{u,v\} \in E(G)\) if and only if \(P_u\) and \(P_v\) intersect in \(H\).
A path representation is proper if no two paths in \(\mathcal{P}\) can be concatenated into another path. The path representation number, \(\mathsf{prn}(G)\), of a graph \(G\) is the minimum number of vertices in any proper path representation of \(G\).
We give bounds on \(\mathsf{prn}(G)\) in terms of the order and size of \(G\), as well as other well-known graph parameters such as the clique cover number, \(\mathsf{cc}(G)\), the clique partition number, \(\mathsf{cp}(G)\), and the clique number, \(\omega(G)\).
We investigate proper path representations of various classes of graphs, including complete bipartite graphs, complete graphs, the Erdős–Rényi random graph \(G(n,p)\), and triangle-free graphs, particularly trees.