Source author record

Nitin Singh

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

ResearcherUnclaimed source record

math.CO math.GT Computer Vision Discrete Mathematics Machine Learning Robotics

Catalog footprint

Research overview

7works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

New bounds on the anti-Ramsey numbers of star graphs

The anti-Ramsey number $ar(G,H)$ with input graph $G$ and pattern graph $H$ , is the maximum positive integer $k$ such that there exists an edge coloring of $G$ using $k$ colors, in which there are no rainbow subgraphs isomorphic to $H$ in $G$ . ( $H$ is rainbow if all its edges get distinct colors). The concept of anti-Ramsey number was introduced by Erdös, Simanovitz, and Sós in 1973. Thereafter several researchers investigated this concept in the combinatorial setting. Recently, Feng et al. revisited the anti-Ramsey problem for the pattern graph $K_{1,t}$ (for $t \geq 3$ ) purely from an algorithmic point of view due to its applications in interference modeling of wireless networks. They posed it as an optimization problem, the maximum edge $q$ -coloring problem. For a graph $G$ and an integer $q\geq 2$ , an edge $q$ -coloring of $G$ is an assignment of colors to edges of $G$ , such that edges incident on a vertex span at most $q$ distinct colors. The maximum edge $q$ -coloring problem seeks to maximize the number of colors in an edge $q$ -coloring of the graph $G$ . Note that the optimum value of the edge $q$ -coloring problem of $G$ equals $ar(G,K_{1,q+1})$ . In this paper, we study $ar(G,K_{1,t})$ , the anti-Ramsey number of stars, for each fixed integer $t\geq 3$ , both from combinatorial and algorithmic point of view. The first of our main results presents an upper bound for $ar(G,K_{1,q+1})$ , in terms of number of vertices and the minimum degree of $G$ . The second one improves this result for the case of triangle-free input graphs. For a positive integer $t$ , let $H_t$ denote a subgraph of $G$ with maximum number of possible edges and maximum degree $t$ . Our third main result presents an upper bound for $ar(G,K_{1,q+1})$ in terms of $|E(H_{q-1})|$ . All our results have algorithmic consequences.

preprint2020arXiv

Uncertainty-aware Short-term Motion Prediction of Traffic Actors for Autonomous Driving

We address one of the crucial aspects necessary for safe and efficient operations of autonomous vehicles, namely predicting future state of traffic actors in the autonomous vehicle's surroundings. We introduce a deep learning-based approach that takes into account a current world state and produces raster images of each actor's vicinity. The rasters are then used as inputs to deep convolutional models to infer future movement of actors while also accounting for and capturing inherent uncertainty of the prediction task. Extensive experiments on real-world data strongly suggest benefits of the proposed approach. Moreover, following completion of the offline tests the system was successfully tested onboard self-driving vehicles.

preprint2014arXiv

On Additive Combinatorics of Permutations of \mathbb{Z}_n

Let $\mathbb{Z}_n$ denote the ring of integers modulo $n$ . In this paper we consider two extremal problems on permutations of $\mathbb{Z}_n$ , namely, the maximum size of a collection of permutations such that the sum of any two distinct permutations in the collection is again a permutation, and the maximum size of a collection of permutations such that the sum of any two distinct permutations in the collection is not a permutation. Let the sizes be denoted by $s(n)$ and $t(n)$ respectively. The case when $n$ is even is trivial in both the cases, with $s(n)=1$ and $t(n)=n!$ . For $n$ odd, we prove $s(n)\geq (nϕ(n))/2^k$ where $k$ is the number of distinct prime divisors of $n$ . When $n$ is an odd prime we prove $s(n)\leq \frac{e^2}π n ((n-1)/e)^\frac{n-1}{2}$ . For the second problem, we prove $2^{(n-1)/2}.(\frac{n-1}{2})!\leq t(n)\leq 2^k.(n-1)!/ϕ(n)$ when $n$ is odd.

preprint2013arXiv

An infinite family of tight triangulations of manifolds

We give an explicit construction of vertex-transitive tight triangulations of $d$ -manifolds for $d\geq 2$ . More explicitly, for each $d\geq 2$ , we construct two $(d^2+5d+5)$ -vertex neighborly triangulated $d$ -manifolds whose vertex-links are stacked spheres. The only other non-trivial series of such tight triangulated manifolds currently known is the series of non-simply connected triangulated $d$ -manifolds with $2d+3$ vertices constructed by Kühnel. The manifolds we construct are strongly minimal. For $d\geq 3$ , they are also tight neighborly as defined by Lutz, Sulanke and Swartz. Like Kühnel's complexes, our manifolds are orientable in even dimensions and non-orientable in odd dimensions.

preprint2013arXiv

Minimal triangulations of (S^3\times S^1)^{#3} and (S^3 \(twisted product) S^1)^{#3}

A triangulated $d$ -manifold $K$ , satisfies the inequality $\binom{f_0(K)-d-1}{2}\geq \binom{d+2}{2}β_1(K;\mathbb{Z}_2)$ for $d\geq 3$ . The triangulated $d$ -manifolds that meet the bound with equality are called {\em tight neighborly}. In this paper, we present tight neighborly triangulations of 4-manifolds on 15 vertices with $\mathbb{Z}_3$ as automorphism group. One such example wasconstructed by Bagchi and Datta in 2011. We show that there are exactly 12 such triangulations up to isomorphism, 10 of which are orientable.

preprint2013arXiv

Non-existence of tight neighborly manifolds with $β_1=2$

For $d\geq 2$ , Walkup's class $\Kd$ consists of the $d$ -dimensional simplicial complexes whose vertex-links are stacked $(d-1)$ -spheres. Recently Lutz, Sulanke and Swartz have shown that all $\mathbb{F}$ -orientable triangulated $d$ -manifolds satisfy the inequality $\binom{f_0-d-1}{2} \geq \binom{d+2}{2}β_1$ for $d\geq 3$ . They call a $d$ -manifold \emph{tight neighborly} if it attains the equality in the bound. For $d\geq 4$ , tight neighborly $d$ -manifolds are precisely the 2-neighborly members of $\Kd$. In this paper we show that there does not exist any tight neighborly $d$ -manifold with $β_1=2$ .

preprint2012arXiv

Tight triangulations of some 4-manifolds

Walkup's class ${\cal K}(d)$ consists of the $d$ -dimensional simplicial complexes all whose vertex links are stacked $(d-1)$ -spheres. According to a result of Walkup, the face vector of any triangulated 4-manifold $X$ with Euler characteristic $χ$ satisfies $f_1 \geq 5f_0 - 15/2 χ$ , with equality only for $X \in {\cal K}(4)$ . Kühnel observed that this implies $f_0(f_0 - 11) \geq -15χ$ , with equality only for 2-neighborly members of ${\cal K}(4)$ . For $n = 6, 11$ and 15, there are triangulated 4-manifolds with $f_0=n$ and $f_0(f_0 - 11) = -15χ$ . In this article, we present triangulated 4-manifolds with $f_0 = 21, 26$ and 41 which satisfy $f_0(f_0 - 11) = -15χ$ . All these triangulated manifolds are tight and strongly minimal.

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.

Nitin Singh

Research overview

Is this your work?

7 publications

New bounds on the anti-Ramsey numbers of star graphs

Uncertainty-aware Short-term Motion Prediction of Traffic Actors for Autonomous Driving

On Additive Combinatorics of Permutations of \mathbb{Z}_n

An infinite family of tight triangulations of manifolds

Minimal triangulations of (S^3\times S^1)^{#3} and (S^3 \(twisted product) S^1)^{#3}

Non-existence of tight neighborly manifolds with $β_1=2$

Tight triangulations of some 4-manifolds

See the researcher in context

Building this map preview

Nitin Singh

Research overview

Is this your work?

7 publications

New bounds on the anti-Ramsey numbers of star graphs

Uncertainty-aware Short-term Motion Prediction of Traffic Actors for Autonomous Driving

On Additive Combinatorics of Permutations of \mathbb{Z}_n

An infinite family of tight triangulations of manifolds

Minimal triangulations of (S^3\times S^1)^{#3} and (S^3 \(twisted product) S^1)^{#3}

Non-existence of tight neighborly manifolds with β1=2β_1=2β1​=2

Tight triangulations of some 4-manifolds

See the researcher in context

Building this map preview

Non-existence of tight neighborly manifolds with $β_1=2$