## FANDOM

10,502 Pages

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 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.

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 n - 1$$, or a postive 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 \vee (x_{2m} \prec y \wedge (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 \vee (x_{2m} \prec y \wedge (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$$.

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 [u_i, 2^{u_i}]$$ such that $$x_j \prec x_{u_i}$$ and $$\max(x_j)$$ is maximized over the $$j$$. If there are no such $$j$$'s then $$u_{i+1}$$ is undefined. 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}$$.

### 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.

## 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+.