Welcome to MathOverflow

Question

3

Let $\mathcal{G}$ be the set of all infinite connected graphs with the following properties:

Every vertex has $4$ neighbors
For every vertex, there are $8$ vertices that have distance exactly $2$ from it.
For every vertex, there are $12$ vertices that have distance exactly $3$ from it.
...
For every vertex, there are $4n$ vertices that have distance exactly $n$ from it.
...

In other words, the size of any ball of radius $r$ is required to be $r^2+(r+1)^2$. As an example, the infinite square grid is an element of $\mathcal{G}$.

Let $\mathcal{G}_r$ be the set of radius $r$ balls that occur as subgraphs of graphs in $\mathcal{G}$.

Is there a nice (efficient) way to randomly produce graphs in $\mathcal{G}_r$, such that every graph in $\mathcal{G}_r$ has a nonzero chance of being produced?

flag	asked Nov 25 2011 at 20:57 zeb 3,321●1●12●24

	Other than the square lattice, do you know how to generate such graphs? Do you have some sort of generating function for their number as a function of $r?$ – Igor Rivin Nov 25 2011 at 21:59
	Are the elements of $\mathcal{G}$ simple graphs? That is, do they allow multiple edges? – Dimitrije Kostic Nov 25 2011 at 22:13
	Perhaps I'm wrong, but why not try this first, and then go for efficiency after you understand the classes G_r better? This is: randomly generate the graph g_r, where g_0 is a single vertex, and for g_r+1 create the set D of 4(r+1) vertices, assign each vertex at least 1 and possibly more edges to random vertices in "the previous 4r" vertices of g_r, and then wire up D with more edges as you like? Once you understand how those look, you can try enumerating isomorphism types and generating those efficiently, at least for small r. Gerhard "Ask Me About System Design" Paseman, 2011.11.25 – Gerhard Paseman Nov 25 2011 at 22:26
	The above class of graphs g_r is strictly larger than what you have, so use the above class and then weed out those which obviously violate one of your desired properties. Once you see how to do that for small r, you can tell us how you do it and then we might be able to improve on the efficiency of your implementation. Gerhard "Ask Me About System Design" Paseman, 2011.11.25 – Gerhard Paseman Nov 25 2011 at 22:30
	@Igor - I don't know any good ways of generating such graphs other than trying all possibilities. I suspect that the square grid is the only Cayley graph with this property, but I haven't proved it (but if I understand correctly, any group with quadratic growth is virtually abelian, so maybe it isn't very hard to check this). – zeb Nov 26 2011 at 0:38

show 3 more comments

Gerhard Paseman · Answer 1 · 2011-12-02 19:28:54Z UTC

As (up to isomorphism, and changing font) $G_0$ has 1 member and $G_1$ has 4, I leave it to the poster how to implement random selections from these classes. That should be straightforward.

I am about to turn enumerating $G_2$ over to a computer, after spending hours trying it by hand.

My chief challenge in attempting the enumeration was to wire up the 8 distance two neighbors to each other in a way that the results could be extended to a member of $G_3$. If I ignore that I have (not an exact number) on the order of 50 nonisomorphic candidates each of which could produce potentially thousands (more specifically, O(28 choose 6)) of members of $G_2$.

Something that may work efficiently by computer for which I have trouble attempting by hand is stitching: there are 4 nonisomorphic members of $G_1$, and you can try stitching such members together in all possible ways to form larger subgraphs of members of $G_2$ or $G_3$. Be sure to check that you don't put in too many distance k neighbors when doing so.

If it turns out that stitching yields a small number (less than a thousand) of members of $G_2$, then it may be computationally feasible to enumerate $G_3$. Until I see an enumeration of $G_2$, any further guesses I make on this are essentially wild speculation.

Gerhard "Real Hand-stitching Is Even Harder" Paseman, 2011.12.02

Gerhard Paseman · Answer 2 · 2012-01-11 17:50:26Z UTC

Here is an alternate suggestion which should yield a reasonable upper bound on the size of $G_2$, and may provide the basis of an estimate for the size of $G_3$.

Any member of $G_2$ will be contained in the following class $C$ of graphs on 13 vertices: 5 vertices, which I call the core, will form one of the subgraphs listed in $G_1$, with 8, 10, or 12 edges going from the same 4 vertices of the core to the 8 vertices I call the rim, with an additional 0 up to 6 edges between the vertices of the rim, with every vertex having degree at most 4, and every vertex in the rim being adjacent to at least one of the 4 outer vertices of the core.

It is mildly tedious but not hard to list up to isomorphism those members of $C$ with 0 edges in the rim; there are less than 50 such representatives, which I shall group into a subclass called $C0$. Now let $i$ be an integer in the range from 0 to 5 and suppose we have the class $Ci$ of graphs which contain all isomorphism types (possibly with some duplication) of members of $C$ which have $i$ edges in the rim. Add a single edge in all possible ways to each member of $Ci$ and determine which such graphs are isomorphic, and this will form the class $Cj$, where $j=i+1$. Some candidates made this way will have to be rejected if, e.g., a vertex gets degree 4 or more.

I suspect that $C1$ will have fewer than 100 members, and that each subclass will have less than 10 times as many members as the previous subclass, except for $C5$ and $C6$, because of the symmetries involved. There will also be conditions to check on the small neighborhoods of each vertex, and there will be interesting restrictions when passing to $G_3$ which may exclude some members of $C$ from being in $G_2$.

I will attempt an exact enumeration of $C0$, $C1$, and $C2$ by hand. I make this post because I am not ready to write or borrow a graph isomorphism subroutine to implement in my current computing environment. This task of enumerating the $Ci$ by computer should be pie for anyone proficient in graph enumeration. Even having good estimates for $C3$ and $C4$ will be of use, should someone wish to take on a limited version of the task.

Gerhard "Ask Me About System Design" Paseman, 2012.01.11

Can you randomly sample graphs with quadratic growth?

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

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.