Source author record

Deepak Bal

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.PR

Catalog footprint

Research overview

12works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

On the size Ramsey number of all cycles versus a path

We say $G\to (\mathcal{C}, P_n)$ if $G-E(F)$ contains an $n$ -vertex path $P_n$ for any spanning forest $F\subset G$ . The size Ramsey number $\hat{R}(\mathcal{C}, P_n)$ is the smallest integer $m$ such that there exists a graph $G$ with $m$ edges for which $G\to (\mathcal{C}, P_n)$ . Dudek, Khoeini and Prałat proved that for sufficiently large $n$ , $2.0036n \le \hat{R}(\mathcal{C}, P_n)\le 31n$ . In this note, we improve both the lower and upper bounds to $2.066n\le \hat{R}(\mathcal{C}, P_n)\le 5.25n+O(1).$ Our construction for the upper bound is completely different than the one considered by Dudek, Khoeini and Prałat. We also have a computer assisted proof of the upper bound $\hat{R}(\mathcal{C}, P_n)\le \frac{75}{19}n +O(1) < 3.947n$ .

preprint2016arXiv

Rainbow perfect matchings and Hamilton cycles in the random geometric graph

Given a graph on $n$ vertices and an assignment of colours to the edges, a rainbow Hamilton cycle is a cycle of length $n$ visiting each vertex once and with pairwise different colours on the edges. Similarly (for even $n$ ) a rainbow perfect matching is a collection of $n/2$ independent edges with pairwise different colours. In this note we show that if we randomly colour the edges of a random geometric graph with sufficiently many colours, then a.a.s. the graph contains a rainbow perfect matching (rainbow Hamilton cycle) if and only if the minimum degree is at least $1$ (respectively, at least $2$ ). More precisely, consider $n$ points (i.e. vertices) chosen independently and uniformly at random from the unit $d$ -dimensional cube for any fixed $d\ge2$ . Form a sequence of graphs on these $n$ vertices by adding edges one by one between each possible pair of vertices. Edges are added in increasing order of lengths (measured with respect to the $\ell_p$ norm, for any fixed $1<p\le\infty$ ). Each time a new edge is added, it receives a random colour chosen uniformly at random and with repetition from a set of $\lceil Kn\rceil$ colours, where $K=K(d)$ is a sufficiently large fixed constant. Then, a.a.s. the first graph in the sequence with minimum degree at least $1$ must contain a rainbow perfect matching (for even $n$ ), and the first graph with minimum degree at least $2$ must contain a rainbow Hamilton cycle.

preprint2015arXiv

The Total Acquisition Number of Random Graphs

Let $G$ be a graph in which each vertex initially has weight 1. In each step, the weight from a vertex $u$ can be moved to a neighbouring vertex $v$ , provided that the weight on $v$ is at least as large as the weight on $u$ . The total acquisition number of $G$ , denoted by $a_t(G)$ , is the minimum possible size of the set of vertices with positive weight at the end of the process. LeSaulnier, Prince, Wenger, West, and Worah asked for the minimum value of $p=p(n)$ such that $a_t(\mathcal{G}(n,p)) = 1$ with high probability, where $\mathcal{G}(n,p)$ is a binomial random graph. We show that $p = \frac{\log_2 n}{n} \approx 1.4427 \ \frac{\log n}{n}$ is a sharp threshold for this property. We also show that almost all trees $T$ satisfy $a_t(T) = Θ(n)$ , confirming a conjecture of West.

preprint2014arXiv

Packing tree factors in random and pseudo-random graphs

For a fixed graph H with t vertices, an H-factor of a graph G with n vertices, where t divides n, is a collection of vertex disjoint (not necessarily induced) copies of H in G covering all vertices of G. We prove that for a fixed tree T on t vertices and ε> 0, the random graph G_{n,p}, with n a multiple of t, with high probability contains a family of edge-disjoint T-factors covering all but an ε-fraction of its edges, as long as ε^4 n p >> (log n)^2. Assuming stronger divisibility conditions, the edge probability can be taken down to p > (C log n)/n. A similar packing result is proved also for pseudo-random graphs, defined in terms of their degrees and co-degrees.

preprint2014arXiv

Power of $k$ choices and rainbow spanning trees in random graphs

We consider the Erdős-Rényi random graph process, which is a stochastic process that starts with $n$ vertices and no edges, and at each step adds one new edge chosen uniformly at random from the set of missing edges. Let $\mathcal{G}(n,m)$ be a graph with $m$ edges obtained after $m$ steps of this process. Each edge $e_i$ ( $i=1,2,..., m$ ) of $\mathcal{G}(n,m)$ independently chooses precisely $k \in \mathbb{N}$ colours, uniformly at random, from a given set of $n-1$ colours (one may view $e_i$ as a multi-edge). We stop the process prematurely at time $M$ when the following two events hold: $\mathcal{G}(n,M)$ is connected and every colour occurs at least once ( $M={n \choose 2}$ if some colour does not occur before all edges are present; however, this does not happen asymptotically almost surely). The question addressed in this paper is whether $\mathcal{G}(n,M)$ has a rainbow spanning tree (that is, multicoloured tree on $n$ vertices). Clearly, both properties are necessary for the desired tree to exist. In 1994, Frieze and McKay investigated the case $k=1$ and the answer to this question is "yes" (asymptotically almost surely). However, since the sharp threshold for connectivity is $\frac {n}{2} \log n$ and the sharp threshold for seeing all the colours is $\frac{n}{k} \log n$ , the case $k=2$ is of special importance as in this case the two processes keep up with one another. In this paper, we show that asymptotically almost surely the answer is "yes" also for $k \ge 2$ .

preprint2014arXiv

Rainbow arborescence in random digraphs

We consider the Erdős-Rényi random directed graph process, which is a stochastic process that starts with $n$ vertices and no edges, and at each step adds one new directed edge chosen uniformly at random from the set of missing edges. Let $\mathcal{D}(n,m)$ be a graph with $m$ edges obtained after $m$ steps of this process. Each edge $e_i$ ( $i=1,2,\ldots, m$ ) of $\mathcal{D}(n,m)$ independently chooses a colour, taken uniformly at random from a given set of $n(1 + O( \log \log n / \log n)) = n (1+o(1))$ colours. We stop the process prematurely at time $M$ when the following two events hold: $\mathcal{D}(n,M)$ has at most one vertex that has in-degree zero and there are at least $n-1$ distinct colours introduced ( $M= n(n-1)$ if at the time when all edges are present there are still less than $n-1$ colours introduced; however, this does not happen asymptotically almost surely). The question addressed in this paper is whether $\mathcal{D}(n,M)$ has a rainbow arborescence (that is, a directed, rooted tree on $n$ vertices in which all edges point away from the root and all the edges are different colours). Clearly, both properties are necessary for the desired tree to exist and we show that, asymptotically almost surely, the answer to this question is "yes".

preprint2014arXiv

Rainbow Matchings and Hamilton Cycles in Random Graphs

Let $HP_{n,m,k}$ be drawn uniformly from all $k$ -uniform, $k$ -partite hypergraphs where each part of the partition is a disjoint copy of $[n]$ . We let $HP^{(\k)}_{n,m,k}$ be an edge colored version, where we color each edge randomly from one of $\k$ colors. We show that if $\k=n$ and $m=Kn\log n$ where $K$ is sufficiently large then w.h.p. there is a rainbow colored perfect matching. I.e. a perfect matching in which every edge has a different color. We also show that if $n$ is even and $m=Kn\log n$ where $K$ is sufficiently large then w.h.p. there is a rainbow colored Hamilton cycle in $G^{(n)}_{n,m}$ . Here $G^{(n)}_{n,m}$ denotes a random edge coloring of $G_{n,m}$ with $n$ colors. When $n$ is odd, our proof requires $m=\om(n\log n)$ for there to be a rainbow Hamilton cycle.

preprint2013arXiv

On Sharp Thresholds of Monotone Properties: Bourgain's Proof Revisited

The purpose of this expository note is to give the proof of a theorem of Bourgain with some additional details and updated notation. The theorem first appeared as an appendix to the breakthrough paper by Friedgut, \emph{Sharp Thresholds of graph properties and the $k$ -SAT Problem}. Throughout, we use notation and definitions akin to those in O'Donnell's book, \emph{Analysis of Boolean Functions}.

preprint2012arXiv

A greedy algorithm for finding a large 2-matching on a random cubic graph

A 2-matching of a graph $G$ is a spanning subgraph with maximum degree two. The size of a 2-matching $U$ is the number of edges in $U$ and this is at least $n-\k(U)$ where $n$ is the number of vertices of $G$ and $\k$ denotes the number of components. In this paper, we analyze the performance of a greedy algorithm \textsc{2greedy} for finding a large 2-matching on a random 3-regular graph. We prove that with high probability, the algorithm outputs a 2-matching $U$ with $\k(U) = \tildeΘ\of{n^{1/5}}$.

preprint2012arXiv

The t-tone chromatic number of random graphs

A proper 2-tone $k$ -coloring of a graph is a labeling of the vertices with elements from $\binom{[k]}{2}$ such that adjacent vertices receive disjoint labels and vertices distance 2 apart receive distinct labels. The 2-tone chromatic number of a graph $G$ , denoted $τ_2(G)$ is the smallest $k$ such that $G$ admits a proper 2-tone $k$ coloring. In this paper, we prove that w.h.p. for $p\ge Cn^{-1/4}\ln^{9/4}n$ , $τ_2(G_{n,p})=(2+o(1))χ(G_{n,p})$ where $χ$ represents the ordinary chromatic number. For sparse random graphs with $p=c/n$ , $c$ constant, we prove that $τ_2(G_{n,p}) = \lceil{{\sqrt{8Δ+1} +5}/{2}}\rceil$ where $Δ$ represents the maximum degree. For the more general concept of $t$ -tone coloring, we achieve similar results.

preprint2011arXiv

On the Maximum Number of Edges in a Hypergraph with a Unique Perfect Matching

In this note, we determine the maximum number of edges of a $k$ -uniform hypergraph, $k\ge 3$ , with a unique perfect matching. This settles a conjecture proposed by Snevily.

preprint2011arXiv

Packing tight Hamilton cycles in uniform hypergraphs

We say that a $k$ -uniform hypergraph $C$ is a Hamilton cycle of type $\ell$ , for some $1\le \ell \le k$ , if there exists a cyclic ordering of the vertices of $C$ such that every edge consists of $k$ consecutive vertices and for every pair of consecutive edges $E_{i-1},E_i$ in $C$ (in the natural ordering of the edges) we have $|E_{i-1}\setminus E_i|=\ell$ . We define a class of $(\e,p)$-regular hypergraphs, that includes random hypergraphs, for which we can prove the existence of a decomposition of almost all edges into type $\ell$ Hamilton cycles, where $\ell<k/2$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Deepak Bal

Research overview

Is this your work?

12 publications

On the size Ramsey number of all cycles versus a path

Rainbow perfect matchings and Hamilton cycles in the random geometric graph

The Total Acquisition Number of Random Graphs

Packing tree factors in random and pseudo-random graphs

Power of $k$ choices and rainbow spanning trees in random graphs

Rainbow arborescence in random digraphs

Rainbow Matchings and Hamilton Cycles in Random Graphs

On Sharp Thresholds of Monotone Properties: Bourgain's Proof Revisited

A greedy algorithm for finding a large 2-matching on a random cubic graph

The t-tone chromatic number of random graphs

On the Maximum Number of Edges in a Hypergraph with a Unique Perfect Matching

Packing tight Hamilton cycles in uniform hypergraphs

See the researcher in context

Building this map preview

Deepak Bal

Research overview

Is this your work?

12 publications

On the size Ramsey number of all cycles versus a path

Rainbow perfect matchings and Hamilton cycles in the random geometric graph

The Total Acquisition Number of Random Graphs

Packing tree factors in random and pseudo-random graphs

Power of kkk choices and rainbow spanning trees in random graphs

Rainbow arborescence in random digraphs

Rainbow Matchings and Hamilton Cycles in Random Graphs

On Sharp Thresholds of Monotone Properties: Bourgain's Proof Revisited

A greedy algorithm for finding a large 2-matching on a random cubic graph

The t-tone chromatic number of random graphs

On the Maximum Number of Edges in a Hypergraph with a Unique Perfect Matching

Packing tight Hamilton cycles in uniform hypergraphs

See the researcher in context

Building this map preview

Power of $k$ choices and rainbow spanning trees in random graphs