6
$\begingroup$

Suppose that on an $n \times n$ square grid, we place edges as we typically would to form unit squares (horizontal, vertical edges on each vertex.) The question is: if we remove $k$ points, how many ways are there to do this so that the graph is still connected? (Let's just agree to call the resulting graph after the removal of $k$ vertices an end graph.)

For ease of discussion, let the vertices be given by Cartesian co-ordinates, starting with $(0,0)$ and ranging up until $n-1$ on the $x-y$ axis (first quadrant.)

To make clear what the problem is:

  1. If a vertex is removed, so is every edge connected to it.

  2. it matters what kind of graph is left after the vertex removals. Perhaps to clarify this point: say we are removing $n^2-1$ vertices. Then there are $n^2$ ways to do this [the vertices are labelled.]

  3. The order in which the vertices are removed does not matter.

  4. You must remove precisely $k$ vertices, so I'm not asking to count the removal of $j \leq k$ vertices.

Are there any known methods known for this sort of counting?

the following is some of the work I've done thus far:

If $k=2$ with $n>2$, I reasoned that the number of ways is $\binom{n^2}{2}-4$, since you can always "clip off a corner."

the following is incorrect: However, the situation changes for $k=3$, since there are different ways of taking off a corner that leaves an isolated vertex (or even $3$ vertices.) In particular, I noticed that there are $3$ ways to clip off a corner, so we can take $\binom{n^2}{3}-4\cdot 4$ as the possible number of ways.

Is it sensible to anticipate an explicit or recursive formula, in general?

Update It appears as though I've only been considering cases where the vertices being removed could be "drawn", or that each choice of vertex was adjacent to one already chosen (vertically, horizontally, or diagonally.) Otherwise, it seems annoying that you could "section off" a corner, say by removing $(1,0)$ and $(0,1)$, but then choosing a any other collection of vertices, in order to form a disconnected end-graph. Consequently, even though I'm asking that precisely vertices be removed, one must consider $k=2$ in this case, since for each way to disconnect the graph also has $n^2-3$ options, so for $k=3$, one must also subtract off $(\binom{n^2}{2}-4)\cdot (n^2-3)$ as well, to obtain: $\binom{n^2}{3}-4\cdot 4-(\binom{n^2}{2}-4)\cdot (n^2-3)$ ways without disconnecting the graph. Does this seem correct? sigh.

feel free to edit the tags, I don't have a good sense about what would be appropriate for this problem.

$\endgroup$
6
  • $\begingroup$ Quick clarification: Does the grid have $(n+1)^2$ or $n^2$ vertices in the beginning? Because you say "starting with (0,0) and ranging up until n", but then you say there are $n^2$ ways to remove $n^2-1$ vertices. $\endgroup$
    – Noiralef
    Sep 25, 2016 at 15:31
  • $\begingroup$ @Noiralef it starts with $n^2$, so I should have labelled it up to $n-1$, sorry. For example: if you wanted to remove everything except for $(0,0)$, you could. Similarly, you could leave $(i,j)$ as the end graph for any $0 \leq i,j \leq n$. So there are $n^2$ ways to do this. In particular: $\binom{n^2}{1}-0$ is the solution for $k=1$. $\endgroup$ Sep 25, 2016 at 15:36
  • $\begingroup$ “In terms of counting”? Jeebus, what's the hip up-to-date way to say what we used to mean by “in terms of”? $\endgroup$ Sep 29, 2016 at 22:46
  • $\begingroup$ @AntonSherwood it's fully unclear to me what you mean. I changed the wording? $\endgroup$ Sep 29, 2016 at 22:52
  • $\begingroup$ Thank you. Do you understand a sentence like “find X in terms of Y”? $\endgroup$ Sep 30, 2016 at 23:39

1 Answer 1

1
$\begingroup$

The biggest problem is enumerating how much islands can you make, since islands make the end graph disconnected (counting all possible corner clips and other things is relatively easy). The number of islands with $l$ vertices is the number of $l$ Polykings for which there is no closed formula. How many islands can you make with removing $l$ vertices is basically the enumeration of polykings. You can make a closed form forumla for your problem for small $k$ by inspecting all possible cases and mutual configurations but even for $k=5$ that becomes too tedious.

polyking hole

Picture shows an island of 5 green vertices made by removing 10 red vertices.

$\endgroup$
1
  • 1
    $\begingroup$ I feel very naive. I suppose that I had only considered small enough cases so that this was not a consideration. Indeed, this makes the problem much more difficult. Thank you for showing the problems full difficulty. $\endgroup$ Sep 29, 2016 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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