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
-
To model reactive power limited generators within power flow problems, PV-PQ switching fixes generator voltages when reactive power outputs are within limits but allows the voltages to vary with a constant reactive power injection when limits are reached. Power flow algorithms often use heuristics that iteratively modify the generators’ PV versus PQ representation as the algorithm executes. The convergence behavior and speed of power flow algorithms with these heuristics significantly depend on their initialization. To improve computational performance, we propose an approach for using neural networks to initialize PV-PQ switching heuristics. After offline training where the neural networks learn the power flow solution’s PV vs. PQ generator statuses across varying load demands, the neural networks are deployed to initialize power flow algorithms in online applications. Numerical results demonstrate the effectiveness of this approach with speedup factors of 1.55× to 4.32× over the nominal generator PV-PQ status initialization.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.37236/9768
