Asymptotic Geodesic Flow on Planar Graphs

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

Assume you have a simple and infinite graph. Choose $x_{0}$ an arbitrary vertex and consider $$G_{n}:=\{x\in G:d(x_0,x)\leq n\}$$ with the graph metric (hop metric). Now for each pair of nodes there is a unit flow that travels through the minimum path between nodes (if there is more than one minimum path it splits equally along all such paths). The total flow in $G_{n}$ is equal to $|G_{n}|^2$.

Given a node $v\in G_{n}$ we define $T_{n}(v)$ as the total flow generated in $G_{n}$ passing through $v$. In other words, $T_{n}(v)$ is the sum off all the geodesic paths in $G_{n}$ which are carrying flow and contain the node $v$. Let $M_{n}$ be the maximum flow $$M_{n}(v):=\max_{v\in G_{n}}{T_{n}(v)}.$$ For any graph $|G_{n}|\leq M_{n}\leq |G_{n}|^2$. It is not very difficult to see that for $G=\mathbb{Z}^2$ $$M_{n}=O(|G_{n}|^{3/2}).$$

My question is: can we do better than this in a planar graph? In other words, does there exist a infinite planar graph $G$ such that $M_{n}=o(|G_{n}|^{3/2})$? If so, how low we can go.

Note that the same problem could be reformulated by instead of having an infinite graph $G$ having a sequence of graphs $\{G_{n}\}$ such that $|G_n|\to\infty$.

-

1 Answer

You can't do better. Lipton and Tarjan's planar separator theorem says that any $n$-node planar graph $G=(V,E)$ contains a set $S$ of $O(\sqrt{n})$ vertices whose removal separates the graph into components all of which have size at most $2n/3$. We can then partition $V \setminus S$ into sets $X,Y$ each containing at least $(1/3-o(1))n$ vertices; there are order $n^2$ pairs $(u,v) \in X \times Y$, and any path between such a pair $(u,v)$ contains a vertex of $S$. Since $|S|=O(\sqrt{n})$, by the pigeonhole principle it follows that some element of $S$ is in order $n^{3/2}$ paths. between $X$ and $Y$.

-

1
And this works for any flow, not just geodesic. – Ori Gurel-Gurevich Feb 20 2012 at 2:33
Thanks Louigi! It makes total sense. – ght Feb 20 2012 at 2:57
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 35, "mathjax_display_tex": 3, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9430304765701294, "perplexity_flag": "head"}