6
$\begingroup$

Let $G = (V, E)$ be a simple, undirected graph with $|V|>2$, and let $S\subseteq V$ be a set with more than $1$ element. By $G/S$ we denote the graph obtained by collapsing $S$ to one point. More formally:

  • $V(G/S) = (V \setminus S) \cup \{S\}$, and
  • $E(G/S) = \big\{\{v,w\} \in E: v, w \notin S \big\}\cup \big\{\{v, \{S\}\}: v\in (V\setminus S)$ and there is $s \in S$ with $\{v,s\}\in E\big\}$.

We call a connected graph $G=(V,E)$ collapse-resistant $|V|> 2$ and if for all $S\subseteq V$ with $1<|S|<|V|$ we have $G \cong G/S$.

Clearly every infinite complete graph is collapse-resistant.

Question. Is every infinite connected collapse-resistant graph complete?

$\endgroup$
11
  • 1
    $\begingroup$ Not a complete answer, but this is at least false if one restricts least false if one restricts only to contractions involving finitely many vertices. Construction: Given a graph $G$ let $C(G)$ be the union of all finite collapses of $G$ Then given a graph $G$, consider $G \cup C(G) \cup C(C(G)) \cdots $. This does not work in the obvious way if one allows countable contractions since one can take a contraction that involves taking a vertex from each level of the construction, but a similar argument then taking a union up to the smallest uncountable ordinal will then work. $\endgroup$
    – JoshuaZ
    Commented Jan 14 at 16:52
  • 1
    $\begingroup$ Wouldn't an infinite graph with no edges be collapse-resistant, for the same reason that an infinite complete graph is? $\endgroup$
    – paste bee
    Commented Jan 14 at 17:16
  • $\begingroup$ Sorry I have to add "connected" graph $\endgroup$ Commented Jan 14 at 17:40
  • 1
    $\begingroup$ Thanks @JoshuaZ - can you maybe make this into an answer? $\endgroup$ Commented Jan 14 at 17:42
  • 1
    $\begingroup$ I would have called it contraction invariant, or possibly finite contraction invariant, since one could consider $\kappa$-contraction invariance, allowing the contraction of fewer than $\kappa$ many vertices. The concept makes sense in any relational structure, not just graphs. Also there is a weak and a strong form, depending on whether the new relation instances occur because of a single instance in $S$, as you defined, or whether you require all the instances with $S$ to hold. Paste bee's solution with the countable random graph is both weak and strong contraction invariant. $\endgroup$ Commented Jan 16 at 12:40

3 Answers 3

16
$\begingroup$

No. Let $G$ be the Rado graph (which is infinite, connected, and not complete), and $S$ a finite subset of the vertices of $G$ (because the Rado graph is countable). $G/S$ still has the extension property: for sets $U$ and $V$, there is a point in $G$ adjacent to all points in $U$, not adjacent to any points in $V$, and that is also not in $S$. (If either $U$ or $V$ contains the point $S$, we require the point in $G$ to be adjacent/not adjacent to all points in $S$). This point is adjacent in $G/S$ to all points in $U$, and not adjacent to any of the points in $V$. Any countable graph with this extension property is the Rado graph, so $G \cong G/S$.

$\endgroup$
13
$\begingroup$

No. Let $V = \mathbb{N}$ and $E = (0, i)$ for $i$ in $\mathbb{N}^*$ (a "star" graph where every vertex is connected to $0$).

If you collapse a subset containing $0$, the collapsed vertex can be mapped to $0$ and the remaining ones can be mapped to $\mathbb{N}^*$ as they are still all connected to $0$.

If you collapse a subset not containing $0$, you can map it to $1$ as it will only be connected to $0$. You can then map $0$ to $0$ and all the remaining vertices to $\mathbb{N} \setminus \{0, 1\}$

$G = (V, E)$ is collapse-resistant.

$\endgroup$
2
  • $\begingroup$ This was the simplest I could think of, I started with a covering tree because we want a connected graph, and then I realised the diameter of the graph will not grow when collapsing a subset. Turns out a tree of diameter 2 will do the trick ! $\endgroup$
    – Vincent
    Commented Jan 16 at 8:25
  • $\begingroup$ I am trying to think of other graphs of diameter 2, but it is starting to look complicated as soon as you have vertices of degree different from 1 and infinity. Actually the Rado graph is of diameter 2 (according to wikipedia) so maybe you have to jump from the star graph directly to the Rado graph ? $\endgroup$
    – Vincent
    Commented Jan 16 at 8:31
5
$\begingroup$

I add this answer to provide some variety, I believe this construction is collapse-resistant but the proof is not as easy and elegant as the other answers. Please comment if you find an error or gap in the proof !

Let $\mathbb{G}_f$ be the set of all finite graph. For $g \in \mathbb{G}_f$ a finite graph, let $\hat{g}$ be the union of a countable number of copy of $g$. Now let $G$ be the union of all $\hat{g}$ for $g \in \mathbb{G}_f$.

$G$ is not connected but it is collapse-resistant. When we collapse a finite subset of $G$, the resulting vertex will be connected to a finite number of vertices and be part a finite graph. It can be mapped to the corresponding finite graph from $G$. There will be a countable number of every finite graph remaining (not taking part in the collapse), so the result is still a countable number of every finite graph.

To get a connected graph, let us construct $\bar{G}$ by adding a vertex $o$ to $G$, connected to every other vertex.

$\bar{G}$ is connected and also collapse-resistant. If we collapse a subset $S$ containing $o$, the resulting vertex will be connected to all other vertices and can be mapped to $o$. For the remaining vertices ($\bar{G} \setminus \{o\}$), it is just as if we deleted $S \setminus \{o\}$, it will still result in a countable number of every finite graph. If we collapse a subset not containing $o$, it will work just the same as for $G$ (but with an added vertex $o$ connected to everything)

Note that this graph $\bar{G}$ is not the Rado graph, for example it has a vertex connected to every other vertex.

$\endgroup$

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.