Source author record

Shashank K Mehta

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

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms math.NT math.OC math.SP

Catalog footprint

Research overview

5works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

New Facets of the QAP-Polytope

The Birkhoff polytope is defined to be the convex hull of permutation matrices, $P_σ\ \forall σ\in S_n$ . We define a second-order permutation matrix $P^{[2]}_σ$ in $\mathbb{R}^{n^2\times n^2}$ corresponding to a permutation $σ$ as $(P^{[2]}_σ)_{ij,kl} = (P_σ)_{ij}(P_σ)_{kl}$ . We call the convex hull of the second-order permutation matrices, the {\em second-order Birkhoff polytope} and denote it by ${\cal B}^{[2]}$ . It can be seen that ${\cal B}^{[2]}$ is isomorphic to the QAP-polytope, the domain of optimization in {\em quadratic assignment problem}. In this work we revisit the polyhedral combinatorics of the QAP-polytope viewing it as ${\cal B}^{[2]}$ . Our main contribution is the identification of an exponentially large set of new facets of this polytope. Also we present a general inequality of which all the known facets of this polytope as well as the new ones, that we present in this paper, are special instances. We also establish the existence of more facets which are yet to be identified.

preprint2013arXiv

Completely Positive formulation of the Graph Isomorphism Problem

Given two graphs $G_1$ and $G_2$ on $n$ vertices each, we define a graph $G$ on vertex set $V_1\times V_2$ and the edge set as the union of edges of $G_1\times \bar{G_2}$ , $\bar{G_1}\times G_2$ , $\{(v,u'),(v,u"))(|u',u"\in V_2\}$ for each $v\in V_1$ , and $\{((u',v),(u",v))|u',u"\in V_1\}$ for each $v\in V_2$ . We consider the completely-positive Lovász $\vartheta$ function, i.e., $cp\vartheta$ function for $G$ . We show that the function evaluates to $n$ whenever $G_1$ and $G_2$ are isomorphic and to less than $n-1/(4n^4)$ when non-isomorphic. Hence this function provides a test for graph isomorphism. We also provide some geometric insight into the feasible region of the completely positive program.

preprint2013arXiv

Eigenvalues and Eigenvectors of the Matrix of Permutation Counts

Define a $(n^4+n^2)/2\times (n^4+n^2)/2$ symmetric $B$ . $(ij)(kl)$ is an index where $i,j,k,l\in [n]$ , $(ab)$ is an unordered pair and $(kl)$ is an ordered pair when $i\neq j$ , otherwise it is also an unordered pair. $B((ij)(kl),(ab)(xy))$ is equal to the number of permutations of S_n in which $\min\{i,j\}$ maps to $k$ , $\max\{i,j\}$ maps to $l$ , $\min\{a,b\}$ maps to $x$ and $\max\{a,b\}$ maps to $y$ . We will show that $B$ has four distinct eigenvalues: $(3/2)n!$ , $n(n-3)!$ , $(n-1)!/(n-3)$ , $2n(n-2)!$ and the corresponding eigenspace dimensions are 1, ${{n-1}\choose{2}}^2$ , $({{n-1}\choose{2}}-1)^2$ , $(n-1)^2$ respectively.

preprint2012arXiv

Representation of Cyclotomic Fields and Their Subfields

Let $\K$ be a finite extension of a characteristic zero field $\F$. We say that the pair of $n\times n$ matrices $(A,B)$ over $\F$ represents $\K$ if $\K \cong \F[A]/< B >$ where $\F[A]$ denotes the smallest subalgebra of $M_n(\F)$ containing $A$ and $< B >$ is an ideal in $\F[A]$ generated by $B$ . In particular, $A$ is said to represent the field $\K$ if there exists an irreducible polynomial $q(x)\in \F[x]$ which divides the minimal polynomial of $A$ and $\K \cong \F[A]/< q(A) >$. In this paper, we identify the smallest circulant-matrix representation for any subfield of a cyclotomic field. Furthermore, if $p$ is any prime and $\K$ is a subfield of the $p$ -th cyclotomic field, then we obtain a zero-one circulant matrix $A$ of size $p\times p$ such that $(A,\J)$ represents $\K$, where $\J$ is the matrix with all entries 1. In case, the integer $n$ has at most two distinct prime factors, we find the smallest 0-1 companion-matrix that represents the $n$ -th cyclotomic field. We also find bounds on the size of such companion matrices when $n$ has more than two prime factors.

preprint2011arXiv

Pattern polynomial graphs

A graph $X$ is said to be a pattern polynomial graph if its adjacency algebra is a coherent algebra. In this study we will find a necessary and sufficient condition for a graph to be a pattern polynomial graph. Some of the properties of the graphs which are polynomials in the pattern polynomial graph have been studied. We also identify known graph classes which are pattern polynomial graphs.

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.