Isoperimetric inequality for exclusion process on a cycle

55 Views Asked by At

Consider $n$ sites on a cycle and $n/2$ indistinguishable particles occupying $n/2$ of these sites such that no two particles are at the same site. Consider a graph $G(V,E)$ where $V$ is the set of all configurations of particles on the cycle, so $|V|={n \choose n/2}$. There is an edge $(w,w')\in E$ between two configurations $w,w'\in V$ if we start from $w$ and can move any of it's particles to it's adjacent site (only if the adjacent site is unoccupied) and end up with $w'$.

I'm looking at finding a lower bound for the function:$$f(r)=\min_{A\subset V, |A|\leq r} \frac{\partial(A)}{|A|}$$

where $\partial(A)$ is the edge boundary of $A$ i.e. $\partial(A)=\{(w,w')\in E:w\in A, w'\in A^c\}$

The bound clearly depends on $n$ and $r$. It's a hard problem and not sure how to approach it. For small $r$, the ratio above is minimized for configurations where particles stick close to each other. But I'm not sure about a general bound. I know that, by Cheeger's inequality, a lower bound of $\lambda_1/2$, where $\lambda_1$ is the least non-trivial eigenvalue of the normalized Laplacian of $G$, for $|A|\leq n/2$ is obtained but I'm looking for a better lower bound which uses the geometry of the problem in question.

1

There are 1 best solutions below

10
On BEST ANSWER

This is not a full answer, but I noticed three observations about the graph $G$ that may help give some rough bounds (I am assuming that you are only consider even cycles $C_{2k}$ for your base space). Let us call the base cycle $C$, the configuration graph $G$, and let $n=2k$. We also assume $k>2$ (this one case can be analysed on its own, and is somewhat degenerate). In a given vertex configuration $w$, let the subgraph of the base cycle $C$ induced by the particles be called $H_w$ (so $H_w$ is a collection of paths of $C$ formed by the $k=\frac{n}{2}$ particles). Last piece of notation, let $c(w)$ be the number of connected components (i.e., paths) in $H_w$. See the diagram for an example.

enter image description here

Some `semi-obvious' things to note are as follows.

Observation 1: Each vertex $w$ in the configuration graph $G$ has degree in $\{2,4,6,\dots, n\}$. To see this, observe that $H_w$ consists of at most $k$ paths ($1\leq c(w)\leq k$). There is one allowed move for each end of a path, so we get that the degree of $w$ in $G$ is given by $deg(w) = 2\cdot c(w)$.

More importantly for finding a bound, there is also a `continuity condition' on the vertex degrees:

Observation 2: If $w$ and $x$ are adjacent configurations in $G$, then $|c(w)-c(x)|\leq 1$: Each move to a particle does exactly one of the following things:

  1. A move can split an end vertex off one path and into `empty space', increasing the number of paths by $1$.
  2. A move can split a vertex off one path, and attach it to another, making $0$ change to the path number.
  3. A move can attach an isolated particle to a path, decreasing the paths by $1$.
  4. An isolated vertex can be moved such that it does not attach to a path, making $0$ change to the number of paths.

Observation 3: the graph $G$ is bipartite. So if you wanted to find sets $A$ minimising $\frac{\partial(A)}{|A|}$, you'd want to be careful about how you spread the sets over the bipartition.

The proof of this (that I can find at least) is non-trivial, and there's likely an easier argument. We show that any cycle $\Omega$ in $G$ has even length. It suffices to show that if we start at a configuration $w$, and make a sequence of $l$ moves $\Omega: w= w_0, w_1, \dots, w_{l-1}, w_0$ that return to $w$, then $l = 0 \pmod 2$. We can think of each move as moving exactly 1 particle along the cycle $C$. Let $S = \{u_1, u_2, \dots, u_k\}$ be the set of $k$ vertices of $C$ occupied by a particle in configuration $w=w_0$, and label the particles $p_i$ such that particle $p_i$ occupies vertex $u_i$ in $w$. Note that a particle $p_i$ does not necessarily start and end the sequence of moves on the same vertex, but all the same vertices $S$ are occupied by some particle at the end of the sequence $\Omega$. Thus we can think of the sequence of moves $\Omega$ as giving a bijection $f:S \rightarrow S$ such that the particle $p_i$ starts at the vertex $u_i$, and ends at $f(u_i)$.

Let $m_i$ be the number of times that particle $p_i$ is moved in the sequence $\Omega$, and observe that

$$\sum m_i = \ell$$

Since each step of $\Omega$ moves exactly one particle.

Because the base cycle $C_{2k}$ is an even cycle, and moves can only push a particle clockwise or counterclockwise exactly one place around the cycle, we observe that $$m_i = d(u_i, f(u_i)) \pmod 2$$

Thus we deduce that $$l = \sum_{u_i \in S} d(u_i, f(u_i)) \pmod 2$$

By a bunch of case checking, it is not too hard to verify that if $h,g: S\rightarrow S$ are both bijections from $S$ to itself, then:

$$d(u_i, gh(u_i)) = d(u_i, h(u_i)) + d(h(u_i), gh(u_i)) \pmod 2$$

From which it follows that

$$\sum d(u_i, gh(u_i)) = \sum d(u_i, h(u_i)) + \sum d(h(u_i), gh(u_i)) \pmod 2$$

Note that the bijection $f$ can be written as a composition of some number of Transpositions (i.e., we can see $f$ as just being a bunch of swaps of vertices). It is easy to observe that for a transposition $t: S\rightarrow S$ that swaps two vertices $u_i$ and $u_j$ that:

$$\sum d(u_i, t(u_i)) = d(u_i,u_j) + d(u_j,u_i) = 2d(u_i,u_j) = 0 \pmod 2$$

Thus the `distance sum' of $f$ is itself $0 \pmod 2$, so $l = 0 \pmod 2$, and thus $\Omega$ must be an even cycle in $G$, so $G$ is bipartite.

All in all this doesn't yield a full bound, but does hopefully give something to work with. Given that the vertices of degree $2$ in $G$ form an independent set, I'd bet that for $r\leq n$, you can show that $f(r) = 2$ exactly, but I'm not sure how to prove this.