6
$\begingroup$

I study graph theory on my own using Diestel's Graph Theory book (with Algorithmic graph theory in mind). I don't understand what local property, global property, locality mean given a graph $G$.

For example, on the page 5 it says

The average degree quantifies globally what is measured locally by the vertex degrees: the number of edges of $G$ per vertex. Sometimes it will be convenient to express this ratio directly, as $\varepsilon(G) := |E|/|V|$.

In particular, I found the following phrases including the word local...

  • local information (pg. 46)
  • maximum local density (pg. 61)
  • the above local structures (pg. 101)
  • locally looks like a tree (pg. 110)
  • there is a local reason for it (pg. 110)
  • we are looking for local implications of global assumptions (pg. 181).

and many more...

Could someone explain (possibly with examples) what these local and global mean in the context of the graph theory?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

Local property - a property that relates to a specific vertex and its near neighbors. For example, the number of neighbors or 2nd order neighbors a vertex $v$ has. "locally looks like a tree" more formally could be written as the sub-graph of vertices with distance $k$ or less of the vertex $v$ is a tree.

Global property - a property that relates to the graph, like its diameter, average degree, number of connected components or even its size.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ $\Upsilon(G) = \max_{n>1}{\left[ \frac{m_n}{n-1}\right] }$, where $m_n$ is the maximum number of edges of a sub-graph on $n$ vertices. This number is defined as the arboricity of the graph $G$. This book says that "the arboricity is a measure for the maximum local density". So, $\Upsilon(G)$ is a property of a graph rather than just a single vertex. I guess by "local" it means the property of a whole sub-graph rather than a single vertex and its neighbourhood. Any idea? $\endgroup$
    – HardFork
    Commented Jan 4, 2018 at 9:28
  • $\begingroup$ $\Upsilon(G)$ is in some sense a global property. $\endgroup$
    – HardFork
    Commented Jan 4, 2018 at 9:29
  • $\begingroup$ This is not well defined, but IMO a property of a sub-graph of size n is a (borderline) local property, but a property that involves the maximal over all sub-graphs of size n is global. Arboricity is a global property. $\endgroup$
    – David Taub
    Commented Jan 4, 2018 at 9:37
  • $\begingroup$ What is not well-defined? $\Upsilon(G)$ or arboricity? $\Upsilon(G)$ is defined here and in HARARY's Graph theory book. It's also defined here. Diestel writes "the arboricity is a measure for the maximum local density". $\endgroup$
    – HardFork
    Commented Jan 4, 2018 at 10:01
  • 1
    $\begingroup$ I meant the distinction between local and global is not well defined. For example one could say a property of a sub-graph is global if the sub-graph size is large enough relative to the graph. $\endgroup$
    – David Taub
    Commented Jan 4, 2018 at 10:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.