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 Edit

Background Edit

\(\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 Edit

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.

\(\mathbf{x}\) is an upper shift greedy clique sequence iff:

  1. \(x_1\) is only 0's.
  2. Let \(m\) be a positive integer such that \(2 \leq 2m \leq n - 1\). 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, 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\}\).

\(\mathbf{x}\) is an upper shift greedy down clique sequence iff:

  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, 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]

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 iff \(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 Edit

We define the following fast-growing functions:

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

Growth rates Edit

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 Edit

  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 Edit

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.