FANDOM


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

Sources

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

See also

Community content is available under CC-BY-SA unless otherwise noted.