**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:

- \(x_1\) is only 0's.
- 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})\).
- \(\{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:

- \(x_1\) is only 0's.
- 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})\).
- \(\{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:

- \(x_1\) is only 0's.
- 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})\).
- If \(x_{2m}\) lies in \([0,k]^k\), then \(x_{2m+1} = (k+(1/2),\text{us}(x_{2m}))\).
- If \(x_{2m}\) lies in \(\mathbb{Q}^k \setminus [0,k]^k\), then \(x_{2m+1} = \text{us}(x_{2m})\).
- If \(x_{2m} = (k+(1/2),z)\) lies in \(\mathbb{Q}^{k+1}\) then \(x_{2m+1} = \text{us}^{-1}(z)\).
- \(\{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^{+}. USGDCS_{2} eventually dominates all functions provably recursive in HUGE, but is itself provably total in HUGE^{+}.

## Sources

- ↑ http://www.cs.nyu.edu/pipermail/fom/2010-January/014282.html, with corrections from [1]
- ↑
^{2.0}^{2.1}http://www.cs.nyu.edu/pipermail/fom/2009-December/014276.html

## See also

**By Harvey Friedman:** Mythical tree problem · Friedman's vector reduction problem · Friedman's finite ordered tree problem · block subsequence theorem n(4) · Friedman's circle theorem · TREE sequence TREE(3) · subcubic graph number SCG(13) · transcendental integer · finite promise games · Friedman's finite trees · **Greedy clique sequence****Miscellaneous:** Factorial · Folkman's number · Exploding Tree Function · Graham's number · fusible number