DCDebsoumya Chakraborti

Debsoumya Chakraborti

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Debsoumya Chakraborti has a total of 21 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Sabotage the Mantel Theorem

    by 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 \rfloor$. We investigate how this extremal bound is affected when $G$ is additionally required to contain a prescribed graph $\mathbb{P}$ as a subgraph. We establish general upper and lower bounds for this problem, which are tight in the exponent for random triangle-free graphs and graphs generated by the triangle-free process, when the size of $\mathbb{P}$ lies within certain ranges.

  • Open Access

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

    by Debsoumya Chakraborti, Micha Christoph, Zach Hunter, Richard Montgomery, Teo Petrov

    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 filled with $n$ symbols where each symbol appears exactly $n$ times) has a transversal of size $n-1$. That is, it should have a collection of $n-1$ entries that share no row, column, or symbol. In 2017, Aharoni, Berger, Kotlar, and Ziv showed that equi-$n$-squares always have a transversal with size at least $2n/3$. In 2019, Pokrovskiy and Sudakov disproved Stein's conjecture by constructing equi-$n$-squares without a transversal of size $n-\frac{\log n}{42}$, but asked whether Stein's conjecture is approximately true. I.e., does an equi-$n$-square always have a transversal with size $(1-o(1))n$? We answer this question in the positive. More specifically, we improve both known bounds, showing that there exist equi-$n$-squares with no transversal of size $n-Ω(\sqrt{n})$ and that every equi-$n$-square contains $n-n^{1-Ω(1)}$ disjoint transversals of size $n-n^{1-Ω(1)}$.

  • Open Access

    Sparse graphs with local covering conditions on edges

    by Debsoumya Chakraborti, Amirali Madani, Anil Maheshwari, Babak Miraftab

    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, Hobbs, and Lai resolved this in a stronger form. In this paper, we study a natural generalization of the question of Erdős in which we replace `triangle' with `clique of order $k$' for ${k\ge 3}$. We completely resolve this generalized question with the characterization of all extremal graphs. Motivated by applications in data science, we also study another generalization of the question of Erdős where every edge is required to be in at least $\ell$ triangles for $\ell\ge 2$ instead of only one triangle. We completely resolve this problem for $\ell = 2$.

  • Open Access

    Colorful fractional Helly theorem via weak saturation

    by Debsoumya Chakraborti, Minho Cho, Jinha Kim, Minki Kim

    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 optimal bound for the unified generalization of the fractional and the colorful Helly theorems using a colored extension of the exterior algebra. In this paper, we combinatorially reduce both the fractional Helly theorem and its colorful version to a classical problem in extremal combinatorics known as {weak saturation}. No such results connecting the fractional Helly theorem and weak saturation are known in the long history of literature. These reductions, along with basic linear algebraic arguments for the reduced weak saturation problems, let us give new short proofs of the optimal bounds for both the fractional Helly theorem and its colorful version without using exterior algebra.

  • Open Access

    Hamilton Transversals in Tournaments

    by Debsoumya Chakraborti, Jaehoon Kim, Hyunwoo Lee, Jaehyeon Seo

    It is well-known that every tournament contains a Hamilton path, and every strongly connected tournament contains a Hamilton cycle. This paper establishes transversal generalizations of these classical results. For a collection $$\textbf{T}=(T_1,\dots ,T_m)$$ T = ( T 1 , ⋯ , T m ) of not-necessarily distinct tournaments on a common vertex set V, an m-edge directed graph $$\mathcal {D}$$ D with vertices in V is called a $$\textbf{T}$$ T -transversal if there exists a bijection $$\phi :E(\mathcal {D})\rightarrow [m]$$ ϕ : E ( D ) → [ m ] such that $$e\in E(T_{\phi (e)})$$ e ∈ E ( T ϕ ( e ) ) for all $$e\in E(\mathcal {D})$$ e ∈ E ( D ) . We prove that for sufficiently large m with $$m=|V|-1$$ m = | V | - 1 , there exists a $$\textbf{T}$$ T -transversal Hamilton path. Moreover, if $$m=|V|$$ m = | V | and at least $$m-1$$ m - 1 of the tournaments $$T_1,\ldots ,T_m$$ T 1 , … , T m are assumed to be strongly connected, then there is a $$\textbf{T}$$ T -transversal Hamilton cycle. In our proof, we utilize a novel way of partitioning tournaments which we dub $$\textbf{H}$$ H -partition.


  • Open Access

    Transversal cycles and paths in tournaments

    by Debsoumya Chakraborti, Jaehoon Kim, Hyunwoo Lee, Jaehyeon Seo

    Thomason [$\textit{Trans. Amer. Math. Soc.}$ 296.1 (1986)] proved that every sufficiently large tournament contains Hamilton paths and cycles with all possible orientations, except possibly the consistently oriented Hamilton cycle. This paper establishes $\textit{transversal}$ generalizations of these classical results. For a collection $\mathbf{T}=\{T_1,\dots,T_m\}$ of not-necessarily distinct tournaments on the common vertex set $V$, an $m$-edge directed subgraph $\mathcal{D}$ with the vertices in $V$ is called a transversal if there exists an bijection $\varphi\colon E(\mathcal{D})\to [m]$ such that $e\in E(T_{\varphi(e)})$ for all $e\in E(\mathcal{D})$. We prove that for sufficiently large $n$, there exist transversal Hamilton cycles of all possible orientations possibly except the consistently oriented one. We also obtain a similar result for the transversal Hamilton paths of all possible orientations. These results generalize the classical theorem of Thomason, and our approach provides another proof of this theorem.

  • Open Access

    Twin-width of random graphs

    by Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey, Donggyu Kim, Sang-Il Oum

    We investigate the twin-width of the Erd\H{o}s-R\'enyi random graph $G(n,p)$. We unveil a surprising behavior of this parameter by showing the existence of a constant $p^*\approx 0.4$ such that with high probability, when $p^*\le p\le 1-p^*$, the twin-width is asymptotically $2p(1-p)n$, whereas, when $01-p^*$, the twin-width is significantly higher than $2p(1-p)n$. In addition, we show that the twin-width of $G(n,1/2)$ is concentrated around $n/2 - \sqrt{3n \log n}/2$ within an interval of length $o(\sqrt{n\log n})$. For the sparse random graph, we show that with high probability, the twin-width of $G(n,p)$ is $\Theta(n\sqrt{p})$ when $(726\ln n)/n\leq p\leq1/2$.

  • Open Access

    Exact results on generalized Erdős-Gallai problems

    by Debsoumya Chakraborti, Da Qi Chen

    Generalized Tur\'an problems have been a central topic of study in extremal combinatorics throughout the last few decades. One such problem is maximizing the number of cliques of size $t$ in a graph of a fixed order that does not contain any path (or cycle) of length at least a given number. Both of the path-free and cycle-free extremal problems were recently considered and asymptotically solved by Luo. We fully resolve these problems by characterizing all possible extremal graphs. We further extend these results by solving the edge-variant of these problems where the number of edges is fixed instead of the number of vertices. We similarly obtain exact characterization of the extremal graphs for these edge variants.

  • Open Access

    Almost spanning distance trees in subsets of finite vector spaces

    by Debsoumya Chakraborti, Ben Lund

    For $d\ge 2$ and an odd prime power $q$, consider the vector space $\mathbb{F}_q^d$ over the finite field $\mathbb{F}_q$, where the distance between two points $(x_1,\ldots,x_d)$ and $(y_1,\ldots,y_d)$ is defined as $\sum_{i=1}^d (x_i-y_i)^2$. A distance graph is a graph associated with a non-zero distance to each of its edges. We show that large subsets of vector spaces over finite fields contain every nearly spanning distance tree with bounded degree in each distance. This quantitatively improves results by Bennett, Chapman, Covert, Hart, Iosevich, and Pakianathan on finding distance paths, and results by Pham, Senger, Tait, and Thu on finding distance trees. A key ingredient in proving our main result is to obtain a colorful generalization of a classical result of Haxell about finding nearly spanning bounded-degree trees in an expander.