Existence of a big connected component in a planar graph

130 Views Asked by At

Let $G$ be a connected finite subgraph of $\mathbb{Z}^2$. We know that we can define the dual graph $G^{\ast}$ of $G$ having vertices the faces of $G$ and edges between two vertices at distance $1$ that are lying in the same face. Let $0,x\in G$ and let $\gamma$ be (one of the) the shortest path joining $0$ to $x$, of length $n$. I am wondering if one can say something along the lines of : There exists a dual (that is, a connected component of $G^{\ast}$) connected component (equivalently, a face of $G$) of size greater or equal to $n/2$, or maybe $n/4$ ?

I think that the result is true but I have no idea how to utilize the fact that $\gamma$ is minimal in order to conclude. If $\gamma$ only uses edges going in the direct $x\cdot \vec{e_1}$ or $x\cdot \vec{e_2}$, then I can juste take the dual boundary of $G$, which is connected and has length $\geq 2n$. But if $\gamma$ is highly suboptimal (doing "U-turns" and things like that), then the dual boundary does not suffice and I am stuck. Also, do we have similar result in higher dimensions ?

Edit : Here $\mathbb{Z}^2$ is the square lattice. The definition of the dual graph I use here is the one commonly used in percolation. We define the dual graph of $\mathbb{Z}^2$ to be the graph having vertex set $$V((\mathbb{Z}^2)^{\ast})= V(\mathbb{Z}^2+\frac{1}{2}\mathbb{Z}^2),$$ which means that each face of the square lattice is a vertex of the dual graph. We add an edge between two adjacent faces, which means that $(\mathbb{Z}^2)^{\ast}$ is a translated of $\mathbb{Z}^2$. We then define the dual of any subgraph $G$ of $\mathbb{Z}^2$ to be the graph with dual edges (that is, edges in $(\mathbb{Z}^2)^{\ast}$) that correspond to edges of $\mathbb{Z}^2\setminus G$ having at least one endpoint in $G$.

The dual of a line consisting of $n$ edges is therefore a (dual) path that "contains" the line. In this case it would correspond to the "boundary" of the line in $\mathbb{Z}^2$

Thanks to anyone who can help me :)

1

There are 1 best solutions below

0
On

In the following graph, the biggest face scales with a size of $\mathcal{O}(\sqrt{n})$ compared to length of the shortest path between $A$ and $B$

enter image description here