Questions tagged [spectral-graph-theory]

Questions related to the spectrum of graphs, defined using one of the possible variants of the discrete Laplace operator or Laplacian matrix. See https://en.wikipedia.org/wiki/Discrete_Laplace_operator

Filter by
Sorted by
Tagged with
6
votes
1answer
165 views

Determinant of walk matrix for a skew-symmetric matrix of even order

Let $S=(s_{ij})$ be a skew-symmetric integral matrix of order $n$. We only consider the case that $n$ is even. Let $e$ be the all-one vector in $\mathbb{R}^n$. Define the walk matrix $$W(S)=[e,Se,\...
7
votes
1answer
374 views

Strategies for bounding the spectral norm of a tensor?

Let $A$ be a symmetric $k$-tensor over a real or complex vector field $W$. We may define its spectral norm $|A|$ by $$|A| = \sup_{v\in W} \frac{|\langle A,x^{\otimes k}\rangle|}{|x|_2^k}.$$ (...
3
votes
0answers
102 views

Spectral norm and “operator norm” for hypergraphs

Consider a $d$-regular, $k$-uniform hypergraph: the elements $S$ of its set $E$ of edges are subsets of $V$ of size $k$, and each vertex $v\in V$ is in $d$ edges. We can then define its adjacency ...
3
votes
1answer
68 views

On cospectral graphs

Is there examples of non-isomorphic cospectral graphs having Non-isomorphic automorphism groups? Isomorphic automorphism groups?
1
vote
1answer
55 views

Non-regular cospectral graphs with same degree sequences

I am looking for a large family (infinite pairs) of cospectral graphs with these condtions: The graphs are non-regular, Minimum degree is greater than $1$, The degree sequences of these cospectral ...
1
vote
0answers
35 views

What are the meaning of left singular vectors of an incident matrix?

Consider a graph G and its incident matrix $B\in R^{m\times n}$. We can compute the SVD of $B$ as $B=U^{\top}\Sigma V$. Note that the Laplacian matrix $L_G=B^{\top}B$, so the right singular vectors ...
3
votes
1answer
109 views

Reference request: Spectrum of intersection matrices

Let $P(A)$ be the set of all non-empty proper subsets of a finite set $A$. Let $M$ be a matrix indexed by the set in $P(A)$ whose $ij$ the entry is $1$ if the associated sets are disjoint and $0$ ...
0
votes
0answers
31 views

Gaussian maxima, graph connectivity, superconcentration and mean outsourcing : reference request

Consider a sequence (indexed by $n$) of centred multivariate Gaussian arrays $\{X_i\}_{i\le n}$ such that $\operatorname{Var}(X_i)=1$ for all $i$ and $\sum_{i\le n}\mathbb{E}(X_iX_j)=c_n$ for all $j$. ...
1
vote
0answers
69 views

Delocalization of eigenvectors of graph Laplacians

Let $(V,E)$ be an undirected, connected graph with $n$ nodes. The graph Laplacian is defined as $L = D - A$, where $D$ is the degree matrix and $A$ is the adjacency matrix. Let $0 = \lambda_1 < \...
33
votes
1answer
464 views

Which graphs on $n$ vertices have the largest determinant?

This is a question that seems like it should have been studied before, but for some reason I cannot find much at all about it, and so I am asking for any pointers / references etc. The determinant of ...
1
vote
0answers
82 views

Varieties determined by a characteristic-type of polynomial with the structure of an underlying graph

While writing my master thesis, following problem came up: Given a digraph $G$ with edges $e_1,..,e_n$ and a given a $n\times n$- matrix $A\in\mathbb{C}^{n\times n}$ such that $A_{ij}=0$ if the ending ...
2
votes
0answers
35 views

Formulas to determine the value of graph energy with addition or deletion of edges

If $G$ is a graph, then the graph energy of $G$ denoted by $E(G)$ is defined as the sum of absolute values of eigenvalues of the adjacency matrix of $G$. It is known that $E(G)\geq E(G-v)$, where $ ...
0
votes
0answers
42 views

How can I find family of non-isomorphic graphs with specific properties?

I asked this question: How to find non-isomorphic graphs with specific orders? Two new questions have arisen for me. I have a graph, $G$, with $2n$ vertices. It has one connected component of order $...
3
votes
1answer
126 views

How to find non-isomorphic graphs with specific orders?

I work on a problem in my research. I have a graph, $G$, with $2n$ vertices. It has one connected component of order $2n-1$ and an isolated vertex. $\lambda_1\geq \lambda_2\geq \ldots \geq \lambda_{2n}...
0
votes
0answers
97 views

Closed non-backtracking walks and eigenvalues of the adjacency matrix in non-regular graphs

Let $\Gamma$ be an undirected finite graph. Write $M_r$ for the number of non-backtracking closed walks of length $r$ in $\Gamma$, i.e., walks where a step is never followed by its inverse. Let $A$ be ...
2
votes
0answers
136 views

Closed geodesics and eigenvalues in a non-regular graph

Let $\Gamma$ be an undirected graph the degree of whose $n$ vertices is $\leq D$ without necessarily being constant. Say we have bounds of type $\leq \gamma^{2 k}$ for the number of closed geodesics ...
0
votes
1answer
65 views

If there are eigenvectors with largest components $i$ resp. $j$, then is there an eigenvector with two largest components $i$ and $j$?

Let $G=(V,E)$ be a connected (finite simple) graph with vertex set $V=\{1,...,n\}$ and let $\theta_2\in\Bbb R$ be the second-largest eigenvalue of its adjacency matrix. I wonder about the following ...
2
votes
0answers
61 views

The rank of a Laplacian-type matrix

Suppose that $M$ is an integer, symmetric matrix of order $n>2$ with the positive integers $K_1,\dotsc,K_n$ on its main diagonal, and with all the off-diagonal elements equal to $0$ or $1$ so that ...
13
votes
1answer
336 views

$\ell^1$-norm of eigenvectors of Erdős-Renyi Graphs

Setting. Let $G(n,p)$ denote the usual Erdős-Renyi (random) graphs. For each such graph there is an associated Laplacian matrix $L = D - A$ where $D$ collects the degrees on the diagonal and $A$ is ...
0
votes
0answers
68 views

How is the second smallest eigenvalue of normalized laplacian bounded for random graphs?

It is well known that for any graph G following holds $\frac{\lambda_2}{2} ≤ \phi(G) ≤ \sqrt{2\lambda_2}$, where $\phi(G)$ is the conductance of the graph and $\lambda_2$ is the second smallest ...
4
votes
0answers
125 views

Relation between two conjectures on reconstruction of graphs

In spectral graph theory, there is a conjecture that claims: Almost every graph is determined by its adjacency spectrum ($DS$). This conjecture belongs to professor Willem Haemers. Also, we have a ...
3
votes
1answer
92 views

Spectral properties of half-transitive graphs

The half-transitive graphs form a curious class of graphs with some kind of intermediate symmetry that is non-trivial to achieve. More precisely, a graph is half-transitive if its symmetry group is ...
11
votes
1answer
330 views

Is there Matrix-Tree theorem for counting the bases of a connected matroid?

The famous Kirchhoff's Matrix-Tree theorem counts the number of spanning trees of a connected graph, that is, the number of bases of its cycle matroid. But it appeals to vertices, that's why I do not ...
71
votes
4answers
8k views

What are good mathematical models for spider webs?

Sometimes I see spider webs in very complex surroundings, like in the middle of twigs in a tree or in a bush. I keep thinking “if you understand the spider web, you understand the space around it”. ...
2
votes
0answers
103 views

Expansion of random subgraphs of a bi-regular bipartite graph

Let $G = (L, R, E)$ be a bi-regular bipartite graph, with $|L|=n$ and $|R| = C \cdot n$, where $C$ is a large constant. Let $d$ be its (constant) right-degree. We know $G$ is a good spectral expander. ...
23
votes
5answers
1k views

Factorization of the characteristic polynomial of the adjacency matrix of a graph

Let $G$ be a regular graph of valence $d$ with finitely many vertices, let $A_G$ be its adjacency matrix, and let $$P_G(X)=\det(X-A_G)\in\mathbb{Z}[X]$$ be the adjacency polynomial of $G$, i.e., the ...
3
votes
1answer
223 views

Sums over products over short paths in an expander graph

Let $\Gamma=(V,E)$ be an undirected graph of degree $d$. (Say $d$ is a large constant and the number of vertices $n=|V|$ is much larger.) Let $W_0$ be the space of functions $f:V\to \mathbb{C}$ with ...
3
votes
0answers
243 views

Eigenvalue bounds and triple (and quadruple, etc.) products

Very basic and somewhat open-ended question: Let $A$ be a symmetric operator on functions $f:X\to \mathbb{R}$, where $X$ is a finite set. Assume that the $L^2\to L^2$ norm of $A$ is $\leq \epsilon$, i....
10
votes
1answer
627 views

Eigenvalues of the complement of a graph

Let $A$ and $\widetilde A$ be the adjacency matrices of a graph $G$ and of its complement, respectively. Is there any relation between the eigenvalues of $A + \widetilde A$ and the eigenvalues of $A$ ...
17
votes
1answer
298 views

Graph embeddings in the projective plane: for the 35 forbidden minors, do we know their Colin de Verdière numbers?

The Graph Minor Theorem of Robertson and Seymour asserts that any minor-closed graph property is determined by a finite set of forbidden graph minors. It is a broad generalization e.g. of the ...
54
votes
5answers
4k views

Intuitively, what does a graph Laplacian represent?

Recently I saw an MO post Algebraic graph invariant $\mu(G)$ which links Four-Color-Theorem with Schrödinger operators: further topological characterizations of graphs? that got me interested. ...
0
votes
0answers
28 views

Spectral gap of continuous-time Markov chain on nonnegative integers: The geometric long indel length chain

Let $S=\mathbb Z_{\ge0}$ be the nonnegative integers, and let $T=\mathbb R_{\ge0}$ be the nonnegative real numbers. Next, let $\gamma\in(0,1),r\in(0,1),$ and let $Q=(Q_{n,m})_{n,m\in S}$ be such that ...
5
votes
1answer
232 views

Finding zero-one vectors in the row space of a matrix

Suppose that $M$ is a square matrix with all elements on its main diagonal equal to $1$, and every row containing exactly two off-diagonal elements equal to $-1$; all other elements are equal to $0$. ...
11
votes
2answers
292 views

Suggestion for framing a course in Representation theory + Spectral graph theory

I am going to give a course in spectral graph theory to graduate students. I want to learn and teach the connection between the spectral graph theory and the representation theory of finite groups. I ...
1
vote
2answers
142 views

From one eigenvector to many, in a very local graph?

Let $\Gamma$ be an undirected graph of bounded degree $d$ with $V = \{1,2,\dotsc,N\}$ as its set of vertices, and edges only between vertices that are at a distance $\leq M$ apart (where $M$ is much ...
25
votes
2answers
637 views

Algebraic graph invariant $\mu(G)$ which links Four-Color-Theorem with Schrödinger operators: further topological characterizations of graphs?

30 years ago, Yves Colin de Verdière introduced the algebraic graph invariant $\mu(G)$ for any undirected graph $G$, see [1]. It was motivated by the study of the second eigenvalue of certain ...
3
votes
0answers
107 views

Chromatic number of regular graphs using spectra

There exist inequalities relating the maximum and minimum eigenvalues of the adjacency matrix of a graph with its chromatic numbers, i.e. the Wilf's and Hoffmann's inequalities, which put together ...
9
votes
2answers
174 views

Conjecture of van der Holst and Pendavingh related to bound for Colin de Verdière invariant

In their 2009 paper (“On a graph property generalizing planarity and flatness”. In: Combinatorica 29.3 (May 2009), pp. 337–361. issn: 1439-6912. doi: 10.1007/s00493-009-2219-6.), van der Holst and ...
5
votes
0answers
89 views

Closed paths, closed trails and traces

Let $A$ be the adjacency matrix of a (non-oriented) graph $\Gamma$. Then $\textrm{Tr} A^k$ equals both the sum $\sum_i \lambda_i^k$ of $k$th powers of eigenvalues of $A$, on the one hand, and the ...
0
votes
0answers
76 views

How to compute the sum of a product of eigenvalues, $\sum_{k=1}^n \lambda_k \lambda'_k$

$\DeclareMathOperator\Cay{Cay}$$G$ is an abelian group of order n. Let $\Gamma_1=\Cay(G,S_1)$ and $\Gamma_2=\Cay(G,S_2)$. (Here, $S$'s are symmetric subsets of $G$ such that $S=S^{-1}$ and $1\notin S$,...
4
votes
1answer
123 views

Digraphs with unique walk of length $k$ between any two vertices

Let $G$ be a digraph such that there is an unique directed walk of length $k$ between any two vertices. Equivalently, if $A$ is the adjacency matrix of $G$, then $A^k$ is the matrix with all entries $...
1
vote
0answers
44 views

Cheeger constant of truncated hypercube

Look at the $d$-dimensional hypercube and truncate it. This means one replaces each vertex by a cycle (of length $d$) in such a way the the new graph is 3-regular. Question 1: What is the asymptotic ...
4
votes
1answer
111 views

Relation between Kirchhoff's Circuital law and Matrix tree Theorem

I'm not a professional mathematician, just an undergraduate student. I was reading Introduction to Graph Theory by West, I came over the topic which discuses the methods to find the spanning trees in ...
4
votes
1answer
165 views

An eigenvalue upper bound for 1-walk-regular graphs

Let $G$ be a graph and suppose that $G$ is 1-walk-regular (or, if you prefer, vertex- and edge-transitive, or distance-regular). Let $\theta_1>\theta_2>\cdots>\theta_m$ be the distinct ...
2
votes
0answers
32 views

Antipodal vertices in spectral graph embeddings

Suppose your are given an antipodal graph $G=(V,E)$, that is, for every vertex $v\in V$ there is a unique maximally distant vertex $v'\in V$. Under which condistions does the following hold: If $\...
2
votes
1answer
98 views

Gaussian bounds with exponential decay for discrete (graph) Dirichlet heat kernel

Let $\Omega$ be a finite, connected subset of $\mathbb{Z}^n$, $W_t$ a standard random walk on $\mathbb{Z}^n$ started at $x$, and $T_\Omega$ the first time at which $W_t$ leaves $\Omega$; consider $$ P^...
5
votes
2answers
337 views

Fiedler vector, what else?

In the spectral analysis of a graph with 1 connected component, the first non-trivial eigenvector (corresponding to the non-zero smallest eigenvalue) is also called the Fiedler vector. This vector is ...
4
votes
1answer
249 views

Closed paths, traces and spectra

Let $\Gamma$ be a graph. Write $A$ for its adjacency matrix. It is trivial to show that $\mathrm{Tr} A^k$ equals the number of closed walks of length k, that is, the number of $k$-step walks that ...
2
votes
0answers
59 views

Upper bound for smallest eigenvalue of infinite family of graphs

Let $\left\{G_{n}\right\}_{n=1}^{\infty}$ be a sequence of regular simple connected graphs with at least one edge such that $G_i$ is an induced sub-graph of $G_{i+1}$ and is not equal to $G_{i+1}$. ...
1
vote
1answer
123 views

Cayley graphs on $Z_{11}$ and $Z_p$

I want to find all cayley graphs on $Z_{11}$. I know how many connected cayley graphs exist but i want to find all of them, connected or not, to find their eigenvalues. I found some of them and a ...

1
2 3 4 5
7