Debsoumya Chakraborti

activity

20192025

most citedOn a rainbow extremal problem for color-critical graphs

11 citations · 79 across the 30 of their papers we have counts for

collaborators

32 papers

math.CO2025

Colour-biased Hamilton cycles in dense graphs and random graphs

Natalie Behague, Debsoumya Chakraborti, Jared León

A classical result of Dirac says that every $n$ -vertex graph with minimum degree at least $\frac{n}{2}$ contains a Hamilton cycle. A `discrepancy' version of Dirac's theorem was sh…

math.CO2025

Sabotaging Mantel's Theorem

Natalie Behague, Debsoumya Chakraborti, Xizhi Liu

One of the earliest results in extremal graph theory, Mantel's theorem, states that the maximum number of edges in a triangle-free graph $G$ on $n$ vertices is $\lfloor n^2/4 \rflo…

math.CO2024★ 1 cited

Almost-full transversals in equi- $n$ -squares

Debsoumya Chakraborti, Micha Christoph, Zach Hunter +2

In 1975, Stein made a wide generalisation of the Ryser-Brualdi-Stein conjecture on transversals in Latin squares, conjecturing that every equi- $n$ -square (an $n \times n$ array fill…

math.CO2024

Regular subgraphs at every density

Debsoumya Chakraborti, Oliver Janzer, Abhishek Methuku +1

In 1975, Erdős and Sauer asked to estimate, for any constant $r$ , the maximum number of edges an $n$ -vertex graph can have without containing an $r$ -regular subgraph. In a recent b…

math.CO2024

Sparse graphs with local covering conditions on edges

Debsoumya Chakraborti, Amirali Madani, Anil Maheshwari +1

In 1988, Erdős suggested the question of minimizing the number of edges in a connected $n$ -vertex graph where every edge is contained in a triangle. Shortly after, Catlin, Grossman…

math.CO2024

Colorful fractional Helly theorem via weak saturation

Debsoumya Chakraborti, Minho Cho, Jinha Kim +1

Two celebrated extensions of the classical Helly's theorem are the fractional Helly theorem and the colorful Helly theorem. Bulavka, Goodarzi, and Tancer recently established the o…

math.CO2024

Transversal cycles and paths in tournaments

Debsoumya Chakraborti, Jaehoon Kim, Hyunwoo Lee +1

Thomason [ $Trans. Amer. Math. Soc.$ 296.1 (1986)] proved that every sufficiently large tournament contains Hamilton paths and cycles with all possible orientations, except…

math.CO2024

Edge-disjoint cycles with the same vertex set

Debsoumya Chakraborti, Oliver Janzer, Abhishek Methuku +1

In 1975, Erdős asked for the maximum number of edges that an $n$ -vertex graph can have if it does not contain two edge-disjoint cycles on the same vertex set. It is known that Turá…

math.CO2024

Approximate packing of independent transversals in locally sparse graphs

Debsoumya Chakraborti, Tuan Tran

Fix $ε > 0$ and consider a multipartite graph $G$ with maximum degree at most $(1 - ε) n$ , parts $V_{1}, \dots, V_{k}$ of the same size $n$ , and where every vertex has a…

math.CO2023★ 2 cited

Robust Hamiltonicity in families of Dirac graphs

Michael Anastos, Debsoumya Chakraborti

A graph is called Dirac if its minimum degree is at least half of the number of vertices in it. Joos and Kim showed that every collection $G = {G_{1}, \dots, G_{n}}$ of Dirac g…

math.CO2023

Hamilton transversals in tournaments

Debsoumya Chakraborti, Jaehoon Kim, Hyunwoo Lee +1

It is well-known that every tournament contains a Hamilton path, and every strongly connected tournament contains a Hamilton cycle. This paper establishes transversal generalizatio…

math.CO2023★ 2 cited

Almost spanning distance trees in subsets of finite vector spaces

Debsoumya Chakraborti, Ben Lund

For $d \geq 2$ and an odd prime power $q$ , consider the vector space $F_{q}^{d}$ over the finite field $F_{q}$ , where the distance between two points $(x_{1}, \dots, x_{d})$ a…

math.CO2023★ 4 cited

Twin-width of subdivisions of multigraphs

Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey +1

For each $d \leq 3$ , we construct a finite set $F_{d}$ of multigraphs such that for each graph $H$ of girth at least $5$ obtained from a multigraph $G$ by subdividing each edge at leas…

math.CO2023

A bandwidth theorem for graph transversals

Debsoumya Chakraborti, Seonghyuk Im, Jaehoon Kim +1

Given a collection $G = (G_{1}, \dots, G_{h})$ of graphs on the same vertex set $V$ of size $n$ , an $h$ -edge graph $H$ on the vertex set $V$ is a $G$ -transversal if th…

math.CO2022★ 4 cited

Twin-width of random graphs

Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey +2

We investigate the twin-width of the Erdős-Rényi random graph $G (n, p)$ . We unveil a surprising behavior of this parameter by showing the existence of a constant $p^{*} \approx 0.4$ su…

math.CO2022★ 1 cited

Rainbow saturation for complete graphs

Debsoumya Chakraborti, Kevin Hendrey, Ben Lund +1

We call an edge-colored graph rainbow if all of its edges receive distinct colors. An edge-colored graph $Γ$ is called $H$ -rainbow saturated if $Γ$ does not contain a rainbow copy…

math.CO2022★ 11 cited

On a rainbow extremal problem for color-critical graphs

Debsoumya Chakraborti, Jaehoon Kim, Hyunwoo Lee +2

There has been extensive studies on the following question: given $k$ graphs $G_{1}, \dots, G_{k}$ over a common vertex set of size $n$ , what conditions on $G_{i}$ ensures a `colorful' co…

math.CO2021

Fractional Helly theorem for Cartesian products of convex sets

Debsoumya Chakraborti, Jaehoon Kim, Jinha Kim +2

Helly's theorem and its variants show that for a family of convex sets in Euclidean space, local intersection patterns influence global intersection patterns. A classical result of…

math.CO2021★ 5 cited

Well-mixing vertices and almost expanders

Debsoumya Chakraborti, Jaehoon Kim, Jinha Kim +2

We study regular graphs in which the random walks starting from a positive fraction of vertices have small mixing time. We prove that any such graph is virtually an expander and ha…

math.CO2021★ 2 cited

Extremal bipartite independence number and balanced coloring

Debsoumya Chakraborti

In this paper, we establish a couple of results on extremal problems in bipartite graphs. Firstly, we show that every sufficiently large bipartite graph with average degree $D$ and…

math.CO2021★ 5 cited

Majority dynamics on sparse random graphs

Debsoumya Chakraborti, Jeong Han Kim, Joonkyung Lee +1

Majority dynamics on a graph $G$ is a deterministic process such that every vertex updates its $\pm 1$ -assignment according to the majority assignment on its neighbor simultaneousl…

math.CO2021★ 2 cited

Colorful Hamilton cycles in random graphs

Debsoumya Chakraborti, Alan Frieze, Mihir Hasabnis

Given an $n$ vertex graph whose edges have colored from one of $r$ colors $C = {c_{1}, c_{2}, \dots, c_{r}}$ , we define the Hamilton cycle color profile $h c p (G)$ to be the set of vectors $…

math.CO2020★ 3 cited

Large rainbow matchings in edge-colored graphs

Debsoumya Chakraborti, Po-Shen Loh

A subgraph of an edge-colored graph is called \emph{rainbow} if all of its edges have distinct colors. There has been much research on the topic of finding a large rainbow matching…

math.CO2020★ 2 cited

Minimizing the number of edges in $K_{s, t}$ -saturated bipartite graphs

Debsoumya Chakraborti, Da Qi Chen, Mihir Hasabnis

This paper considers an edge minimization problem in saturated bipartite graphs. An $n$ by $n$ bipartite graph $G$ is $H$ -saturated if $G$ does not contain a subgraph isomorphic to…

Colour-biased Hamilton cycles in dense graphs and random graphs

Sabotaging Mantel's Theorem

Almost-full transversals in equi-n-squares

Regular subgraphs at every density

Sparse graphs with local covering conditions on edges

Colorful fractional Helly theorem via weak saturation

Transversal cycles and paths in tournaments

Edge-disjoint cycles with the same vertex set

Approximate packing of independent transversals in locally sparse graphs

Robust Hamiltonicity in families of Dirac graphs

Hamilton transversals in tournaments

Almost spanning distance trees in subsets of finite vector spaces

Twin-width of subdivisions of multigraphs

A bandwidth theorem for graph transversals

Twin-width of random graphs

Rainbow saturation for complete graphs

On a rainbow extremal problem for color-critical graphs

Fractional Helly theorem for Cartesian products of convex sets

Well-mixing vertices and almost expanders

Extremal bipartite independence number and balanced coloring

Majority dynamics on sparse random graphs

Colorful Hamilton cycles in random graphs

Large rainbow matchings in edge-colored graphs

Minimizing the number of edges in Ks,t​-saturated bipartite graphs

Almost-full transversals in equi- $n$ -squares

Minimizing the number of edges in $K_{s, t}$ -saturated bipartite graphs