An official website of the United States government
Let $$\Gamma$$ be a finite group acting transitively on $$[n]=\{1,2,\ldots,n\}$$, and let $$G=\mathrm{Cay}(\Gamma,T)$$ be a Cayley graph of $$\Gamma$$. The graph $$G$$ is called normal if $$T$$ is closed under conjugation. In this paper, we obtain an upper bound for \textcolor[rgb]{0,0,1}{the second (largest) eigenvalue} of the adjacency matrix of the graph $$G$$ in terms of the second eigenvalues of certain subgraphs of $$G$$ (see Theorem 2.6). Using this result, we develop a recursive method to determine the second eigenvalues of certain Cayley graphs of $$S_n$$ and we determine the second eigenvalues of a majority of the connected normal Cayley graphs (and some of their subgraphs) of $$S_n$$ with $$\max_{\tau\in T}|\mathrm{supp}(\tau)|\leq 5$$, where $$\mathrm{supp}(\tau)$$ is the set of points in $[n]$ non-fixed by $$\tau$$.
more »
« less
Computing Volumes of Adjacency Polytopes via Draconian Sequences
Adjacency polytopes appear naturally in the study of nonlinear emergent phenomena in complex networks. The ``"PQ-type" adjacency polytope, denoted $$\nabla^{\mathrm{PQ}}_G$$ and which is the focus of this work, encodes rich combinatorial information about power-flow solutions in sparse power networks that are studied in electric engineering. Of particular importance is the normalized volume of such an adjacency polytope, which provides an upper bound on the number of distinct power-flow solutions. In this article we show that the problem of computing normalized volumes for $$\nabla^{\mathrm{PQ}}_G$$ can be rephrased as counting $D(G)$-draconian sequences where $D(G)$ is a certain bipartite graph associated to the network. We prove recurrences for all networks with connectivity at most $$1$$ and, for $$2$$-connected graphs under certain restrictions, we give recurrences for subdividing an edge and taking the join of an edge with a new vertex. Together, these recurrences imply a simple, non-recursive formula for the normalized volume of $$\nabla^{\mathrm{PQ}}_G$$ when $$G$$ is part of a large class of outerplanar graphs; we conjecture that the formula holds for all outerplanar graphs. Explicit formulas for several other (non-outerplanar) classes are given. Further, we identify several important classes of graphs $$G$$ which are planar but not outerplanar that are worth additional study.
more »
« less
- PAR ID:
- 10353223
- Date Published:
- Journal Name:
- The Electronic Journal of Combinatorics
- Volume:
- 29
- Issue:
- 1
- ISSN:
- 1077-8926
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Let $$\Gamma$$ be a finite group acting transitively on $$[n]=\{1,2,\ldots,n\}$$, and let $$G=\mathrm{Cay}(\Gamma,T)$$ be a Cayley graph of $$\Gamma$$. The graph $$G$$ is called normal if $$T$$ is closed under conjugation. In this paper, we obtain an upper bound for \textcolor[rgb]{0,0,1}{the second (largest) eigenvalue} of the adjacency matrix of the graph $$G$$ in terms of the second eigenvalues of certain subgraphs of $$G$$ (see Theorem 2.6). Using this result, we develop a recursive method to determine the second eigenvalues of certain Cayley graphs of $$S_n$$ and we determine the second eigenvalues of a majority of the connected normal Cayley graphs (and some of their subgraphs) of $$S_n$$ with $$\max_{\tau\in T}|\mathrm{supp}(\tau)|\leq 5$$, where $$\mathrm{supp}(\tau)$$ is the set of points in $[n]$ non-fixed by $$\tau$$.more » « less
-
Let $$G$$ be a finite group acting transitively on $$[n]=\{1,2,\ldots,n\}$$, and let $$\Gamma=\mathrm{Cay}(G,T)$$ be a Cayley graph of $$G$$. The graph $$\Gamma$$ is called normal if $$T$$ is closed under conjugation. In this paper, we obtain an upper bound for the second (largest) eigenvalue of the adjacency matrix of the graph $$\Gamma$$ in terms of the second eigenvalues of certain subgraphs of $$\Gamma$$. Using this result, we develop a recursive method to determine the second eigenvalues of certain Cayley graphs of $$S_n$$, and we determine the second eigenvalues of a majority of the connected normal Cayley graphs (and some of their subgraphs) of $$S_n$$ with $$\max_{\tau\in T}|\mathrm{supp}(\tau)|\leqslant 5$$, where $$\mathrm{supp}(\tau)$$ is the set of points in $[n]$ non-fixed by $$\tau$$.more » « less
-
Abstract We considerG, a linear algebraic group defined over$$\Bbbk $$, an algebraically closed field (ACF). By considering$$\Bbbk $$as an embedded residue field of an algebraically closed valued fieldK, we can associate to it a compactG-space$$S^\mu _G(\Bbbk )$$consisting of$$\mu $$-types onG. We show that for each$$p_\mu \in S^\mu _G(\Bbbk )$$,$$\mathrm {Stab}^\mu (p)=\mathrm {Stab}\left (p_\mu \right )$$is a solvable infinite algebraic group when$$p_\mu $$is centered at infinity and residually algebraic. Moreover, we give a description of the dimension of$$\mathrm {Stab}\left (p_\mu \right )$$in terms of the dimension ofp.more » « less
-
Graph neural networks (GNNs) have achieved lots of success on graph-structured data. In light of this, there has been increasing interest in studying their representation power. One line of work focuses on the universal approximation of permutation-invariant functions by certain classes of GNNs, and another demonstrates the limitation of GNNs via graph isomorphism tests. Our work connects these two perspectives and proves their equivalence. We further develop a framework of the representation power of GNNs with the language of sigma-algebra, which incorporates both viewpoints. Using this framework, we compare the expressive power of different classes of GNNs as well as other methods on graphs. In particular, we prove that order-2 Graph G-invariant networks fail to distinguish non-isomorphic regular graphs with the same degree. We then extend them to a new architecture, Ring-GNN, which succeeds in distinguishing these graphs as well as for tasks on real-world datasets.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.37236/9768
