Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Conjectural Brouwer Inequality for Higher-Dimensional Laplacian Spectra
59
0
0.0
(
0
)
Authors
Rediet Abebe
Ask ChatGPT about the research
No Arabic abstract
We present a generalization of Brouwers conjectural family of inequalities -- a popular family of inequalities in spectral graph theory bounding the partial sum of the Laplacian eigenvalues of graphs -- for the case of abstract simplicial complexes of any dimension. We prove that this family of inequalities holds for shifted simplicial complexes, which generalize threshold graphs, and give tighter bounds (linear in the dimension of the complexes) for simplicial trees. We prove that the conjecture holds for the the first, second, and last partial sums for all simplicial complexes, generalizing many known proofs for graphs to the case of simplicial complexes. We also show that the conjecture holds for the tth partial sum for all simplicial complexes with dimension at least t and matching number greater than $t$. Returning to the special case of graphs, we expand on a known proof to show that the Brouwers conjecture holds with equality for the tth partial sum where t is the maximum clique size of the graph minus one (or, equivalently, the number of cone vertices). Along the way, we develop machinery that may give further insights into related long-standing conjectures.
rate research
Read More
Let $a,n in mathbb{Z}^+$, with $a<n$ and $gcd(a,n)=1$. Let $P_{a,n}$ denote the lattice parallelogram spanned by $(1,0)$ and $(a,n)$, that is, $$P_{a,n} = left{ t_1(1,0)+ t_2(a,n) , : , 0leq t_1,t_2 leq 1 right}, $$ and let $$V(a,n) = # textrm{ of visible lattice points in the interior of } P_{a,n}.$$ In this paper we prove some elementary (and straightforward) results for $V(a,n)$. The most interesting aspects of the paper are in Section 5 where we discuss some numerics and display some graphs of $V(a,n)/n$. (These graphs resemble an integral sign that has been rotated counter-clockwise by $90^circ$.) The numerics and graphs suggest the conjecture that for $a ot= 1, n-1$, $V(a,n)/n$ satisfies the inequality $$ 0.5 < V(a,n)/n< 0.75.$$
We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The $k$-token graph $F_k(G)$ of a graph $G$ is the graph whose vertices are the $k$-subsets of vertices from $G$, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$. In this paper, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers $h$ and $k$ such that $1le hle kle frac{n}{2}$, the Laplacian spectrum of $F_h(G)$ is contained in the Laplacian spectrum of $F_k(G)$. We also show that the double odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph $K_n$ and the star $S_{n}=K_{1,n-1}$, respectively. Besides, we obtain a relationship between the spectra of the $k$-token graph of $G$ and the $k$-token graph of its complement $overline{G}$. This generalizes a well-known property for Laplacian eigenvalues of graphs to token graphs. Finally, the double odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph $G$ and its token graph.
In this paper, we use a new and correct method to determine the $n$-vertex $k$-trees with the first three largest signless Laplacian indices.
In this paper we prove a reverse Faber-Krahn inequality for the principal eigenvalue $mu_1(Omega)$ of the fully nonlinear eigenvalue problem [ label{eq} left{begin{array}{r c l l} -lambda_N(D^2 u) & = & mu u & text{in }Omega, u & = & 0 & text{on }partial Omega. end{array}right. ] Here $ lambda_N(D^2 u)$ stands for the largest eigenvalue of the Hessian matrix of $u$. More precisely, we prove that, for an open, bounded, convex domain $Omega subset mathbb{R}^N$, the inequality [ mu_1(Omega) leq frac{pi^2}{[text{diam}(Omega)]^2} = mu_1(B_{text{diam}(Omega)/2}),] where $text{diam}(Omega)$ is the diameter of $Omega$, holds true. The inequality actually implies a stronger result, namely, the maximality of the ball under a diameter constraint. Furthermore, we discuss the minimization of $mu_1(Omega)$ under different kinds of constraints.
We study the symmetry properties of the spectra of normalized Laplacians on signed graphs. We find a new machinery that generates symmetric spectra for signed graphs, which includes bipartiteness of unsigned graphs as a special case. Moreover, we prove a fundamental connection between the symmetry of the spectrum and the existence of damped two-periodic solutions for the discrete-time heat equation on the graph.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
