Consider a regular (multi-)graph $\Gamma$ of order $N=nv$ and degree $D=(n-1)d$ given by an adjacency matrix of the form $$ A= U_n\otimes F + (U_n\otimes F)^T, \quad (U_n)_{ij}=\begin{cases} 1 & i<j\leq n\\ 0 & \text{otherwise} \end{cases} $$ where $F$ is a $v\times v$ matrix and $U_n$ is $n\times n$ and $\otimes$ is Kronecker product. Furthermore assume the diagonal elements of $F$ are all non-zero. Let $\Omega$ be the set of all orientations of $\Gamma$. For each orientation $\omega\in \Omega$ let $\Gamma_\omega$ be resulting directed (multi-)graph. Define $$ \lambda_m(\omega)=\# \text{ of vertexes in }\Gamma_\omega \text{ with out-degree}\geq m $$ and call $\lambda(\omega)= (\lambda_1(\omega), \lambda_2(\omega)\cdots, \lambda_D(\omega))$ the type of $\omega$. Assuming one orders the vertexes of $\Gamma$ exactly as the adjacency matrix suggests, then there is one easy to describe orientation: $\omega_0$ in which an edge $ij$ will be oriented as $i\to j$ iff $i<j$. Then $$ \Lambda = \lambda(\omega_0) = \Big(\underbrace{(n-1)v, \cdots, (n-1)v}_{d\text{ times}},\underbrace{(n-2)v, \cdots, (n-2)v}_{d\text{ times}}, \cdots, \underbrace{v, \cdots, v}_{d\text{ times}}) $$

I want to show that $\Lambda\preceq \lambda(\omega)$, with dominance order, for all orientations $\omega\in \Omega$.

The question has come from physics and this suspicion is also motivated by physical evidence. These graphs come from Quantum Hall states. As long as my numerical capabilities can handle, for all the examples I could think of, this seems to hold. However it is now two months that I've been stomped by this problem. Does anybody have any suggestions on how to approach such a question?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.