The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
1answer
216 views

What is the largest possible operator norm of a sparse (0,1)-matrix?

Inspired by this question, I was wondering about the following problem: Consider all $n\times n$ $(0,1)$-matrices with $k$ ones. Which of these matrices has the largest operator norm? And how does ...
-1
votes
1answer
225 views

Upper bound on iterations count for power iteration algorithm

I'm stuck trying to get upper bound on iterations count for power iteration algroithm for finding first eigenvalue of adjacency matrix $A$ given tolerance value. I've tried to figure something out ...
4
votes
0answers
130 views

Relaxation = absorption?

Let $A$ be a stochastic matrix, that is, the entries are non-negative and each row adds to $1$. Assume that it is primitive, that is, $A^n$ has only positive entries for sufficiently large $n$. We ...
1
vote
2answers
207 views

Random walk on the hypercube

Consider the hypercube $Q_4$. I would like to know how to compute the number of steps of a random walk in this graph such that the probability to be at a vertex is a given number $x$. I think I just ...
11
votes
1answer
267 views

Variant of an Expander graph: Probability that S random points cast a shadow/projection of size at most S/2 on each face of a cube.

Consider an integer cube of size $\sqrt{k} \times \sqrt{k} \times \sqrt{k}$, where $k$ is an asymptotically large perfect square number. Place k points in this cube at uniformly random locations, ...
1
vote
1answer
105 views

Spectrum of composition of graphs( lexicographic product)

I was wondering how to relate the spectra of the composition of two graphs in term of the factors...someone can help me?
4
votes
1answer
551 views

How many distinct eigenvalues does a random graph have?

It is well-known that a random graph a.e. has diameter 2. It is also well-known that the number of distinct eigenvalues of a graph is at least the diameter plus one. But what is known about the ...
0
votes
0answers
93 views

Global solution for spectral clustering

I used spectral clustering for directed graphs suggested by Dengyong Zhou paper to partition the graph.I selected the eigen vectors corresponding to k largest eigen values and then I use kmeans or FCM ...
10
votes
0answers
221 views

Ramanujan Digraphs?

In Gowers' paper on quasirandom groups, he suggests a spectral theory of bipartite graphs employ the singular values of the bipartite adjacency matrix. Accordingly, singular values appear to be a ...
4
votes
2answers
340 views

signing a strongly regular graph

Let $A$ be the adjacency matrix of a strongly regular graph. When is it possible to sign $A$ (i.e. replace some of the +1 entries by -1) so that the resulting matrix has exactly two eigenvalues? I ...
5
votes
1answer
238 views

Dimension of Specht Modules $S^\lambda$

In the study of representation theory of $S_n$, we know that the irreducible characters of $\chi_\lambda$ of $S_n$ are indexed by partitions $\lambda \vdash n$. There are several methods in ...
2
votes
1answer
572 views

Eigenvalues of directed Laplacian matrix $L$ and $DL$, where $D$ is a diagonal matrix with positive entries

I have a weighted Laplacian matrix $L$ of a strongly connected directed graph and a diagonal matrix $D$ with positive entries. Since the graph is directed, $L$ is non-symmetric real. Further, since ...
1
vote
2answers
288 views

How to identify bridge nodes between nearly connected graph components in partitioned adjacency matrices?

I have adjacency matrices which have nearly connected components. That is partitions with a dense number of edges between nodes in the same group and few edges acting as bridges between these groups. ...
0
votes
1answer
352 views

Find edge weights that fit given node weights

Let $G = (V,E)$ be a connected simple graph (unweighted, undirected, no selfloops) on $n$ nodes. Let $\mathbf{d} := (d_1, d_2, ..., d_n) \in \mathbb{R}_{>0}^n$ be a vector of arbitrary given node ...
0
votes
1answer
1k views

Can the first non-zero eigenvalue of a Laplacian matrix with more than 1 zero valued eigenvalue be used to reorder an adjacency matrix?

I have a graph with multiple connected components, and its adjacency matrix. I form the Laplacian matrix (wiki Laplacian matrix), and from the 1K nodes there around ...
3
votes
1answer
648 views

Connection between eigenvalues of matrix and its Laplacian.

Hello! There are two definitions of graph spectrum: 1) Eigenvalues of adjacency matrix $A$. 2) Eigenvalues of Laplacian of adjacency matrix ($L$). Different sources offer different properties based ...
1
vote
1answer
143 views

The cliques of cospectral graphs

There are some facts that can be found by the spectrum of adjacency matrix of graph.For example, the number of edges and vertices, is bipartite or not, is complete multipartite or not and so on. Can ...
0
votes
2answers
305 views

Confused about orbits

I am trying to apply the main theorem of this paper to a certain kind of graph and keep getting confused. The theorem uses $rank(Aut\Gamma)$ which is defined as "the number of $Aut \Gamma$ orbits on ...
1
vote
1answer
139 views

The smallest eigenvalue from an equitable partitions

Suppose that $G$ is a connected graph with equitable partition $\pi$. Then the eigenvalues of the divisor multigraph $G / \pi$ are all eigenvalues of $G$. (Perhaps excluding some pathological cases) ...
1
vote
0answers
108 views

Lower bound for the difference between the maximum eigenvalue of a graph with the one of the one-edge-deleted subgraph

I have proposed very recently a question in the following link concerning the title of the current question: Difference of the maximum eigenvalue of a graph with the one of one-edge-deleted subgraph ...
3
votes
2answers
200 views

are there pairs of combinatorial graphs that are both isospectral and have the same matroid?

Two graphs are isospectral if the combinatorial Laplacian on them has the same spectrum, equivalently, the adjacency matrix has the same the set of eigenvalues (including multiplicities). Two graphs ...
2
votes
1answer
401 views

“Nice” eigenvectors for (square of) adjacency matrix of a bipartite graph?

Let $G$ be a bipartite graph, and let $A$ be its adjacency matrix. I was wondering in this case whether $A^2$ will have nice eigenvectors that reflect combinatorial structure of the graph. I'd be ...
1
vote
3answers
423 views

Characteristic polynomial of hypercube graph

This is probably well-known, but... Define the $n$-dimensional hypercube graph $H_n$ as having for vertices the integers between 0 and $2^n-1$, and edges between integers differing by a power of 2. ...
0
votes
1answer
253 views

Is there a closed form for the characteristic polynomial of the graph cycle (of n edges and n summits) ?

Is there a closed form for the characteristic polynomial of the graph cycle (of $n$ edges and $n$ summits)? I know it for the graph path (it is a Chebyschev polynomial), but I couldn't find a ...
2
votes
2answers
358 views

Extreme Laplacian eigenvalues

For each undirected (and unweighted) graph $G$ we define the Laplacian matrix by $L(G) = D(G)-A(G)$, where $A(G)$ should denote the adjacency matrix and $D(G)$ the diagonal matrix, where $D(G)_{ii}$ ...
6
votes
0answers
156 views

When can the Cheeger constant be well-approximated by ``Hamming balls''?

Given a graph G, the Cheeger constant is defined by $$ \DeclareMathOperator{\Vol}{Vol} h_G := \min_{S \subseteq V, \Vol S \leq (\Vol G)/2} \frac{|\partial S|}{\Vol S}. $$ Here, $\Vol S$ is the sum of ...
1
vote
1answer
143 views

a variation on the theory of equitable partitions for graphs

Assume you have a graph with an equitable partition with respect to cells $V_1,\ldots,V_n$. Accordingly, you can take the cellwise average value of a function on the node set - in other words, the ...
3
votes
1answer
250 views

Eigenvectors of asymmetric graphs

Let $G$ be an asymmetric connected graph. Then is it always the case that at least one of the eigenvectors of its adjacency matrix $A$ consists entirely of distinct entries? Thanks!
1
vote
0answers
88 views

expansion with respect to p-norms for p other than 2

Suppose I have an $d$-regular expander graph with $n$ vertices, where the stochastic version of its adjacency matrix $A$ (with entries $1/d$ and zero) has second eigenvalue $\lambda$. Let $x \in ...
5
votes
2answers
252 views

Number of trees with the same matching number

Let $\sigma(n,m)$ be the number of trees with $n$ vertices $\{ v_1, \dots, v_n \}$ such that the matching number (the size of a maximum matching) is $m$. I have been trying to compute the value of ...
3
votes
0answers
112 views

inverse M-matrix times mixed-sign vector

Recently a colleague and I came across this unusual phenomenon. Take $M\in\mathbb{R}^{n\times n}$ a singular irreducible M-matrix, and $b\in\mathbb{R}^{n}$ such that the system $Mx=b$ is solvable ...
5
votes
1answer
370 views

Repeated Second Eigenvalue of the Adjacency Matrix of a Graph

This question is motivated by a talk I went to earlier today. Suppose we have a $d$-regular graph $G$ with $n$ vertices, with adjacency matrix $A$. Let $$\lambda_1\geq \lambda_2 \geq\dots \geq ...
1
vote
1answer
126 views

In what probability does cospectra of Cayley graph imply isomorphism of the corresponding group

In what probability does cospectra of adjacent matrix of Cayley graph imply isomorphism of the corresponding group? Further more,In what probability does cospectra of adjacent matrix imply isomorphism ...
14
votes
1answer
601 views

Convexity of spectral radius of Markov operators, Random walks on non-amenable groups

Let $P_1,P_2$ denote stochastic transition matrices on a countable set $I$. Consider $P_1,P_2$ as operators on $\ell^2(I)$ given by multiplication. Question Under which conditions can we show that ...
1
vote
1answer
269 views

Simple Laplacian versus simple adjacency matrix eigenvalues

If the eigenvalues of the Laplacian matrix of a graph G are all simple, is it always the case that the eigenvalues of the adjacency matrix of G are all simple as well? Thanks in advance!
0
votes
0answers
127 views

A graph eigenvalue problem

This is motivated by a graph problem considered by me. For a directed graph $G$ on nodes ${1,\cdots,N}$, denote its graph Laplacian by $L$($l_{ij}=-1$ iff there is an directed edge $j\rightarrow i$ ...
1
vote
1answer
592 views

equitable partitions

It is well known that if $\pi$ is an equitable partition of a graph, then the spectrum of the corresponding partition matrix is a subset of the spectrum of the graph's matrix (where the matrix can be ...
4
votes
1answer
264 views

Graphs which are “distance-regular” with respect to a vertex (but not distance-regular)

A distance-regular graph (DRG) is, in essence, a graph $\Gamma$ of diameter $d$ for which there are integers $c_i, a_i, b_i, (0 \le i \le d)$ such that for all vertices $x$ of $\Gamma$ and for all ...
2
votes
2answers
546 views

Positive semidefinite decomposition, Laplacian eigenvalues, and the oriented incidence matrix

Suppose $A\in\mathbb{C}^{n\times n}$ is Hermitian and positive semidefinite with some decomposition $A=BB^*$, where $B=(b_{ij})\in\mathbb{C}^{n\times m}$ (not necessarily the Cholesky decomposition). ...
7
votes
1answer
420 views

Diophantine elements in SU(2)

Following notions from [1], call a set of elements $g_1, \dots, g_k \in G = SU(2)$ Diophantine if it satisfies the following property: there exists a constant $D$ such that for every word $W_m$ of ...
2
votes
2answers
386 views

Decomposition of $K_{10}$ in copies of the Petersen graph

It is a well-known and cute exercise in algebraic graph theory to show that $K_{10}$ cannot be written as the edge-disjoint union of three copies of the Petersen graph $P$. Indeed, the graph $G$ whose ...
2
votes
2answers
341 views

Isoperimetric dimension of Graphs.

According to the wikipedia page on "Isoperimetric dimension", the isoperimetric dimension is invariant under quasi-isometries, even between manifolds and graphs: "[...] the isoperimetric dimension is ...
8
votes
0answers
1k views

a new lower bound for the chromatic number of a graph?

Let S+(G) denote the sum of the squares of the positive eigenvalues of the adjacency matrix of a graph G. Let S-(G) denote the sum of the squares of the negative eigenvalues and q the chromatic ...
3
votes
1answer
183 views

Estimation of DS graph growth

We know that $DS$ graphs are such connected graphs that determinable by their adjacency spectrum. Suppose $DS(n)$ and $G(n)$ show the number of $DS$ graphs and all graphs with $n$ ...
2
votes
3answers
486 views

Non-isomorphic graphs with the same numbers of closed walks

Can somebody help me to construct two family of finite simple connected graph $G_i$ and $H_i$, $i=1, 2, \cdots,n$ ($n$ possibly large), such that: $1)$ $G_i‎\ncong H_i$ for $i=1, 2, \cdots, n$ $2)$ ...
4
votes
3answers
263 views

Operation on Isospectral graphs

Suppose $G$ and $H$ are two isospectral connected graphs. Can we say anything about isospectrality of graphs that obtain by binary operation between $G$ and $H$? For example,in special case, is ...
5
votes
2answers
333 views

cospectral graphs

The simple connected graph $G$ has $n$ vertices and we have: 1) $|E(G)|‎\geq‎ \frac{n(n-1)}{3}$ 2) we have the spectrum and degree sequence of $G$ 3) $Spectrum(G)=Spectrum(H)$ Is $G \cong ‎H$?
1
vote
1answer
242 views

spectrum and degree sequence

We have the spectrum and the degree sequence of one graph. Can we uniquely determine the graph with these given information?
1
vote
2answers
339 views

Lovasz theta function of circulant graphs

Let $G$ be a cirulant graph with no loops at vertices and vertex degree $d$. Is the Lovasz theta function of this graph given by: $\vartheta(G) = \max_{i}\frac{-N\epsilon_{i}}{-\epsilon_{i}+d-1}$? ...
0
votes
1answer
230 views

Lovasz theta function - uses

Lovasz theta function bounds the Shannon capacity of graphs. What are some other uses of the function - especially in asymptotic coding theory and optimization problems?