Source author record

E. Ghorbani

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

ResearcherUnclaimed source record

math.CO Information Theory math.IT math.PR math.RA math.RT

Catalog footprint

Research overview

8works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Regular Graphs with Minimum Spectral Gap

Aldous and Fill conjectured that the maximum relaxation time for the random walk on a connected regular graph with $n$ vertices is $(1+o(1)) \frac{3n^2}{2π^2}$ . This conjecture can be rephrased in terms of the spectral gap as follows: the spectral gap (algebraic connectivity) of a connected $k$ -regular graph on $n$ vertices is at least $(1+o(1))\frac{2kπ^2}{3n^2}$ , and the bound is attained for at least one value of $k$ . Based upon previous work of Brand, Guiduli, and Imrich, we prove this conjecture for cubic graphs. We also investigate the structure of quartic (i.e. 4-regular) graphs with the minimum spectral gap among all connected quartic graphs. We show that they must have a path-like structure built from specific blocks.

preprint2015arXiv

Integral trees with given nullity

A graph is called integral if all eigenvalues of its adjacency matrix consist entirely of integers. We prove that for a given nullity more than 1, there are only finitely many integral trees. It is also shown that integral trees with nullity 2 and 3 are unique.

preprint2014arXiv

Maximum order of triangle-free graphs with a given rank

The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. We determine the maximum order of reduced triangle-free graphs with a given rank and characterize all such graphs achieving the maximum order.

preprint2014arXiv

On Order and Rank of Graphs

The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. Akbari, Cameron, and Khosrovshahi conjectured that the number of vertices of every reduced graph of rank r is at most $m(r)=2^{(r+2)/2}-2$ if r is even and $m(r) = 5\cdot2^{(r-3)/2}-2$ if r is odd. In this article, we prove that if the conjecture is not true, then there would be a counterexample of rank at most $46$ . We also show that every reduced graph of rank r has at most $8m(r)+14$ vertices.

preprint2013arXiv

On optimality of designs with three distinct eigenvalues

Let $\D_{v,b,k}$ denote the family of all connected block designs with $v$ treatments and $b$ blocks of size $k$ . Let $d\in\D_{v,b,k}$. The replication of a treatment is the number of times it appears in the blocks of $d$ . The matrix $C(d)=R(d)-\frac{1}{k}N(d)N(d)^\top$ is called the information matrix of $d$ where $N(d)$ is the incidence matrix of $d$ and $R(d)$ is a diagonal matrix of the replications. Since $d$ is connected, $C(d)$ has $v-1$ nonzero eigenvalues $μ_1(d),...,μ_{v-1}(d)$ . Let $\D$ be the class of all binary designs of $\D_{v,b,k}$. We prove that if there is a design $d^*\in\D$ such that (i) $C(d^*)$ has three distinct eigenvalues, (ii) $d^*$ minimizes trace of $C(d)^2$ over $d\in\D$, (iii) $d^*$ maximizes the smallest nonzero eigenvalue and the product of the nonzero eigenvalues of $C(d)$ over $d\in\D$, then for all $p>0$ , $d^*$ minimizes $(\sum_{i=1}^{v-1}μ_i(d)^{-p})^{1/p}$ over $d\in\D$. In the context of optimal design theory, this means that if there is a design $d^*\in\D$ such that its information matrix has three distinct eigenvalues satisfying the condition (ii) above and that $d^*$ is E- and D-optimal in $\D$, then $d^*$ is $Φ_p$ -optimal in $\D$ for all $p>0$ . As an application, we demonstrate the $Φ_p$ -optimality of certain group divisible designs. Our proof is based on the method of KKT conditions in nonlinear programming.

preprint2011arXiv

Intersection matrices revisited

Several intersection matrices of $s$ -subsets vs. $k$ -subsets of a $v$ -set are introduced in the literature. We study these matrices systematically through counting arguments and generating function techniques. A number of new or known identities appear as natural consequences of this viewpoint; especially, appearance of the derivative operator $d/dz$ and some related operators reveals some connections between intersection matrices and the "combinatorics of creation-annihilation". As application, the eigenvalues of several intersection matrices including some generalizations of the adjacency matrices of the Johnson scheme are derived; two new bases for the Bose--Mesner algebra of the Johnson scheme are introduced and the associated intersection numbers are obtained as well. Finally, we determine the rank of some intersection matrices.

preprint2011arXiv

Simple signed Steiner triple systems

Let $X$ be a $v$ -set, $\B$ a set of 3-subsets (triples) of $X$ , and $\B^+\cup\B^-$ a partition of $\B$ with $|\B^-|=s$. The pair $(X,\B)$ is called a simple signed Steiner triple system, denoted by ST $(v,s)$ , if the number of occurrences of every 2-subset of $X$ in triples $B\in\B^+$ is one more than the number of occurrences in triples $B\in\B^-$. In this paper we prove that $\st(v,s)$ exists if and only if $v\equiv1,3\pmod6$ , $v\ne7$ , and $s\in\{0,1,...,s_v-6,s_v-4,s_v\}$ , where $s_v=v(v-1)(v-3)/12$ and for $v=7$ , $s\in\{0,2,3,5,6,8,14\}$ .

preprint2010arXiv

Integral trees of odd diameters

A graph is called integral if all eigenvalues of its adjacency matrix consist entirely of integers. Recently, Csikvari proved the existence of integral trees of any even diameter. In the odd case, integral trees have been constructed with diameter at most 7. In this paper, we show that for every odd integer n > 1, there are infinitely many integral trees of diameter n.

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.