Googology Wiki
Register
Advertisement
Googology Wiki

View full site to see MathJax equation

Greedy clique sequences are a concept from graph theory that leads to three fast-growing functions.[1] Defined by Harvey Friedman in 2010, the resulting functions are some of the strongest Friedman has ever defined.

Definition[]

Background[]

\(\mathbb{Q}^*\) (using the Kleene star) denotes the set of all tuples of rational numbers, or Q-tuples. We use subscripts to denote indexes into tuples (starting at 1) and angle brackets to denote concatenation of tuples (e.g. \(\langle (0,1), (2,3) \rangle = (0,1,2,3)\)).

Given \(a \in \mathbb{Q}^*\), we define the upper shift of \(a\), denoted \(\text{us}(a)\) to be the result of adding 1 to all its nonnegative components.[2] Given \(a,b \in \mathbb{Q}^*\), we say that \(a \preceq b \Leftrightarrow \max(a) \leq \max(b)\) and \(a \prec b \Leftrightarrow \max(a) < \max(b)\). \(a,b \in \mathbb{Q}^*\) are called order equivalent iff they have the same length and for all \(i,j\), \(a_i < a_j\) iff \(b_i < b_j\). A non-empty set \(E \subseteq \mathbb{Q}^*\) is order invariant iff for all order equivalent \(x\) and \(y\), \(x \in E \Leftrightarrow y \in E\).

Let \(H\) be a graph with vertices in \(\mathbb{Q}^*\). Let \(E\) be the set defined as follows: for every edge \((x,y)\) in \(H\), their concatenation \(\langle x, y \rangle\) is in \(E\). Then if \(E\) is order invariant, we say that \(H\) is order invariant. When \(H\) is order invariant, \(H\) has infinite edges.

Definition of USGCS's, USGDCS's, and open threads[]

We are given \(k \in \mathbb{N}\), \(S \subseteq \mathbb{Q}^*\), and \(G\) a simple graph (for USGCS) or a digraph (for USGDCS) with vertices in \(S\). We define a sequence \(\mathbf{x}\) as a nonempty tuple \((x_1, x_2, \ldots, x_n)\) where \(x_i \in S\). This is not a Q-tuple but rather a tuple of Q-tuples.

The thread of \(\mathbf{x}\) is a subsequence \((u_1, u_2, \ldots, u_r)\) of \([1, n]\) defined inductively as follows. \(u_1 = 1\). If \(u_i\) is defined, then \(u_{i+1}\) is defined as the maximal \(j \in S_{i+1}\) such that \(x_j = \max \{x_{j'} | j' \in S_{i+1}\}\), where \(S_{i+1}\) denotes \(\{j \in [u_i, 2^{u_i}] \mid x_j \prec x_{u_i}\}\). In other words, \(u_{i+1} = \max (j \in [u_i, 2^{u_i}] | x_j \prec x_{u_i})\). If \(S_{i+1}\) is empty then \(u_{i+1}\) is undefined.

There is a following inductive algorithm for determining \(u_{i+1}\):

  1. Start with the \(j\)'s lying in \([u_i, 2^{u_i}]\) such that \(x_j \prec x_{u_i}\). If there are no such \(j\)'s then \(u_{i+1}\) is undefined.
  2. Select \(j\)'s from step 1 where \(max(x_j)\) is the largest.
  3. Then \(u_{i+1}\) is equal to the largest of these \(j\)'s.

From this follows important consequence: \(u_2\) is 2 if \(x_2 \prec x_1\) and undefined otherwise.

Given a thread \(u\), we say that it is open (or terminal in the updated terminology) if \(2^{u_r} \leq n\) (recalling that \(r\) is the length of \(u\)). This means that we couldn't find any such j's when trying to construct \(u_{r+1}\).

Now \(\mathbb{Q}^k\) is the set of tuples of rational numbers with length \(k\).

When \(S = \mathbb{Q}^k\), \(\mathbf{x}\) is said to be an upper shift greedy clique sequence in \(\mathbb{Q}^k\) if it satifies the following:

  1. \(x_1\) is only 0's.
  2. Let \(m\) be an integer such that \(2 \leq 2m \leq k - 1\), or a positive integer if we allow infinite sequences. Define \(Y\) as the concatenation \(\langle x_1,x_2,\ldots, x_{2m-1}\rangle\) and let \(y = (Y_m, Y_{m+1}, \ldots, Y_{m+k-1})\). Then \(x_{2m} \preceq y\) and \((y, x_{2m})\) is not an edge of \(G\), and \(x_{2m + 1} = \text{us}(x_{2m})\).
  3. \(\{x_2, x_3, \ldots, x_n\}\) is a clique in \(G\). That is, \(G\) contains as an edge every pair of vertices in \(\{x_2, x_3, \ldots, x_n\}\).

When \(S = \mathbb{Q}^k\), \(\mathbf{x}\) is said to be an upper shift greedy down clique sequence in \(\mathbb{Q}^k\) if:

  1. \(x_1\) is only 0's.
  2. Define \(m\) and \(y\) as above. Then \(x_{2m} = y \text{ or } (x_{2m} \prec y \text{ and } (y, x_{2m}) \text{ is not an edge of } G)\), and \(x_{2m+1} = \text{us}(x_{2m})\).
  3. \(\{x_2, x_3, \ldots, x_n\}\) is a down clique in \(G\). \(A\) is a down clique in \(G\) iff for all \(x,y \in A\) and \(x \succ y\), \((x, y)\) is an edge of \(G\).[2]

When \(S = \mathbb{Q}^k \cup \mathbb{Q}^{k+1}\), \(\mathbf{x}\) is said to be an extreme upper shift greedy down clique sequence in \(\mathbb{Q}^k \cup \mathbb{Q}^{k+1}\) if:

  1. \(x_1\) is only 0's.
  2. Define \(m\) and \(y\) as above. Then \(x_{2m} = y \text{ or } (x_{2m} \prec y \text{ and } (y, x_{2m}) \text{ is not an edge of } G)\), and \(x_{2m+1} = \text{us}(x_{2m})\).
  3. If \(x_{2m}\) lies in \([0,k]^k\), then \(x_{2m+1} = (k+(1/2),\text{us}(x_{2m}))\).
  4. If \(x_{2m}\) lies in \(\mathbb{Q}^k \setminus [0,k]^k\), then \(x_{2m+1} = \text{us}(x_{2m})\).
  5. If \(x_{2m} = (k+(1/2),z)\) lies in \(\mathbb{Q}^{k+1}\) then \(x_{2m+1} = \text{us}^{-1}(z)\).
  6. \(\{x_2, x_3, \ldots, x_n\}\) is a down clique in \(G\).

Functions[]

Friedman defined the following three "witness functions", which are originally denoted by \(W(k)\):

  • \(\text{USGCS}(k)\) is the least integer \(N\) such that every simple, order invariant graph \(G\) has an upper shift greedy clique sequence in \(\mathbb{Q}^k\) of length at most \(N\) with an open thread.
  • \(\text{USGDCS}(k)\) is the least integer \(N\) such that every order invariant digraph \(G\) has an upper shift greedy down clique sequence in \(\mathbb{Q}^k\) of length at most \(N\) with an open thread.
  • \(\text{USGDCS}_2(k)\) is the least integer \(N\) such that every order invariant digraph \(G\) has an extreme upper shift greedy down clique sequence in \(\mathbb{Q}^k \cup \mathbb{Q}^{k+1}\) of length at most \(N\) with an open thread.

Properties and lower bounds[]

Clearly, \(\text{USGDCS}(k) \geq \text{USGCS}(k)\). USGDCS restricts only one direction out of two on edges since it uses digraphs instead of simple graphs. It's not known whether a function \(f(k)\) exists such that \(\text{USGCS}(f(k)) > \text{USGDCS}(k)\) (that would make this pair of functions similar to \(\text{SSCG}(k)\) and \(\text{SCG}(k)\)).

Following values and lower bounds are known:

\(\text{USGCS}(1) = 2\) using sequence ((0),(0)).

\(\text{USGCS}(2) = 2\) using sequence ((0,0),(0,0))[3].

\(\text{USGCS}(3) \geq 4\) using sequence ((0,0,0),(-1,-1,-1),(-1,-1,-1),(-0.5,-0.5,-0.5)).

\(\text{USGCS}(4) \geq 16\) using a generic sequence with thread [1,2,4] [4].

Growth rates[]

In all the following definitions, \(n\) ranges over natural numbers. We define the theory SRP as ZFC + "there exists a cardinal with \(n\)-Stationary Ramsey Property" for all \(n\), and SRP+ as ZFC + "for every \(n\) there exists a cardinal with \(n\)-Stationary Ramsey Property". Similarly, we define HUGE as ZFC + "there exists an \(n\)-huge cardinal" for all \(n\) and HUGE+ as ZFC + "for every \(n\) there exists an \(n\)-huge cardinal".

USGCS and USGDCS eventually dominate all functions provably recursive in SRP, but are themselves provably recursive in SRP+. USGDCS2 eventually dominates all functions provably recursive in HUGE, but is itself provably total in HUGE+.

These were claimed on Harvey Friedman’s website, but so far a proof has not been provided.

Sources[]

See also[]

Graph theory in googology

TREE sequence  TREE(3) · Greedy clique sequence · Friedman's finite trees · Subcubic graph number  SCG(13) · Graham's number  G(64)

Advertisement