The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)

Abstract

Graphs (1-skeletons) of Traveling-Salesman-related polytopes have attracted a lot of attention. Pedigree polytopes are extensions of the classical Symmetric Traveling Salesman Problem polytopes (Arthanari 2000) whose graphs contain the TSP polytope graphs as spanning subgraphs (Arthanari 2013). Unlike TSP polytopes, Pedigree polytopes are not “symmetric”, e.g., their graphs are not vertex transitive, not even regular.

We show that in the graph of the pedigree polytope, the quotient minimum degree over number of vertices tends to 1 as the number of cities tends to infinity.

D.O. Theis—Supported by the Estonian Research Council, ETAG (Eesti Teadusagentuur), through PUT Exploratory Grant #620, and by the European Regional Development Fund through the Estonian Center of Excellence in Computer Science, EXCS.

1 Introduction

Steinitz’s Theorem states that 3-connected planar graphs are precisely the graphs of 3-dimensional polytopes.

Properties of graphs of polytopes of higher dimension are of interest not only in the combinatorial study of polytopes, but also in Combinatorial Optimization, and Theoretical Computer Science.

The famous Hirsch conjecture in the combinatorial study of polytopes, settled by Santos [18], concerned the diameter of graphs of polytopes.

In Combinatorial Optimization, the study of the graphs of polytopes associated with combinatorial optimization problems was initially motivated by the search for algorithms for these problems.

In Theoretical Computer Science, the theorem by Papadimitriou [16] that Non-Adjacency of vertices of (Symmetric) Traveling Salesman Problem (TSP) polytopes is NP-complete, gave rise to similar results about other families of polytopes (cf. [1, 11] and the references therein, for recent examples).

There have been particularly many attempts to understand the graph of TSP polytopes, and, where this turned out to be infeasible, of TSP-related polytopes (e.g., [22]; cf. [6, 13, 15, 23, 24] and the references therein). The presence of long cycles has been studied ([21], see also [12, 14]), as has the graph density/vertex degrees (e.g., [19], see also [7, 9]).

The motivation for the research in this paper was a 1985 conjecture by Grötschel and Padberg [6] — well-known in polyhedral combinatorial optimization — stating that the graph of TSP polytopes has diameter 2 (also, Problem # 36 in [20]). Already in [6], Grötschel and Padberg extend the question for the diameter to a family of TSP-related polytopes which seemed easier to understand at the time.

A more recent family of TSP-related polytopes are the Pedigree polytopes of Arthanari [4]. For this family of polytopes, adjacency of vertices can be decided in polynomial time [2]. Moreover, the graphs of the TSP polytopes are spanning subgraphs of the graphs of the Pedigree polytopes [3]. This is so mainly because the Pedigree polytope for n cities is an extension, without “hidden” vertices, of the TSP polytope (cf., [5, 17]).

In this paper, we prove the following about graphs of Pedigree polytopes. Recall that the number of vertices of the TSP polytope for n cities is the number of cycles with vertex set $[n] := \{1,\dots ,n\}$, which is $(n-1)!/2$.

Theorem 1

The minimum degree of a vertex on the Pedigree polytope for n cities is $(1-o(1))\cdot (n-1)!/2$ (for $n\rightarrow \infty$).

In particular, the density graph of Pedigree polytopes is asymptotically equal to 1. Note, though, that while for TSP polytopes, these two statements are equivalent, this is not the case of Pedigree polytopes. The reason is that Pedigree extensions are not as “symmetric” as TSP polytopes (cf. [8]): For every two vertices u, v of the TSP polytope for n cities, there is an affine automorphism of the polytope mapping u to v. (Similar statements are true for monotone-TSP and graphical-TSP polytopes.) This is not true for Pedigree polytopes: Arthanari’s construction removes the symmetry to a large extent.

Numerical simulations show that, even for relatively large n (say, ${\approx }100$), the graph of the Pedigree polytope is not complete. We have made no attempt, however, to find a non-trivial upper bound for the minimum degree.

We Now Give a Non-technical Description of the Proof of Theorem 1. Arthanari’s beautiful idea of a pedigree is that of a cycle “evolving” over time: Starting from the unique cycle with node set $\{1,2,3\}$ at time 3, at time $n\geqslant 4$, the node n is added to the cycle by subdividing one of its edges. We say that n is inserted into that edge.

Arthanari’s combinatorial condition for adjancency on the Pedigree polytope can be thought of as a process, too, with a pedigree graph G evolving over time. Suppose we have two evolving cycles. Let us refer to A as Alice’s cycle, and to B as Bob’s cycle. At time n, Alice chooses an edge of her current cycle A (with node set $[n-1]$) and inserts her new node n into that edge to form her new cycle (with node set [n]). At the same time, Bob chooses an edge of his current cycle B, and inserts his new node n into that edge to form his new cycle.

The pedigree graph G may also change at time n. The new pedigree graph is either equal to the current one, or arises from the current one by adding the new vertex¹ n with incident edges. The choices of Alice and Bob determine: whether the new vertex is added or not; the number of edges incident to the new vertex n; the end vertices of these edges.

Arthanari’s combinatorial characterization of adjacency on the Pedigree polytope is now this.

Theorem 2

[2]. At all times $n\geqslant 4$, the two vertices of the Pedigree polytope for n cities corresponding to the (new) cycles A and B with node set [n] are adjacent in the Pedigree polytope, if, and only if, the (new) graph G is connected.

Theorem 1 states that, if B is a cycle chosen uniformly at random from all cycles on [n], then

$$\begin{aligned} \min _{A} \mathbb {P}\bigl ( \{\text { the pedigree graph is connected } \} \bigr ) = 1-o(1), \end{aligned}$$

where the minimum ranges over all cycles on [n]. Lower bounding this quantity amounts to studying the following “connectivity game”: Alice’s goal is to make the graph G disconnected; whereas Bob makes uniformly random choices all the time. We prove that Alice loses with probability $1-o(1)$. To analyze the game, we study a kind of a Markov Decision Process with state space $\mathbb {Z}_+\times \mathbb {Z}_+$. The states are pairs (s, t), where s is the number of common edges in Alice’s and Bob’s cycles, and t is the number of connected components of the current pedigree graph.

In the next section, we will give rigorous statements corresponding to the handwaving explanations above. In Sect. 3, we prove some basic facts about Bob playing randomly, and discuss the intuition of the proof of the main theorem. In Sect. 4, we introduce the Markov-Decision-Problem-ish situation that Alice finds herself in. The proof of the main theorem is sketched in Sect. 5; due to space limitations we have to refer to the upcoming journal version [10] of the paper for the details. We conclude with a couple of questions for future research which we find compelling.

2 Exact Statements of the Definitions, Facts, and Results

2.1 Cycles, One Node at a Time

Our cycles are undirected (so, e.g., there is only one cycle on 3 nodes). For ease of notation, let us say that the positive direction on a cycle with node set [n], $n\geqslant 3$, is the one in which, when starting from the node 1, the node 2 comes before the node 3; the other direction the negative direction. When referring to the kth edge of a cycle, we count the edges in the positive direction; the 1st one being the one incident on node 1. E.g., in the unique cycle with node set $\{1,2,3\}$, the 1st edge is $\{1,2\}$, the 2nd edge is $\{2,3\}$, and the 3rd edge is $\{3,1\}$.

As mentioned in the introduction, Arthanari’s Pedigree is a combinatorial object representing the “evolution” of a cycle “over time”, and the combinatorial definition of adjacency of pedigrees makes use of that step-by-step development. The set of Pedigrees is in bijecton with the set of cycles. In our context (we do not have to associate points in space with Pedigrees), defining Pedigrees and then explaining the bijection with cycles is more cumbersome than necessary. For convenience, we use the following more convenient definitions, which mirror the definition of Pedigrees, but they use cycles only. Let us say that an infinite cycle ² is a sequence $A = c_{{\scriptscriptstyle {\square }}} \in \prod _{n=3}^\infty [n]$. An infinite cycle A gives rise to an infinite sequence $A_{{\scriptscriptstyle {\square }}}$ of finite cycles (in the usual graph theory sense), defined inductively as follows:

• $A_3$ is the unique cycle with node set $\{1,2,3\}$;

• for $n\geqslant 3$, $A_n$ is the cycle with node set [n] which arises from adding the node n to $A_{n-1}$ by inserting it into (i.e., subdividing) the $c_{n-1}$th edge.

We think of $A_{{\scriptscriptstyle {\square }}}$ as a cycle developing over time: At time n, the node n is added.

We will need to access the neighbors of node n in $A_n$, i.e., the ends of the edge into which n is inserted (i.e., which is subdivided) when n is added to $A_{{\scriptscriptstyle {\square }}}$. We write $\nu _A^+(n)$ for the neighbor of n in $A_n$ following n in the positive direction, and $\nu _A^-(n)$ for the neighbor of n in $A_n$ following n in the negative direction. The unordered pair $\nu _A(n) = \{ \nu _A^+(n), \nu _A^-(n) \}$ is the $c_{n-1}$th edge of $A_{n-1}$, the one into which n was inserted.

These definitions are for $n\geqslant 4$ but extend naturally for $n=1,2,3$: for $n=3$ we let $\nu _A^+(3)=1$, and $\nu _A^-(3)=2$; for $n=2$, we let $\nu _A^+(2)=\nu _A^-(2)=1$. The equation $\nu _A(n) = \{ \nu _A^+(n), \nu _A^-(n) \}$ holds for $n\geqslant 2$ (so $|{\nu _A(2)}|=1$); for $n=1$ we have $\nu _A(1) := \emptyset$.

Remark 3

(Finding $\nu (k)$ for “old” nodes k ). It is readily verfied directly from the definition, that, for $k\geqslant 2$, $\nu ^\pm _A(k)$ can be found as follows: start from node k and walk in positive direction. The first node smaller than k which you encounter is $\nu ^+_A(k)$. Similarly, if you walk in negative direction starting from k, the first node smaller than k which you hit, is $\nu ^-_A(k)$.

A pair of nodes i, j split each cycle $A_{n}$, $n>i,j$ into two (open) segments (i, j do not belong to either segment). We say that the segment between i and j is the one which does not contain the node $\min (\{1,2,3\}{\setminus }\{i,j\})$ (i.e., 1, unless $1\in \{i,j\}$, in that case, 2, unless $\{1,2\}=\{i,j\}$, in that case 3). Note that this does not depend on the choice of $n>i,j$, which justifies to say “the segment of $A_{{\scriptscriptstyle {\square }}}$ between i and j”.

Remark 4

(Testing/finding n with $\nu (n)=\{i,j\}$ ). Given a pair of nodes $\{i,j\}$ and $n'>i,j$, there exists an $n\leqslant n'$ with $\nu _A(n)=\{i,j\}$ if, and only if, the segment between i and j on $A_{n'}$ is non empty and every node in it is larger than both i and j. In that case, the smallest node, n, in the segment between i and j on $A_{{\scriptscriptstyle {\square }}}$ is the one with $\nu (n)=\{i,j\}$.

2.2 The Pedigree Graph

Two infinite cycles A, B give rise to a sequence of graphs $G^{AB}_{{\scriptscriptstyle {\square }}}$ which we call the pedigree graphs. We omit the superscripted A, B when possible. We speak of vertices of the pedigree graphs (rather than nodes). We do this to avoid confusion between the nodes of the cycles $A_{{\scriptscriptstyle {\square }}},B_{{\scriptscriptstyle {\square }}}$ and the vertices of $G^{AB}_{{\scriptscriptstyle {\square }}}$, because the vertex set of $G_n$ is a subset of $\{4,\dots ,n\}$, and hence of the node set of $A_n$ and $B_n$. So a node $k\in [n]$ may or may not be a vertex of $G_n$.

The pedigree graph $G_{n-1}$ is the subgraph of $G_n$ induced by the vertices in $[n-1]$. In other words, $G_n$ is either equal to $G_{n-1}$ (if n is not a vertex), or it arises from $G_{n-1}$ by adding the vertex n together with edges between n and vertices in $[n-1]$.

Example 5

$G_1,G_2,G_3$ are graphs without vertices. $G_4$ may be a graph without vertices, or it may consist of a single isolated vertex 4. $G_5$ could be a graph without vertices; a graph with a single vertex 5; a graph with two isolated vertices 4, 5, or a graph with two vertices 4, 5, linked by an edge. Check Fig. 1 for possible $G_4$ and $G_5$.

According to Arthanari [2, 3] the condition for the existence of vertices is the following:

• (1) A node $n\in [n]$ is a vertex of $G_n$, iff $\nu _A(n) \ne \nu _B(n)$.

There are several conditions for the presence of edges between the vertex n and earlier vertices. To make it easier to distinguish these, we speak of edge “types” and give the edges implicit “directions:” from A to B or from B to A. Here are the conditions for edges from n to earlier vertices.

• (2) There is a type-1 edge “from A to B” between n and $k\in [n-1]$, if $\nu _A(n) = \nu _B(k)$. (Note that the condition implies that k is a vertex.)

• (3) There is a type-1 edge “from B to A” Ditto, with A and B exchanged.

• (4) There is a type-2 edge “from A to B” between n and $\ell := \max \nu _A(n)$, unless $\displaystyle \nu _B( \ell ) \cap \nu _A(n) \ne \emptyset$. In other words, suppose the node n was inserted into the edge $\{k,\ell \}$ in A, with $k < \ell$. Now look up the end-nodes of the edge $\nu _B(\ell )$ into which $\ell$ was inserted when it was added to B. Unless k coincides with one of these end nodes, there is an edge between n and $\ell$.

• (5) Type-2 edge “from B to A” Ditto, with A and B exchanged.

Arthanari’s theorem [2] Theorem 2 states that, if $n\geqslant 4$, and $A_n$, $B_n$ are two cycles with node set [n], then the two vertices of the Pedigree polytope (for n cities) corresponding to $A_n$ and $B_n$ are adjacent, if, and only if, $G^{AB}_n$ is connected.

We will always think of A as “Alice’s cycle” and B as “Bob’s cycle”.

Example 6

Going through an example will help understand the definition of a pedigree graph. Figure 1 shows two cycles A and B evolving over time $n=3,\dots ,10$, together with the evolving pedigree graph $G^{AB}_{{\scriptscriptstyle {\square }}}$.

Fig. 1.

Cycles $A_{\scriptscriptstyle {\square }}$ and $B_{\scriptscriptstyle {\square }}$ and corresponding $G_{\scriptscriptstyle {\square }}^{AB}$

• $n=3$ : As mentioned above, $G^{AB}_{3}$ is a graph without vertices.

• $n=4$ : Alice inserts her new node 4 between into the edge $\{1,2\}$ of her cycle $A_3$; Bob inserts his new node 4 into the edge $\{1,3\}$ of his cycle $B_3$. Hence, $\{1,2\} = \nu _A(4) \ne \nu _B(4) = \{1,3\}$, so vertex 4 is added to $G_3^{AB}$.

• $n=\!5$ : Alice inserts her new node 5 into the edge $\{2,4\}$ of her cycle $A_4$; Bob inserts his new node 5 into the edge $\{1,2\}$ of his cycle $B_4$. Since $\{2,4\} = \nu _A(5) \!\ne \! \nu _B(5) = \{1,2\}$, vertex 5 is added to $G_4^{AB}$. Let us check the edges:

  • – In $B_4$, the segment between 2 and 4 contains the node 3 which is smaller than 4. By Remark 4, there is no k with $\nu _A(5) = \nu _B(k)$, and hence no type-1 edge from A to B at this time.

  • – As $\nu _B(5) = \nu _A(4)$, there is a type-1 edge between 4 and 5 from B to A.

  • – Since $\max \nu _A(5)=4$ and $\nu _B(4) =\{1,3\} \not \ni 2$, there is also a type-2 edge between 5 and 4 from A to B.

  • – MOZHGAN: Type-2 edge from B to A.

• $n=6$ : Alices inserts her new node 6 into the edge $\{2,3\}$ of her cycle, Bob inserts his new node 6 into the edge $\{2,3\}$ of his cycle. Since $\{2,3\} = \nu _A(6) = \nu _B(6) = \{2,3\}$, we don’t have a vertex 6 in $G_6^{AB}$.

• $n=7$ : Alice throws into $\{4,5\}$, Bob throws into $\{3,4\}$. Since $\{4,5\} = \nu _A(7) \ne \nu _B(7) = \{3,4\}$, the vertex 7 is added to $G_6^{A,B}$.

  • – MOZHGAN: Type-1 edge from A to B.

  • – MOZHGAN: Type-1 edge from B to A.

  • – As $\max \nu _A(7)=5$ and $\nu _B(5)=\{1,2\} \not \ni 4$, we have a type-2 edge from A to B between 7 and 5.

  • – As $\max \nu _B(7)=4$ and $\nu _A(4)=\{1,2\} \not \ni 3$, there is also a type-2 edge from B to A between 7 and 4.

• $n=8$ : Alice plays $\{3,6\}$, Bob chooses $\{1,4\}$. Since $\{3,6\} = \nu _A(8) \ne \nu _B(8) = \{1,4\}$, the vertex 8 is added to $G_7^{A,B}$.

  • – In $B_7$, the segment between 3 and 6 is empty (just the edge). By Remark 4, there is no k with $\nu _A(8) = \nu _B(k)$, and hence no type-1 edge from A to B.

  • – For the same reason (segment between 1 and 4 empty), there is no type-1 edge from B to A incident to the vertex 8.

  • – $\max \nu _A(8)=6$ and $\nu _B(6)=\{2,3\} \ni 3$. So there is no type-2 edge from A to B between 8 and a smaller vertex.

  • – $\max \nu _B(8)=4$ and $\nu _A(4)=\{1,2\} \ni 1$. So there is no type-2 edge from B to A between 8 and a smaller vertex.

Hence, vertex 8 is isolated in $G_8$.

• $n=9$ : Alice chooses $\{1,3\}$, Bob chooses $\{1,8\}$. As $\{1,3\} = \nu _A(9) \ne \nu _B(9) = \{1,8\}$, the vertex 9 is added to $G_8^{A,B}$.

  • – As $\{1,3\} = \nu _A(9) = \nu _B(4) = \{1,3\}$, there is a type-1 edge from A to B between 9 and 4.

  • – MOZHGAN: Type-1 edge from B to A.

  • – MOZHGAN: Type-2 edge from A to B.

  • – As $\max \nu _B(9)=8$ and $\nu _A(8) = \{3,6\} \not \ni 1$, there is a type-2 edge from B to A between 9 and 8.

• $n=10$ : Alice chooses $\{3,9\}$, Bob chooses $\{2,6\}$. Since $\{3,9\} = \nu _A(10) \ne \nu _B(10) = \{2,6\}$, the vertex 10 is added to $G_9^{A,B}$.

  • – MOZHGAN: Type-1 edge from A to B.

  • – Again, in B, the segment between 3 and 9 has a vertex (4) smaller than 9. Remark 4 gives us that there is no k $\nu _B(k) = \nu _A(10)$, so no type-1 edge from B to A is created.

  • – As $\max \nu _A(10)=9$ and $\nu _B(9) = \{1,8\}\not \ni 3$, there is a type-2 edge from A to B between 10 and 9.

  • – As $\max \nu _B(10)=6$ and $\nu _A(6) = \{2,3\} \ni 2$, no type-2 edge from B to A is created.

2.3 Rephrasing Theorem 1

We now rephrase Theorem 1, in terms of the pedigree graph. We also unravel the little-o, and move to the “Alice-and-Bob” letters for the cycles.

Theorem 7

(Theorem 1 , rephrased). For every $\varepsilon >0$ there is an integer N such that for all $n\geqslant N$ and all cycles $A_n$ with node set [n], if $B_n$ is drawn uniformly at random from all cycles with node set [n], then

$$\begin{aligned} \mathbb {P}\bigl ( G^{AB}_n \text { is connected } \bigr ) \geqslant 1-\varepsilon . \end{aligned}$$

In symbols, and using infinite cycles, this reads:

$$\begin{aligned} \forall \varepsilon >0 \;\; \exists N:\; \forall A \, \forall n\geqslant N:\mathbb {P}( G^{AB}_n \text { is connected } ) \geqslant 1-\varepsilon , \end{aligned}$$

where the probability is taken over all infinite cycles, see the next section. A close look at our proof shows that we are actually proving the following stronger statement (we don’t have any use for it, though):

$$\begin{aligned} \forall \varepsilon >0 \;\; \exists N:\; \forall A:\; \mathbb {P}\bigl ( \forall n\geqslant N: G^{AB}_n \text { is connected } \bigr ) \geqslant 1-\varepsilon . \end{aligned}$$

3 Pedigree Graphs of Random Cycles

We have to reconcile uniformly random cycles with the “evolution over time” concept of pedigrees. The definition of an infinite cycle makes that very convenient, just do the same as with infinite sequences of coin tosses: Take, as probability measure on the sample space $\prod _{n=1}^\infty [n]$ of all infinite cycles the product of the uniform probability measures on each of the sets [n], $n\geqslant 3$. We refer to the atoms in this probability space as random infinite cycles. The following is a basic property of product probability spaces. We will use it mostly without mentioning it.

Fact 8

If B is a random infinite cycle, then, for each $n\geqslant 3$, the cycle $B_n$ is uniformly random in the set of all cycles with node set [n].

Creating Isolated Vertices. The first substantial result about the connectedness of the pedigree graph, concerns the creation of isolated vertices.

As outlined in the introduction, we study the situation in which Alice chooses her edge of $A_{n-1}$ according to a sophisticated strategy, whereas Bob always chooses a uniformly random edge of $B_{n-1}$ to insert his node n into (which amounts to his cycle $B_n$ being uniformly random in the set of all cycles on [n], by Fact 8). In this section, we adopt a purely “random graph” perspective. For fixed A and random B, the pedigree graphs $G^{AB}_{{\scriptscriptstyle {\square }}}$ are a sequence of random graphs, with some weirdo distribution: At time n, whether the new vertex n is added or not, and if it is, how many incident edges it has, and what their end vertices are — these are all random events/variables.

For deterministic A and random B, let the random variable Y count the total number of times that an isolated vertex of the pedigree graph is created. In other words, $Y = \sum _{n=4}^\infty \mathbf {1}_{I_n}$, where $I_n$ denotes the event that, at time n, n is added as an isolated vertex to $G_n^{A,B}$ (and $\mathbf {1}_{{\scriptscriptstyle {\square }}}$ is the indicator random variable of the event).

Lemma 9

Whatever Alice does, $\mathbb {E}Y = 2$.

Moreover, for every $\varepsilon >0$, if $n_0 \geqslant 4/\varepsilon +2$, then, whatever Alice does

$$\begin{aligned} \mathbb {P}\Bigl ( \bigcup _{n \geqslant n_0} I_n \Bigr ) \quad \leqslant \; \varepsilon . \end{aligned}$$

For the proof we refer to the journal version of this extended abstract [10]. To understand why the lemma is important, consider a pedigree graph at time n, just before Alice and Bob make their choices of cycle edges into which their respective new nodes n are inserted. If n is not a vertex of the new pedigree graph $G_n$, the number of connected components of $G_{{\scriptscriptstyle {\square }}}$ doesn’t change. If n is a vertex, and and it does have incident edges, then the number of connected components can only decrease. The only way that the number of connected components of $G_n$ can increase is if n is an isolated vertex in the new pedigree graph. Hence, Lemma 9 provides an upper bound on the expected number of connected components, uniform over n.

The Intuition. From Lemma 9, it is unlikely that the pedigree graph will have many components. Indeed, intuitively, if only 2 isolated vertices are ever created, that means that most of the time either nothing happens (no new vertex) or edges are created, ultimately reducing the number of components, so the pedigree graph is connected.

While this basic intuition is essentially correct, a closer look reveals some subtleties. First of all, Alice has a big sway in choosing the end vertices of new edges: she can pick the end vertices of type-2 edges from A to B; and she can influence the end vertices of type-1 edges (both directions).

Secondly, Bob’s choices are reduced by the low degrees of the vertices. (A stronger version of (a) is proved in [10].)

Lemma 10

The maximum degree of a vertex in a pedigree graph is at most 6:

• (a) up to 2 to vertices created in the past; and

• (b) up to 6 to future vertices.

Hence, if a vertex $n_0$ was created as an isolated vertex or landed in a small connected component, Bob has only 4–6 shots at connecting it to another connected component. The good news is that Alice can never “shut down” a connected component completely: Bob can always extend it by one more vertex.

Lemma 11

Let C be a connected component of the pedigree graph $G^{AB}_{n-1}$. There exists a $k\in C$ such that, no matter what Alice’s move is at time n, Bob has a move which creates the vertex n and makes it adjacent to k.

Proof

Take $k := \max V(C)$. Since k is a vertex, we have $|{ \nu _B(k) \cap \nu _A(k) }| \leqslant 1$. Suppose that $\nu ^+_B(k) \notin \nu _A(k)$ (the other case is symmetric). Then, the first time Bob inserts a node, say $n'$, into the edge on the positive side of k, this will create a type-2 edge “from B to A” between $n'$ and k. Since k is the newest vertex in its component, Bob has not yet inserted a node there, so he can insert n there, now.    $\square$

However, for Bob to make a disconnected pedigree graph connected, at some time, he will have to manage to insert his new node in such a way that it has two incident edges, linking two connected components at the same time.

There is no difficulty in realizing that Alice wouldn’t stand a chance against a strategically playing Bob. But we claim that the game between a clever Alice and a blindfolded Bob will turn in Bob’s favour almost all of the time.

Computer simulations give another indication that some care has to be taken implementing the basic intuition: Even for n as large as 100, even if Alice’s cycle is chosen uniformly at random instead of adversarial, the frequency (in 100000 samples) with which we saw a connected pedigree graph was only about 84%. In the remaining 16% of cases, the typical situation is that of one giant connected component containing almost every vertex, and one tiny component growing only very slowly. This indicates that even a disinterested Alice can do some damage.

4 The Connectivity Game

At each time, Alice moves first. As already explained, she determines the cycle A by choosing, at each time n, the edge of $A_{n-1}$ into which her new node n will be inserted. Then Bob moves. He determines B in the same way, but (using Fact 8), he will draw the edge of $B_{n-1}$ into which his new node n is inserted uniformly at random from all edges of $B_{n-1}$, and his choice is independent of his earlier choices.

We say that Bob wins, if there exists an $n_0$ such that for all $n\geqslant n_0$, the pedigree graph $G^{AB}_n$ is connected. We need Bob to win “uniformly”, i.e., $n_0$ must not depend on Alice’s moves.

Let the random variable $T_n$ denote the number of connected components in the pedigree graph $G^{AB}_n$. To analyze the development of the random process $T_{\scriptscriptstyle {\square }}$, it turns out to be useful to consider a second random process, $S_{\scriptscriptstyle {\square }}$. Denote by $E^\cap _n$ the set of edges that Alice’s cycle and Bob’s cycles have in common,

$$\begin{aligned} E^\cap _n := E(A_n) \cap E(B_n), \end{aligned}$$

and let

$$\begin{aligned} S_n := |{E^\cap _n}| \end{aligned}$$

count the number of cycle edges that Alice and Bob have in common. We will distinguish Alice’s moves by whether or not she chooses a common cycle edge to place her new cycle node. The set $E^{\cap *}_n$ holds those common edges which are not incident on the edge which Alice chooses for her new node:

$$\begin{aligned} E^{\cap *}_n := \bigl \{ e \in E^\cap _n \mid e \cap \nu _A(n+1) = \varnothing \bigr \}; \end{aligned}$$

we let $S^{*}$ count the edges in $E^{\cap *}$:

$$\begin{aligned} S^{*}_n := |{E^{\cap *}_n}|. \end{aligned}$$

Finally, denote by $E^r_n$ the set of edges in Bob’s cycle which are neither common nor incident on Alice’s chosen edge:

$$\begin{aligned} E^r_n&:= \bigl \{ e \in E(B_n){\setminus }E^\cap _n \mid e\cap \nu _A(n+1) = \varnothing \bigr \} \text {; and}\\ R_n&:= |{ E^r_n }|. \end{aligned}$$

We are now ready to state and prove the transition probabilities. They depend on whether Alice chooses, for her new node, a common edge — we refer to that as a c-move by Alice — or an edge which is in the difference $E(A_n){\setminus }E^\cap _n$ — we call that a d-move.

Lemma 12

The conditional probabilities

$$\begin{aligned} \mathbb {P}\Bigl ( S_{n+1}=S_n + \varDelta _S \;\; \wedge \;\; T_{n+1}=T_n + \varDelta _T \;\; \mid \; B_n \Bigr ) \end{aligned}$$

satisfy these bounds (entries not shown are “${=}0$”):

The proof of this lemma requires some delicated distinguishing of cases, we refer to the journal version [10].

The proof of the main theorem now follows the following idea. From the tables in Lemma 12, you see that d-moves have chance of reducing the number of connected components — albeit a small one. Moreover, Alice cannot take a c-move only when $S_n > 0$, but c-moves have a strong tendency to reduce $S_{\scriptscriptstyle {\square }}$. We prove that the number of d-moves that Alice has to take are frequent enough to lead to a decrease in the number of connected components. This suffices to prove Theorem 5, along the lines sketched on page 10.

The next section gives more details of the proof.

5 Proof of Theorem 7

Using the Azuma-Hoeffding super-martingale tail bound, we can prove that, for large enough $n_0$, Alice has to take many d-moves between times $n_0$ and $2n_0$. Due to space restrictions, we have to refer to the journal version [10] for all of the proofs.

Lemma 13

For every $\varepsilon \in \left]0,1\right[$, if $n_0 \geqslant \max (900, 8\ln (1/\varepsilon ))$, and $n_1 := 2 n_0$ then, whatever Alice does, the probability, conditioned on $B_{n_0}$ and $S_{n_0}\leqslant \ln ^2 n_0$, that among her moves at times $n = n_0+1,\dots ,n_1$, there are fewer than $n_0/3$ d-moves, is at most $\varepsilon$.

From this, we deduce that must $T_{\scriptscriptstyle {\square }}$ decrease, but some sophistication is needed, because of the slow divergence of $\sum 1/n$: Indeed, between $n_0$ and $2n_0$, $T_{\scriptscriptstyle {\square }}$ decreases only with a constant probability:

Lemma 14

Fix . If $n_0 \geqslant \max (900, 8\ln (1/\delta ))$, and $n_1 := 2 n_0$ then, whatever Alice does,

$$\begin{aligned} \mathbb {P}\Bigl ( \exists n \in \{n_0+1,\dots ,n_1\}:\;\; T_{n+1} < T_n \;\; \Bigm | B_{n_0}, T_{n_0} \geqslant 2, S_{n_0} \leqslant \ln ^2 n_0 \Bigr ) \quad \geqslant \quad 1/7. \end{aligned}$$

We can boost the probability to $1-\varepsilon$, for arbitrary $\varepsilon >0$, by iterating the argument $\varOmega (\ln (1/\varepsilon ))$ times.

Lemma 15

Fix . For every , with $a := 10\ln (2/\varepsilon )$, if

$$\begin{aligned} n_0 \geqslant \max (900, 8\ln (1/\delta ), (2a)^{4/\varepsilon }, e^{6/\varepsilon }), \end{aligned}$$

and $n_1 := 2 a n_0$ then, whatever Alice does,

$$\begin{aligned} \mathbb {P}\Bigl ( \exists n \in \{n_0,\dots ,n_1\}:\;\; T_{n+1} < T_n \;\; \Bigm | B_{n_0}, T_{n_0} \geqslant 2 \Bigr ) \quad \geqslant \quad 1-\varepsilon \end{aligned}$$

Note that Lemma 15 also gets rid of the conditioning on $S_n \leqslant \ln ^2 n$.

We are now ready to complete the proof of the main theorem.

Proof

(of Theorem 7 ). Let be given. Set $t := 6/\varepsilon '$. Since $T_{{\scriptscriptstyle {\square }}}$ can only increase when an isolated vertex is created, we have $T_n \leqslant Y$, for all $n\geqslant 4$, where Y is the number of isolated vertices. Hence, by Lemma 9 and Markov’s inequality, we have

$$\begin{aligned} \mathbb {P}\Bigl ( \exists n \geqslant 4:\;\; T_n \geqslant t+1 \Bigr ) \leqslant \mathbb {P}( Y \geqslant t ) \leqslant \mathbb {E}(Y) / t = \varepsilon '/3. \end{aligned}$$

Now take $n_0' \geqslant 12/\varepsilon ' +2$, and large enough to apply Lemma 15 $n_0:=n_0'$ and to $\varepsilon := \varepsilon '/3t$ (note that this is less than 1/56). Denote by a be the number defined in that lemma. Applying the lemma t times, for $n_0$ ranging over $n'_0 +j2a n'_0$, $j=0,\dots ,t-1$, the probability that we fail at least once to obtain a decrease in the number of connected components, $T_{\scriptscriptstyle {\square }}$, is at most $\varepsilon '/3$. So, with probability at least $1-2\varepsilon '/3$, we must have $T_{n_0}=1$ for one of these $n_0$’s or for an n between $n'_0 +(t-1)2a n'_0$ and $n'_0 +t2a n'_0$.

Finally, since $n_0' \geqslant 12/\varepsilon ' +2$, by Lemma 9, with probability $1-\varepsilon '/3$, $T_{\scriptscriptstyle {\square }}$ will not increase after $n'_0$, and hence, with probability $1-\varepsilon '$, will drop to 1 and stay there for all eternity. Bob wins.

6 Some Open Questions

There are two questions which we believe should be asked in the context of our result.

Firstly, are there other polytopes whose graphs are not complete, but the minimum degree is asymptotically that of a complete graph? Could that even be the case for the Traveling Salesman Problem polytope itself?

Secondly, in view of the Traveling Salesman Problem polytope, it would be interesting to find other combinatorial conditions on cycles which are implied by the adjacency of the corresponding vertices on the TSP polytope. The pedigree graph connectedness condition is derived from an extension of the TSP polytope, but maybe there are other combinatorial conditions without that geometric context. The graph resulting from such a condition might be “closer” to the actual TSP polytope graph, i.e., add fewer edges.