\section{Introduction}

This paper presents a new Byzantine fault tolerant (BFT) consensus algorithm that can work under asynchronous conditions. Like Hashgraph \cite{baird2016swirlds} and Aleph \cite{gkagol2018aleph}, it has no leaders, no round robin, no proof-of-work and reaches eventual consensus with probability one. It is also fully open, and a work-in-progress implementation written in Rust is available \cite{parsec}. Like HoneyBadger BFT \cite{miller2016honey}, this algorithm is built by composing a number of good ideas present in the literature. A gossip protocol is used to allow efficient communication between nodes \cite{guerraoui2010lifting}, as in Hashgraph \cite{baird2016swirlds}, Aleph \cite{gkagol2018aleph} and Avalanche \cite{rocket2018snowflake}.

The general problem of reaching Byzantine agreement on any value is reduced to the simpler problem of reaching binary Byzantine agreement on the nodes participating in each decision. This allows us to reuse the elegant binary Byzantine agreement protocol described in \cite{aba} after adapting it to the gossip protocol.

Finally, even though a trusted dealer (or another trusted external source of private key shares) is still required to initialise the instances of the algorithm (like in \cite{miller2016honey}), changes to the set of processes executing the instances (which we call \emph{dynamic membership}) can be made without the need for such external sources. The resulting algorithm is a Protocol for Asynchronous, Reliable, Secure and Efficient Consensus. PARSEC is a key building block of the SAFE Network, an ethical decentralized network of data and applications providing Secure Access For Everyone \cite{penland2016towards}.

The key contribution of this paper is the creation of an asynchronous BFT protocol, and which is resilient to 1/3 byzantine nodes. This is an optimal model. It also satisfies an agreement with probability one (unlike some probabilistic methods), and with a common coin for source of randomization that it respects the FLP impossibility result \cite{borowsky1993generalized}\cite{fischer1982impossibility}. The algorithm uses gossip for efficient and resilient communication. It is leaderless (with a caveat at network start-up) and the paper outlines how it can be adapted it to a dynamic membership context, while remaining leaderless after start-up. In comparable work, HBBFT (Honey Badger of BFT) has a less efficient communication mechanism with a secure broadcast \cite{miller2016honey}, and HashGraph is not rigorous in a liveness proof \cite{alpern1985defining} and where the published work only discusses the possibility of using a common coin in passing \cite{baird2016swirlds}. AlephZero \cite{gkagol2018aleph} is more recent than our initial work \cite{parsec} and is an improvement on HashGraph, and which also includes the use of a common coin. Avalanche \cite{rocket2018snowflake} differs from our work in that is uses a synchronous context. None of these methods, though, includes dynamic membership, and this is a key differentiator in this paper.

\section{Related work}

A gossip protocol has been likened to office workers spreading a rumour, and where Alice starts a new rumour, and then passes it to Bob, who then passes it to Dave. Alice then tells it to Frank, and who might have already heard it from Dave. In this way the rumour propagates quickly through a network, depending on the frequency that those spreading the rumours will pass them on.  The advantages of gossip protocols was outlined by \cite{birman2007promise} and who defined that they could be used with autonomic self-management, repair of inconsistencies, reliable multicast and distributed search. In actual operation, a gossip protocol involves a group of agents who hold private information, and who can communicate with each other. The core objective is for all of the agents to learn the private information \cite{apt2017computational}, and where distributed epistemic methods lead to simplified system models. A core weakness of the gossip protocols is that the dissemination of the rumour might not be radiated across a whole network of connections. Recent applications of gossip protocols has included the verifying the consistency of certificate logs \cite{chuat2015efficient}.

Honey Badger is Byzantine Fault Tolerant \cite{miller2016honey} which is asynchronous in its scope. It does not involve a leader node beyond the trusted setup phase and can cope with corrupted nodes. It does not actually make any commitments around the timing of the delivery of a message, and where even if Eve control the scheduling of messages, there will be no impact of the overall consensus. It can reach a consensus within an infrastructure of $f$ failed nodes, and where the total number of node ($N$) is greater than $3\times f$.

Hashgraph builds on the Directed Acyclic Graphs (DAG) approach \cite{baird2016swirlds} with gossip communications; \emph{gossip-about-gossip} methods; and Byzantine voting algorithms. The gossip-about-gossip method allows for the history of all the communications within an infrastructure to be reconstructed. Avalanche \cite{rocket2018snowflake} focuses on a scaleable electronic payment system. It uses synchronous communications with a leaderless BFT. In the face of adversaries, it uses a probabilistic safety guarantee.

\section{The algorithm description}

\subsection{The network model}

We assume the network to be a set $\mathcal{N}$ of $N$ instances of the algorithm communicating via asynchronous connections, which means that messages sent over these connections are all delivered eventually, but we make no assumptions regarding the delays between sending the message and its reception. In such a setup, it is impossible to distinguish between an instance failing by completely stopping and a large delay in message delivery.

We allow a possibility of up to $f$ Byzantine (arbitrary) failures, where $3f < N$. We will call
the instances that have not failed \emph{correct} or \emph{honest}, and the failing instances
\emph{faulty} or \emph{malicious} - as the Byzantine failure model allows for malicious behaviour
and collaboration. We will refer to any set of instances containing more than $\frac{2}{3}N$ of them as a \emph{supermajority}.

\subsection{Data structures}

A node executing the algorithm keeps two data structures: a \emph{gossip graph} and an
ordered set of \emph{blocks}. The vertices of the gossip graph, called \emph{gossip events},
contain the following fields:

\begin{itemize}
		\item Payload - data the node wants to pass to other nodes
		\item Self-parent (optional) - a cryptographic hash of another gossip event created by the
			same node
		\item Other-parent (optional) - a hash of another gossip event created by some other node
		\item Cause - cause of creation for this event; can be \emph{sync}, \emph{observation} or
			\emph{coin share}
		\item Creator ID - the public key of the event's creator
		\item Signature - a cryptographic signature of the above fields
\end{itemize}

The self-parent and other-parent are always present, except for the first events created by
respective nodes, as there are no parent events to be referred to in such cases. Other-parent is
also absent in events created because of an observation or a coin share - because there is no
gossip partner in such a case.

The blocks in the ordered set are network events signed by a subset of the nodes in the network.
This set is the output of the algorithm, and represents an order of network events that all nodes
agree upon. We call the blocks that are elements of the ordered set \emph{stable blocks}. Let us also define a few useful terms regarding the gossip graph for future use.

\begin{defn}
	We say that event $A$ is an \emph{ancestor} of event $B$ iff: $A = B$, or $A$ is an ancestor of
	$B$'s self-parent, or $A$ is an ancestor of $B$'s other-parent.
\end{defn}

\begin{defn}
	We say that event $A$ is a \emph{self-ancestor} of event $B$ iff: $A = B$, or $A$ is a
	self-ancestor of $B$'s self-parent.
\end{defn}

\begin{defn}
	We say that event $A$ is a \emph{descendant} of event $B$ iff $B$ is an ancestor of $A$.
\end{defn}

\begin{defn}
	We say that event $A$ is a \emph{self-descendant} of event $B$ iff $B$ is a self-ancestor of
	$A$.
\end{defn}

Following Hashgraph\cite{baird2016swirlds}, we also define two additional useful notions:

\begin{defn}
	An event $A$ is said to \emph{see} an event $B$ iff $B$ is an ancestor of $A$, and there
	doesn't exist any pair of events by $B$'s creator $B_1$, $B_2$, such that $B_1$ and $B_2$ are
	ancestors of $A$, but $B_1$ is neither an ancestor nor a descendant of $B_2$ (see fig.
	\ref{fig-seen}). We call a situation in which such a pair exists a \emph{fork}.
\end{defn}

\begin{defn}
	An event $A$ is said to \emph{strongly see} an event $B$ iff $A$ sees a set of events created
	by a supermajority of nodes in the system that all see $B$ (see fig. \ref{fig-stronglyseen}).
\end{defn}

\begin{figure}[!ht]
	\centering
	\begin{floatrow}
		\ffigbox[\FBwidth]{%
			\caption{d\_4 sees b\_0: b\_0 is its ancestor and there are no forks}
			\label{fig-seen}}{%
			\includegraphics[width=.4\textwidth]{seen.png}
		}
		\ffigbox[\FBwidth]{%
			\caption{a\_1 strongly sees b\_0: it sees itself, b\_1 and d\_1, which have been
			created by a supermajority of nodes and all see b\_0}
			\label{fig-stronglyseen}}{%
			\includegraphics[width=.4\textwidth]{strongly_seen.png}
		}
	\end{floatrow}
\end{figure}

\subsection{General overview of the algorithm}

The nodes execute two main steps in an infinite loop:

\begin{itemize}
		\item Synchronise the gossip graph with another random node
		\item Determine whether any new blocks should be appended to the ordered set
\end{itemize}

\subsubsection{Synchronisation}

This step is responsible for building the gossip graph and spreading information around the
network. Nodes continually make random calls, called \emph{sync calls}, to other nodes and exchange
information about the graph, so that all correct nodes end up with the same data in their graphs.
The hashes and signatures in gossip events make sure that malicious nodes won't be able to tamper
with any part of the graph.

Whenever a node receives a sync call, it creates a new gossip event. The self-parent of this event
is the hash of the last gossip event created by the recipient, and the other-parent is the hash of
the last event created by the sender (which the recipient learns about from the call). The new event
also stores the reason for which it was created (cause: \emph{sync}).

If the recipient of a sync call believes it knows a network event that should be appended as the
next one in the chain, it records its vote as the payload of the newly created event. The other
nodes will learn of this vote during subsequent sync calls made by its creator.

\begin{lem}\label{descendants}
	If A and B are correct nodes, then every event created by A will eventually have a descendant
	created by B.
\end{lem}

\begin{proof}
	This trivially follows from the network assumption that every message is eventually delivered, and
	from the fact that nodes continue to make sync calls, which result in the callee creating a
	descendant of the caller's last event.
\end{proof}

\subsubsection{Determining order}

During this step, a node analyses the graph, counts the votes and decides which block should become the next one. This step is a complex one and so it is described in detail in a separate subsection below.

\subsection{Calculating the order}

To be able to order blocks, we need first to have some blocks that can be ordered.

Every event has a set of \emph{interesting payloads} associated with it, which are some of the
network events its ancestors contain votes for. The exact way the set of interesting payloads is
calculated is left to the user; however, it has to satisfy some constraints:

\begin{itemize}
	\item If event $e$ has an interesting payload $p$, there exists an ancestor of $e$ containing a vote for $p$.
	\item If $e$ has an interesting payload $p$, no self-descendants of $e$ have an interesting
		payload $p$.
	\item If event $a$ has an interesting payload $p$, $a$ is an ancestor of event $e$ and $e$ has
		no self-ancestor having an interesting payload $p$, then $e$ has an interesting payload $p$.
	\item If $e$ has an interesting payload $p$, then no stable block contains $p$.
\end{itemize}

For example, $p$ might become an interesting payload of $e$ if $e$ has a single ancestor that
contains a vote for $p$. Another option is that $p$ only becomes an interesting payload if there is a supermajority of ancestors of $e$ containing votes for $p$. An event that has a non-empty set of interesting payloads is called an \emph{interesting event}.

From the first constraint on interesting payloads it follows that an interesting event always has a self-parent. Only the initial events have no self-parents, but they are their only ancestors, and they never contain votes, so they can't be interesting.

The first gossip event created by any given node which strongly sees interesting events created by a supermajority of nodes is said to be an \emph{observer}. The interesting events don't need to have the same interesting payloads - in fact, it is the case when they have different payloads that is the most interesting.

Since observers are descendants of interesting events, and interesting events always have
self-parents, it follows that observers always have self-parents as well. An observer implicitly carries a list of $N$ \emph{meta-votes}. Every meta-vote is just a binary value denoting whether a corresponding node's interesting event is to be taken into account when determining the order. An observer casts a meta-vote of $true$ on a node if it can strongly see an interesting event by that node. Each node casts a meta-vote on every node, hence each node casts $N$
meta-votes, and since an observer strongly sees a supermajority of interesting events, by
definition, more than $\frac{2}{3}N$ of them are $true$.

Meta-votes reduce the problem of Byzantine agreement about the order to that of binary Byzantine
agreement, which has been solved previously\cite{aba}. The algorithm described in \cite{aba}, like many ABFT algorithms, requires a device called a common coin. PARSEC is no different in this regard. In PARSEC, we utilise a common coin based on a threshold cryptography scheme using Boneh-Lynn-Shacham signatures \cite{bls}.

\subsubsection{Binary agreement}

For the sake of simplicity, we will define the algorithm in terms of deciding a single
\emph{meta-election} - that is, deciding whether or not to take a single node's opinion into
account when trying to choose a single new block. We can view a meta-election for node $X$ with
latest agreed block $B$ as a function on a subset $H_{X,B}$ of the gossip graph $G$, which is the
set of all events that are descendants of any observer of this meta-election:

\[ \mathsf{meta\_election}_{X,B}: H_{X,B} \to \{0, 1, \bot\} \]

The $\bot$ value means that the result has not been decided yet at this point in the graph.

Any gossip event which is an element of $H_{X, B}$ and is not an observer trivially has a
self-parent in $H_{X, B}$.

From this point on, until section \ref{nextblock}, whenever we mention a meta-election, we mean a
single meta-election regarding a single node, with a specific block $B$ being the last stable one.

In order to calculate the meta-election value for events in $H_{X,B}$, we will need to calculate a
few helper values as well:

\begin{itemize}
	\item $\mathsf{stage}$ - a counter denoting the calculation stage
	\item $\mathsf{estimates}$ - a set of one or two values estimating the final result
	\item $\mathsf{bin\_values}$ - a helper set of binary values
	\item $\mathsf{aux}$ - a helper binary value
\end{itemize}

$\mathsf{stage}$ is an integer value which represents the stage of the protocol we are considering
when looking at a specific gossip event. A number is associated with each gossip event, such that
the $\mathsf{stage}$ of the observers is always 0. The $\mathsf{stage}$ of any other gossip event
is either the $\mathsf{stage}$ of its self-parent, or the stage of its self-parent plus one under
specific conditions. The exact conditions under which the stage is incremented will be described
later in more details. Other variables such as $\mathsf{estimates}$, $\mathsf{bin\_values}$ and
$\mathsf{aux}$ all depend on the stage.

$\mathsf{estimates}$ (abbreviated $\mathsf{est}$) is a set of binary values that represent the
perceived opinion(s) of the creator of any gossip event on the outcome of a meta-election. The
initial $\mathsf{estimates}$ of an observer is the set containing just its own meta-vote, and it is
the set of the self-parent's $\mathsf{estimates}$ for other events, except the events which increase
the stage - it is then calculated from the results of the previous stage.

If the initial estimates for an event contain a single value $v$, and that event sees more than
$\frac{N}{3}$ events with $\neg v$ in their $\mathsf{estimates}$ (which means that at least one
honest node estimated $\neg v$), this opposite value gets added to its $\mathsf{estimates}$ (so it
will contain both true and false).

Note: the convention in function definitions below is that the value of the function is the first
value for which the corresponding condition is satisfied. We also use the common convention of $0$
denoting \emph{false}, and $1$ denoting \emph{true}.

\[ \mathsf{init\_est}: H_{X,B} \to 2^{\{0,1\}} \]
\[ \mathsf{init\_est}(e) = \left\{ \begin{array}{ll}
	\{ v \} & \textrm{if $e$ is an observer} \\
	& \textrm{with meta-vote $v$} \\
	\mathsf{next\_est}(\mathsf{self\_par}(e)) & \textrm{if $\mathsf{stage}(e) >
		\mathsf{stage}(\mathsf{self\_par}(e))$} \\
	\mathsf{est}(\mathsf{self\_par}(e)) & \textrm{otherwise}
\end{array} \right. \]

\[ \mathsf{est}: H_{X,B} \to 2^{\{0,1\}} \]
\[ \mathsf{est}(e) = \left\{ \begin{array}{ll}
	\{ v \} & \textrm{if there exists an ancestor $d$ of $e$} \\
	& \textrm{such that $v = \mathsf{meta\_election}(d) \neq \bot$} \\
	\{ 0,1 \} & \textrm{if $\mathsf{init\_est}(e) = \{v\}$} \\
	& \textrm{and $e$ sees $\geq\frac{N}{3}$ events $x$}\\
	& \textrm{by different nodes such that} \\
	& \textrm{$\mathsf{stage}(x) = \mathsf{stage}(e)$ and $\neg v \in \mathsf{est}(x)$} \\
	\mathsf{init\_est}(e) & \textrm{otherwise}
\end{array} \right. \]

$\mathsf{self\_par}(e)$ denotes $e$'s self-parent, and $\mathsf{next\_est}$ and $\mathsf{stage}$
will be defined later, once we have defined more values related to the events.

Once an event can see a supermajority of events by different nodes which agree in their estimates,
this agreed estimate becomes an element of this event's $\mathsf{bin\_values}$ (abbreviated
$\mathsf{bv}$). This set serves to validate values proposed by other nodes - if they propose
something we don't have in $\mathsf{bin\_values}$, we will reject it, as we have no way to ensure
its validity.

\[ \mathsf{bv}: H_{X,B} \to 2^{\{0,1\}} \]
\[ \mathsf{bv}(e)  =  \{ v: \begin{array}[t]{l} \textrm{there exist $> \frac{2}{3}N$ events $x$} \\
	\textrm{by different nodes such that} \\
	\textrm{$e$ sees $x$ and $\mathsf{stage}(e) = \mathsf{stage}(x)$ and $v \in \mathsf{est}(x)$} \\
	\textrm{or there exists an ancestor $d$ of $e$} \\
	\textrm{such that $\mathsf{meta\_election}(d) = v \neq \bot$}\}
\end{array}\]

\begin{figure}[!ht]
	\centering
	\includegraphics[width=\textwidth]{bvg.png}
	\caption{An example gossip graph, along with estimates and bin\_values
	associated with each gossip event. It illustrates how different nodes process the information
	they receive in order to populate their bin\_values.}
\end{figure}

If an event's parent has an empty $\mathsf{aux}$ value, and the event itself has non-empty
$\mathsf{bin\_values}$, it can propose a value to be agreed. This proposing is realised by having a
non-empty $\mathsf{aux}$ value. If $\mathsf{bin\_values}$ contains just one value, this value
becomes the $\mathsf{aux}$ value; otherwise, we can pick an arbitrary value, so we will pick true.
If the parent's value isn't empty, it becomes our value as well.

\[ \mathsf{aux}: H_{X,B} \to \{0, 1, \bot\} \]
\[ \mathsf{aux}(e) = \left\{ \begin{array}{ll}
	v & \textrm{if there exists an ancestor $d$ of $e$} \\
	& \textrm{such that $v = \mathsf{meta\_election}(d) \neq \bot$} \\
	\bot & \textrm{if $\mathsf{bv}(e) = \varnothing$} \\
	w & \textrm{if $\mathsf{bv}(e) = \{ w \}$} \\
	& \textrm{and $\mathsf{aux}(\mathsf{self\_par}(e)) = \bot$ } \\
	1 & \textrm{if $\mathsf{bv}(e) = \{ 0,1 \}$} \\
	& \textrm{and $\mathsf{aux}(\mathsf{self\_par}(e)) = \bot$ } \\
	\mathsf{aux}(\mathsf{self\_par}(e)) & \textrm{if $\mathsf{aux}(\mathsf{self\_par}(e))
		\neq \bot$}
\end{array}\right. \]

Whenever an event sees a supermajority of events with valid $\mathsf{aux}$ values, we perform the
common coin protocol (described in section \ref{commoncoin}), which will lead either to deciding
the final agreed value, or updating the estimates and moving to the next stage.

First, let us define some helper functions:

\[ \mathsf{supermajority\_valid\_aux}: H_{X,B} \to \{0,1\} \]
\[ \mathsf{supermajority\_valid\_aux}(e) = \begin{array}[t]{l}
	\textrm{$e$ sees a supermajority} \\
	\textrm{of events $x$ by different nodes} \\
	\textrm{such that $\mathsf{stage}(x) = \mathsf{stage}(e)$} \\
	\textrm{and $\mathsf{aux}(x) \in \mathsf{bv}(e)$}
\end{array} \]

\[ \mathsf{count\_aux}: H_{X,B} \times \{0, 1\} \to \mathbb{N} \]
\[ \mathsf{count\_aux}(e, v) = \begin{array}[t]{l}
	\textrm{number of events $x$ by different nodes such that} \\
	\textrm{$e$ sees $x$ and $\mathsf{stage}(x) = \mathsf{stage}(e)$} \\
	\textrm{and $\mathsf{aux}(x) \in \mathsf{bv}(e)$ and $\mathsf{aux}(x) = v$}
\end{array} \]

Now we can define how to determine a decided value:

\[ \mathsf{meta\_election}: H_{X,B} \to \{0, 1, \bot\} \]
\[ \mathsf{meta\_election}(e) = \left\{ \begin{array}{ll}
	v & \textrm{if there exists an ancestor $d$ of $e$} \\
	& \textrm{such that $v = \mathsf{meta\_election}(d) \neq \bot$} \\
	1 & \textrm{if $\mathsf{coin\_flip}(e) = 1$} \\
	& \textrm{and $\mathsf{count\_aux}(e, 1) > \frac{2}{3}N$} \\
	0 & \textrm{if $\mathsf{coin\_flip}(e) = 0$} \\
	& \textrm{and $\mathsf{count\_aux}(e, 0) > \frac{2}{3}N$} \\
	\bot & \textrm{otherwise}
\end{array} \right. \]

$\mathsf{coin\_flip}$ is the value of the common coin flip and will be defined later, in section
\ref{commoncoin}.

If an event sees a supermajority of valid $\mathsf{aux}$ values, but isn't able to decide, the next
event will mark the beginning of the next stage of the algorithm. This lets us finally define
$\mathsf{stage}$:

\[ \mathsf{stage}: H_{X,B} \to \mathbb{N} \]
\[ \mathsf{stage}(e) = \left\{ \begin{array}{ll}
	0 & \textrm{if $e$ is an observer} \\
	\mathsf{next\_stage}(\mathsf{self\_par}(e)) & \textrm{otherwise}
\end{array}\right. \]
\[ \mathsf{next\_stage}: H_{X,B} \to \mathbb{N} \]
\[ \mathsf{next\_stage}(e) = \mathsf{stage}(e) + \left\{ \begin{array}{ll}
	1 & \textrm{if $\mathsf{supermajority\_valid\_aux}(e)$} \\
	& \textrm{and $\mathsf{next\_est}(e) \neq \bot$} \\
	0 & \textrm{otherwise}
\end{array}\right.\]

If we don't decide in a stage, we need new estimates for the next one. This is being taken care of
by the common coin protocol briefly mentioned before, and described in more detail in section
\ref{commoncoin}.

In every stage, when the coin value is known, we can either decide or calculate the initial estimate
for the next stage. The general rule is this: we decide $v$ if we see a supermajority of
$\mathsf{aux}$ values of $v$ and the coin value is $v$. If we see a supermajority of $\mathsf{aux}$
values of $\neg v$ and the coin value is $v$, we estimate $\neg v$ in the next stage. If we don't
see any supermajority, we estimate the coin value in the next stage.

To calculate new estimates, we will define a $\mathsf{next\_est}$ function (which appeared already
in the definition of $\mathsf{est}$):

\[ \mathsf{next\_est}: H_{X,B} \to 2^{\{0,1\}} \cup \{ \bot \} \]
\[ \mathsf{next\_est}(e) = \left\{ \begin{array}{ll}
	\{v\} & \textrm{if $\mathsf{count\_aux}(e, v) > \frac{2}{3}N$} \\
	& \textrm{and $\mathsf{coin\_flip}(e) \neq \bot$} \\
	\{\mathsf{coin\_flip}(e)\} & \textrm{if $\mathsf{count\_aux}(e, 0) \leq \frac{2}{3}N$} \\
	& \textrm{and $\mathsf{count\_aux}(e, 1) \leq \frac{2}{3}N$} \\
	& \textrm{and $\mathsf{coin\_flip}(e) \neq \bot$} \\
	\bot & \textrm{otherwise}
\end{array} \right. \]

We can now start defining the $\mathsf{coin\_flip}$ function.

\subsubsection{Common coin}\label{commoncoin}

The common coin protocol is used to calculate the value of the coin flip in a stage. Every stage can
either have a predefined coin value, or demand a genuine flip. The exact pattern of which stage has
which option associated with it can be defined by the user, as long as there will be infinitely
many genuine flips with the stage number tending towards infinity (otherwise the termination
property of the algorithm - explained later in the paper - will not hold).

The simplest pattern would be to require a genuine flip at every stage. But other patterns
\cite{miller}, e.g. 1, 0, flip, 1, 0, flip\cite{trivial}, etc. can be used to avoid some of the
expensive flips, and optimise more for the optimistic case. Using fixed values at some stages may
speed up reaching consensus in some cases, as it doesn't require the exchange of coin shares and
returns the coin value right away.

For the genuine flip, the nodes do need to exchange coin shares. In order to define what they are,
let us first define the \emph{round hash} as follows. This hash will help us uniquely identify one
particular stage of a specific meta-election for a given node's meta vote:

\[ \mathsf{round\_hash}: H_{X,B} \to [0, 2^{256}) \]
\[ \mathsf{round\_hash}(e) = \mathsf{hash}( \mathsf{hash}(X), \mathsf{hash}(payload(B)),
	\mathsf{hash}(\mathsf{stage}(e))) \]

All nodes are assumed to possess private key shares - parts of a Boneh-Lynn-Shacham private key in a
threshold scheme, in which at least $\frac{N}{3}$ signature shares (signatures generated with
private key shares) are needed to reconstruct a full signature, and any $\frac{N}{3}$ signature
shares will result in the same, bit-by-bit identical signature. All nodes are also in possession of
public keys corresponding to all other nodes, so that they can verify each signature share
independently, as well as the full signature.

When a node creates an event $e$ with $\mathsf{stage}(e)$ corresponding to a genuine flip, that sees
a supermajority of aux values in its stage, it signs $\mathsf{round\_hash}(e)$ with its private key
share and publishes the resulting signature share in a gossip event with cause \emph{coin share}.
Once an event sees enough events with valid coin shares, it can collect them and calculate the full
signature, of which the lowest order bit will be taken as the coin flip value.

Let us define $\mathsf{count\_shares}$ analogously to $\mathsf{count\_aux}$:

\[ \mathsf{count\_shares}: H_{X,B} \times \{0, 1\} \to \mathbb{N} \]
\[ \mathsf{count\_shares}(e) = \begin{array}[t]{l}
	\textrm{number of events $x$ by different nodes such that} \\
	\textrm{$e$ sees $x$ and $\mathsf{stage}(x) = \mathsf{stage}(e)$} \\
	\textrm{and $x$ contains a valid coin share for $\mathsf{stage}(e)$} \\
\end{array} \]

The genuine flip can then be defined as:

\[ \mathsf{genuine\_flip}: H_{X,B} \to \{0,1,\bot\} \]
\[ \mathsf{genuine\_flip}(e) = \left\{ \begin{array}{ll}
	\textrm{lowest order bit} & \\
	\textrm{of the full signature} & \textrm{if $\mathsf{count\_shares}(e) \geq \frac{N}{3}$} \\
	\bot & \textrm{otherwise}
\end{array}\right. \]

Let us denote the set of stages with coin value fixed to 1 as $C_1$, the set of stages with coin
value fixed to 0 as $C_0$, and the set of genuine flip stages as $C_f$. The sets satisfy $C_1 \cup
C_0 \cup C_f = \mathbb{N}$, $C_1 \cap C_0 = C_1 \cap C_f = C_0 \cap C_f = \varnothing$, and
$|C_f| = |\mathbb{N}|$. Then, the full coin flip will be defined as follows:

\[ \mathsf{coin\_flip}: H_{X,B} \to \{0,1,\bot\} \]
\[ \mathsf{coin\_flip}(e) = \left\{ \begin{array}{ll}
	1 & \textrm{if $\mathsf{stage}(e) \in C_1$} \\
	0 & \textrm{if $\mathsf{stage}(e) \in C_0$} \\
	\mathsf{genuine\_flip}(e) & \textrm{if $\mathsf{stage}(e) \in C_f$}
\end{array}\right. \]

This is all we need to reach consensus on the meta-votes.

\subsubsection{Agreement about the next block}\label{nextblock}

Using the above, every node can calculate the results of all meta-elections. Once the results are
known, they can be used to determine the next block in the ordered set.

Let us remember that the meta-elections started with a set of observers - a set of events that all
strongly see a supermajority of interesting events. The results of the meta-elections tell us which
interesting events are to be taken into account.

The properties of meta-elections ensure that all nodes will agree on the considered set of nodes.
What we need to do is change that into an agreement on what the next block should be. This is
pretty trivial, although we must consider two issues: every node could create multiple interesting
events, and every interesting event could contain multiple interesting payloads.

To counter the first issue, we can just take the earliest interesting event created by a given node.
The events created by a single node form a linear sequence, so the earliest one is well-defined.
This narrows the considered set down to a single interesting event per node.

The next step is to choose a valid block among potentially multiple ones seen by the chosen
interesting event. To do that, we can take the lexicographically first one, or use really any method
that will always choose the same element of a set.

Once we have one vote on a block per node, we just count them and the next agreed block will be the
one with the most votes. Any ties can be broken again by lexicographic ordering, or some other
method.

It is also possible to repeat the steps above for other interesting payloads of the interesting
events that have been selected by the meta-election as an optimisation, so that a single
meta-election results in appending multiple stable blocks.

This completes the description of the algorithm. The next section will prove that it is correct,
that is, that it provides robust consensus in an asynchronous setting, and in the presence of
Byzantine faults.

\section{Proof of correctness}

Let us begin by stating two important properties of the gossip graph.

\begin{defn}
	We call two gossip graphs \emph{consistent} iff for every gossip event $x$ that is present in
	both graphs, both contain the same set of ancestors of $x$ with the same sets of edges between
	them.
\end{defn}

\begin{lem}\label{consistency}
	All nodes in the network have consistent gossip graphs.
\end{lem}

\begin{lem}\label{stronglysee}
	If a pair of gossip events $(x,y)$ is a fork, and another gossip event $z$ strongly sees $x$,
	then no other gossip event in a consistent graph can strongly see $y$.
\end{lem}

We won't prove the above lemmas - they have been proved in \cite{baird2016swirlds} (as Lemma 5.11 and 5.12,
respectively). Note that lemma \ref{stronglysee} only holds if $N > 3f$, but we assume that anyway.

Let us now prove some properties of our approach stemming from it being an adaptation of
\cite{aba}.

\begin{lem}[Interesting events]\label{interesting}
	If a correct node creates an interesting event with payload $p$, then all correct nodes will
	eventually create an interesting event with payload $p$.
\end{lem}

\begin{proof}
	Let $e$ be the event created by a correct node that has interesting payload $p$. By lemma
	\ref{descendants}, eventually every correct node will create a descendant of $e$. By the
	properties of interesting payloads, either this descendant or one of its self-ancestors will
	then have interesting payload $p$. Thus, for every correct node, there will be an event that is
	an interesting event with payload $p$, which completes the proof.
\end{proof}

\begin{lem}[Aux values]\label{aux}
	If all correct nodes created an event in stage $s$, then all correct nodes will eventually
	create an event with an $aux$ value in stage $s$.
\end{lem}

\begin{proof}
	Every event in stage $s$ has at least one estimate. There is a supermajority of correct nodes,
	so there will exist a value $v$ such that at least $N/3$ correct nodes have $v$ in estimates.
	Thus, there will exist a value $v$ that will eventually be estimated by all honest nodes, which
	means it will get promoted to bin-values by all honest nodes. Once $\mathsf{bin\_values}$ is
	not empty for an event, this event also has an aux value. Since all honest nodes will
	eventually create events with non-empty bin-values, these events will have aux values, which
	completes the proof.
\end{proof}

\begin{lem}[Progress]\label{progress}
	If a correct node created a gossip event in stage $s$, every other correct node will eventually
	create an event in stage $s$ as well.
\end{lem}

\begin{proof}
	Assume $s = 0$. The first gossip event in stage 0 is an observer. If a correct node created an
	observer, it must have strongly seen a supermajority of interesting events. A supermajority
	always contains a correct node, so at least one correct node created an interesting event. By
	lemma \ref{interesting}, all correct nodes will eventually have created interesting events.

	If all correct nodes created interesting events, it means that eventually all correct nodes will
	create an event strongly seeing a supermajority of interesting events - as there is a
	supermajority of correct nodes, they continue gossipping and they never fork. Thus, all correct
	nodes will eventually create observers, which completes the proof for $s = 0$.

	Assume the lemma holds for stage $s$. We will now prove that this implies it holds for stage
	$s+1$.

	Assume a correct node created an event in stage $s+1$. This means that this event sees a
	supermajority of events in stage $s$ with some \emph{aux} values. This means that at least one
	honest node created an event in stage $s$, so by our assumption, all honest nodes will have
	eventually created an event in stage $s$. By lemma \ref{aux}, this means that all honest nodes
	will eventually have created an event in stage $s$ with an aux value. All honest nodes will
	eventually create events that see all these events with aux values, which constitutes a
	supermajority, which is enough to progress to the next stage - so all honest nodes will create
	an event in stage $s+1$. By induction, the proof is complete.
\end{proof}

\begin{lem}\label{claima}
	If all correct nodes created events in stage $s$ and stage $s$ is a genuine flip stage, then the
	estimates of the nodes' events in the next stage will be in agreement with probability
	$\geq \frac{1}{2}$.
\end{lem}

\begin{proof}
	Let us consider the worst case scenario, in which there are $f$ malicious nodes among the
	$N = 3f + 1$ nodes. Let us also assume that the adversary controls the timing of the messages,
	so by controlling which messages are delivered when, they can control the gossip pattern and
	effectively, to some extent, the values associated with the gossip events.

	Assume the adversary tries to force a disagreement among the honest nodes. The only way to do so
	is to make some honest nodes see no agreeing supermajority among the aux values, which will make
	them take the coin value as the next estimate, and other honest nodes to see a supermajority
	of aux values opposite to the coin value. In other cases the honest nodes will automatically
	have agreeing estimates in stage $s+1$.

	The adversary cannot control the coin value, so they need to learn its value first. It is only
	possible if at least one honest node published its coin share, which means it has already seen
	a supermajority of aux values. Then, for the first $2f+1$ aux values seen by the correct node,
	exactly one of the following is true:

	\begin{itemize}
		\item There are at least $f+1$ \emph{true} aux values.
		\item There are at least $f+1$ \emph{false} aux values.
	\end{itemize}

	Whichever one is true, no matter what control the adversary has over the remaining aux values,
	it cannot make other honest nodes see a supermajority for the opposite value. Thus, it is out
	of the adversary's control to make the nodes disagree, as they couldn't have known beforehand
	which value they need to have a supermajority of.

	If there is no supermajority of agreeing aux values, the honest nodes will automatically be in
	agreement. If there is one and all of them see it, they will also be in agreement. If not all
	of them see it, there is a $\frac{1}{2}$ probability that the coin value will agree, thus also
	making all honest nodes agree.

	Thus, the probability of the honest nodes agreeing in stage $s+1$ is at least $\frac{1}{2}$.
\end{proof}

\begin{lem}\label{claimb}
	If all correct nodes' first events in stage $s$ had $\mathsf{estimates} = \{v\}$, either they
	will decide $v$ in stage $s$, or their first events in stage $s+1$ will also have
	$\mathsf{estimates} = \{v\}$.
\end{lem}

\begin{proof}
	If all correct nodes only estimate $v$, there is no way for any event to see even $\frac{N}{3}$
	of estimates for $\neg v$ - so no event by a correct node will have it in its estimates in
	stage $s$.

	For a value to be an element of $\mathsf{bin\_values}$, there must be a supermajority of events
	estimating that value. Because of the above, the only value that can have a supermajority is
	$v$. Thus, every event with nonempty $\mathsf{bin\_values}$ will have it equal to $\{v\}$.
	Hence, every event with an $\mathsf{aux}$ value will have it equal to $v$.

	In order to proceed to the next stage, an event has to see a supermajority of valid
	$\mathsf{aux}$ values. No event can have a value other than $v$ as $\mathsf{aux}$ in stage $s$,
	so there will always be a supermajority for $v$. Depending on the coin flip value, this can
	either lead to deciding $v$, or estimating $v$ in stage $s+1$. Either way, the agreement will
	still hold.
\end{proof}

\begin{lem}\label{decide}
	If all correct nodes' first events in stage $s$ had $\mathsf{estimates} = \{v\}$, they will all
	decide $v$ eventually.
\end{lem}

\begin{proof}
	No matter what malicious nodes do, there is less than a third of them, so no event by a correct
	node will have $\neg v$ in estimates (by definition of the $\mathsf{est}$ function). This means
	that for $\mathsf{bin\_values}$ of an event to be non-empty, it must see a supermajority of
	estimates for $v$, as there will never be a supermajority for $\neg v$.

	The above means that no correct node will add $\neg v$ to $\mathsf{bin\_values}$, so all of
	them will eventually create an event with $\mathsf{aux} = v$. This means there will be a
	supermajority of events by different creators with $\mathsf{aux} = v$, which will make the
	correct nodes either decide in stage $s$ (if $\mathsf{coin\_flip} = v$), or estimate $v$ for the
	next stage. This will repeat until $\mathsf{coin\_flip} = v$ and the nodes decide $v$. Since
	there will be infinitely many genuine flips with the number of stages tending to infinity, and
	each genuine flip will result in $v$ with probability $\frac{1}{2}$, this will eventually happen
	with probability 1.
\end{proof}

\begin{thm}[Binary Byzantine Consensus]\label{binconsensus}
	The algorithm for calculating meta-election results presented in this paper satisfies the
	general properties of a Byzantine fault tolerant consensus algorithm:
	\begin{itemize}
		\item \emph{Validity} - if a correct node decides on a value, it has been proposed by a
			correct node.
		\item \emph{Agreement} - if a correct node decides on a value, all correct nodes decide
			on that value.
		\item \emph{Integrity} - once a correct node decides on a value, it never decides on
			another value.
		\item \emph{Termination} - all correct nodes eventually decide with probability 1.
	\end{itemize}
\end{thm}

\begin{proof}[Validity]
	We will prove an equivalent statement: that if initially all correct nodes propose $v$, then
	all correct nodes will decide $v$. Since $v$ is a binary value, a node can only decide a value
	not proposed by a correct node if all correct nodes propose $v$, and the node decides $\neg v$.
	Thus, deciding $v$ when all correct nodes propose $v$ is equivalent to always deciding on a
	value proposed by a correct node.

	If all correct nodes propose $v$, they will all put $v$ in their estimates. By Lemma
	\ref{decide}, they will all decide $v$ eventually.
\end{proof}

\begin{proof}[Agreement]
	Assume there is an event $e$ created by a correct node which was able to decide a value $v$. It
	means that $\mathsf{coin\_flip}(e) = v$ and this event must have seen a supermajority of events
	with $\mathsf{aux} = v$. This means there was no supermajority for $\neg v$. Thus, if a correct
	node has seen a supermajority in this stage, it must have been for $v$, so it would decide $v$.
	If it hasn't, it would estimate $v$ for the next stage, which means there will be agreement at
	the start of the next stage. Following Lemma \ref{claimb}, this agreement will propagate to the
	end of the stage and the next stages, until everyone decides $v$.
\end{proof}

\begin{proof}[Integrity]
	Once an event $e$ created by a correct node decides on a value $v$, all later events created by
	that node will have event $e$ as an ancestor. Following the definition of
	$\mathsf{meta\_election}$, all later events will also decide $v$.
\end{proof}

\begin{proof}[Termination]
	By Lemma \ref{progress}, if a correct node creates an event in stage $s$, then every correct
	node eventually creates an event in stage $s$. This means there will be events by
	$> \frac{2}{3}N$ correct nodes, which will eventually be seen by every correct node.  Every
	such event will have non-empty estimates. It is not possible for both 0 and 1 to be estimated
	by $< \frac{N}{3}$ events by different correct nodes, so at least one of those values will
	eventually be an element of estimates of every correct node's event.

	Eventually, the events with agreeing estimates will all be seen by an event created by every
	correct node. Hence, every correct node will eventually create an event with non-empty
	$\mathsf{bin\_values}$, and so an $\mathsf{aux}$ value.

	The events with $\mathsf{aux}$ values will eventually be seen by every correct node's event,
	which means every correct node will eventually either decide or progress to the next stage.

	By Lemma \ref{claima}, after every stage with a genuine coin flip, all nodes' estimates agree
	with probability $> \frac{1}{2}$. This means that the probability of estimates still not
	agreeing at stage $s$ is less than:
	\[ (1 - \frac{1}{2})^{\mathsf{gf}(s)} = \frac{1}{2^{\mathsf{gf}(s)}} \]
	where $\mathsf{gf}(s)$ is the number of genuine flips up to stage $s$. Since we assume an
	infinite number of genuine flip stages as $s$ tends to infinity, $\mathsf{gf}(s)$ grows to
	infinity as $s$ grows, which implies that the probability of estimates not agreeing tends to 0.
	This means that the estimates will eventually agree with probability 1. By Lemma \ref{decide},
	the nodes will decide eventually after that happens.
\end{proof}

The above theorem proves that our algorithm will reach agreement about every single meta-election
in a Byzantine fault tolerant way. This is not the end, though - we also need to prove that
meta-elections lead to agreement about the next block in the ordered set. The proof of that is
presented below.

\begin{lem}\label{minvotes}
	If the result of a meta-election is $v$, there have been at least $\frac{N}{3}$ meta-votes for
	$v$.
\end{lem}

\begin{proof}
	Assume there have been less than $\frac{N}{3}$ meta-votes for $v$ and $v$ has been decided.
	When nodes that initially meta-voted $v$ create an event that sees a supermajority of
	meta-votes, this supermajority must contain at least $\frac{N}{3}$ votes for $\neg v$ - so
	their estimates will contain $\neg v$. On the other hand, no node that meta-voted $\neg v$ can
	ever create an event that will see at least $\frac{N}{3}$ estimates for $v$, so they won't add
	$v$ to estimates.

	Due to the above, any supermajority among the estimates must be for $\neg v$. Any event with
	non-empty $\mathsf{bin\_values}$ can thus only have $\neg v$ in this set, which means that
	all valid $\mathsf{aux}$ values will also be $\neg v$, which will lead to a decision on $\neg
	v$ eventually.

	This is a contradiction. Such a situation is impossible, which proves the lemma.
\end{proof}

\begin{lem}\label{nonempty}
	The set of nodes for which the result of meta-election is $true$ is always non-empty.
\end{lem}

\begin{proof}
	Assume all meta-elections resulted in $false$. By Lemma \ref{minvotes}, at least $\frac{N}{3}$
	nodes meta-voted $false$ for every node, so there have been at least $\frac{N^2}{3}$ meta-votes
	for $false$.

	On the other hand, by definition of an observer, every node voted $true$ for more than
	$\frac{2}{3}N$ nodes - so there have been more than $\frac{2}{3}N^2$ meta-votes for $true$,
	which leaves less than $\frac{N^2}{3}$ meta-votes for $false$ (there are $N^2$ meta-votes in
	total: $N$ nodes meta-vote in $N$ meta-elections).

	This is a contradiction, which proves the lemma.
\end{proof}

\begin{thm}[Byzantine Consensus]
	The algorithm for calculating the next block presented in this paper satisfies the general
	properties of a Byzantine fault tolerant consensus algorithm:
	\begin{itemize}
		\item \emph{Validity} - if a correct node decides on a next block, its payload was in at
			least one interesting event created by a correct node.
		\item \emph{Agreement} - if a correct node decides on a next block, all correct nodes decide
			on that block.
		\item \emph{Integrity} - once a correct node decides on a next block, it never decides on
			another block.
		\item \emph{Termination} - all correct nodes eventually decide with probability 1.
	\end{itemize}
\end{thm}

\begin{proof}[Validity]
	Assume that no correct node created an interesting event with payload $p$, but $p$ was still
	decided as the payload of the next block.

	This means that only faulty nodes could create interesting events with payload $p$, so there is
	less than $N/3$ such interesting events. Furthermore, if a correct node created a descendant of
	such an interesting event, then either it or one of its self-ancestors would have to be an
	interesting event with payload $p$ as well. This would contradict our assumption, so no correct
	node could have created a descendant of an interesting event with payload $p$.

	It follows from this that when correct nodes create observers, no such observer can meta-vote
	\emph{true} for a creator of an interesting event with payload $p$ (as it would require the
	observer to be a descendant of such an event). This means that after the meta-election is
	complete, no interesting event with payload $p$ will be taken into consideration, so $p$ will
	not be decided as the payload of the next stable block.

	QED by contradiction.
\end{proof}

\begin{proof}[Agreement]
	Assume that a correct node decided the next block $B$. Since a decision has been reached, this
	means that there is consensus about the meta-votes, so every correct node will have chosen the
	same nodes' interesting events.

	For any observer to meta-vote $true$ on a node, it must have strongly seen an interesting event
	by that node. By Lemma \ref{stronglysee}, even if that node created a fork, if any other
	observers also voted $true$ on that node, they must have strongly seen interesting events on the
	same fork. Thus, we can consider interesting events by all elected nodes to form linear
	histories - which will be seen the same way by all nodes by Lemma \ref{consistency}.

	In a linear history, the earliest interesting event is well-defined. Also, because all correct
	nodes see the same history, they will all choose the same interesting event as the earliest. If
	the interesting events has multiple payloads, all correct nodes will use the same tie-breaker
	algorithm and choose the same single one. Thus, all correct nodes will gather the same set of
	votes, and because they use the same voting rules, decide the same block as the next one.
\end{proof}

\begin{proof}[Integrity]
	By construction of the algorithm, once the next block has been decided, it is appended to the
	ordered set and no other block can be decided in its place.
\end{proof}

\begin{proof}[Termination]
	The consensus algorithm starts when a correct node creates an interesting event. Once that
	happens, by lemma \ref{interesting}, all correct nodes will eventually create interesting
	events, and this in turn implies that all of them will create observers. Once there is a
	supermajority of observers, we start the binary agreement algorithm, which will terminate by
	Theorem \ref{binconsensus}. After binary agreement terminates, because the set of voters for
	the next block is non-empty (by Lemma \ref{nonempty}), the next block is already determined -
	so the agreement about the next block also terminates.
\end{proof}

\section{Conclusions}

A new consensus algorithm has been presented, building upon some previous achievements in this
field (\cite{baird2016swirlds}, \cite{aba}), but combining their features in a novel way. It works under
asynchronous conditions, uses a gossip graph (like \cite{gkagol2018aleph}, \cite{baird2016swirlds} and \cite{rocket2018snowflake}),
and a common coin. It is also leaderless (barring the very initialisation of the network, when a
trusted dealer may be required) and an open source implementation is provided. We believe this
approach will be useful in numerous applications, one of which is the SAFE Network.


\section{Introduction}\label{sec:intro}

Independent sets in a graph count among the most studied objects of graph
theory, both for their theoretical and practical appeal.  An \emph{independent
set} in a graph is a set of vertices no two of which are adjacent.  This notion
is at the heart of graph colouring, where one tries to find a partition of the
vertex set of a graph in the smallest possible number of independent sets, this
number being the \emph{chromatic number} of the graph. It follows that
every graph~$G$ with chromatic number~$k$ has an independent set of size at
least~$|V(G)|/k$.  We investigate what kind of converse statement could be
true.  As is usual, we write~$\chi(G)$ for the chromatic number of~$G$
and~$\alpha(G)$ for the \emph{independence number} of~$G$, that is, the size of
a largest independent set in~$G$. Since we study the independence number of a
graph in relation to the number of its vertices, it is useful to define the
\emph{independence ratio}~$\ir(G)$ of a graph~$G$ (with at least one vertex) to
be~$\frac{\alpha(G)}{|V(G)|}$, and the \emph{minimum
independence ratio}~$\mir(G)$ to be~$\min\sst{\ir(H)}{\text{$H$ induced
subgraph of~$G$ with at least one vertex}}$.  (The inverse of the minimum independence ratio is
sometimes called the Hall ratio.) Let us start with a straightforward
observation. Every graph with chromatic number greater than~$2$ contains an
induced odd cycle, and the independence number of an odd cycle is less than
half the number of its vertices.  The contrapositive statement reads as follows.

\begin{observation}\label{obs-bip}
If every induced subgraph~$H$ of a graph~$G$ has independence ratio
at least~$\frac12$, then~$G$ has chromatic number at most~$2$.
\end{observation}

One could try to generalise \Cref{obs-bip} in several ways. For
instance, what about replacing the constant~$2$ by some larger integer~$k$?
This would yield an incorrect statement, as for each integer~$k\ge3$, there
is a graph with chromatic number greater than~$k$ and minimum independence ratio at least~$\frac{1}{k}$.
Indeed, let~$M_k$ be the $k^\text{th}$ Mycielski graph (so~$M_2$ is a cycle of length~$5$).
Then~$\chi(M_k)=k+1$ and, as is well known, every proper subgraph of~$M_k$ has chromatic number
at most~$k$, from which one infers that~$\mir(M_k)\ge\frac{1}{k}$ whenever~$k\ge3$.

Let us point out here that the exact value of the minimum independence ratio of
Mycielski graphs seems to be unknown. In~2006, Cropper, Gyarfás and
Lehel~\cite{CGL06} proved that every triangle-free graph is an induced subgraph
of a Mycielski graph and, using results on Ramsey numbers~\cite{AKS80,Kim95}
and on the fractional chromatic number of Mycieslki graphs~\cite{LPU95}, they
inferred the existence of two positive real numbers~$c_1$ and~$c_2$ such that
for every integer~$m\ge3$,
\[ c_1\cdot\frac{\sqrt{\log m}}{m} \le \mir(M_s) \le c_2\cdot\frac{\log m}{m}.\]
Here~$s$ is one less than the Ramsey number~$R(3,m)$, which is the largest integer~$n$
such that there exists an $n$-vertex triangle-free graph with independence number less than~$m$.
As is well known,~$R(3,m)=\Theta(m^2/\log m)$ (the lower bound was established by Kim~\cite{Kim95}
in~1995, while the upper bound had been proved fifteen years before by Ajtai, Komlós and Szemerédi~\cite{AKS80};
simpler proofs for the lower bound along with improvements of the multiplicative constant
were found subsequently~\cite{AKS81,Gri83,She91}).

Another way is to look for approximate generalisations of \Cref{obs-bip}.
Let us say that a graph is \emph{half-stable} if its independence ratio is at least one half.
\begin{question}\label{que-half}
Let~$k$ be a non-negative integer and~$G$ a graph. Assume that for every induced
    subgraph~$H$ of~$G$, there exists a set~$Y\subseteq V(H)$ of at most~$k$
    vertices such that~$H-Y$ is half-stable. Is it true that there
    exists a subset~$X\subseteq V(G)$ of at most~$k$ vertices such that
    $G-X$ is bipartite?
\end{question}
\noindent
Again this turns out to be false: for $k=1$, consider the graph obtained
from the cycle~$v_1v_2v_3v_4v_5v_6$ of length~$6$ by adding the triangle
$v_1v_3v_5$ (see Figure~\ref{fig:CEque-half}).

\begin{figure}[h]
  \centering
  \begin{tikzpicture}
    \tikzstyle{whitenode}=[draw,circle,fill=white,minimum size=9pt,inner sep=0pt]
    \tikzstyle{blacknode}=[draw,circle,fill=black,minimum size=7pt,inner sep=0pt]
    \tikzstyle{rednode}=[draw,circle,fill=red,minimum size=9pt,inner sep=0pt]
    \tikzstyle{greennode}=[draw,circle,fill=green,minimum size=9pt,inner sep=0pt]
    \tikzstyle{bluenode}=[draw,circle,fill=black!20!blue,minimum size=9pt,inner sep=0pt]
    \tikzstyle{texte}=[minimum size=0pt,inner sep=0pt]
 \draw (0,0) node[blacknode] (a) {}
-- ++(30+60:1cm) node[blacknode] (b) {}
-- ++(30+2*60:1cm) node[blacknode] (c) {}
-- ++(30+3*60:1cm) node[blacknode] (d) {}
-- ++(30+4*60:1cm) node[blacknode] (e) {}
-- ++(30+5*60:1cm) node[blacknode] (f) {};
\draw (f) -- (a) -- (c) -- (e) -- (a);
  \end{tikzpicture}
  \caption{A negative answer to Question~\ref{que-half} for $k=1$.}\label{fig:CEque-half}
\end{figure}

A more careful question was raised by Erd\H{o}s and Hajnal.
A graph satisfying the hypothesis of \Cref{que-half} has been
called \emph{$k$-near-bipartite} in the literature~\cite{Ree99}.
Erd\H{o}s and Hajnal conjectured (see~\cite{Gya97}) the existence of
a function~$g\colon\mathbf{N}\to\mathbf{N}$ such that every $k$-near-bipartite
graph~$G$ contains a set~$X$ of at most~$g(k)$ vertices such that~$G-X$ is bipartite.
This conjecture was confirmed by Reed~\cite{Ree99} in~1999.

Here is yet another way to weaken \Cref{que-half}: it was raised by Erd\H os
and Hajnal~\cite{ErHa66} and gave rise to a ``deep theorem'' (to quote
Gyárfás~\cite{Gya97}) demonstrated by Folkman~\cite{Fol69} in~1969.

\begin{restatable}[Folkman~\cite{Fol69}]{theorem}{folkman}\label{th:folkman}
Let~$k$ be a non-negative integer and~$G$ a graph.
    If for every induced subgraph~$H$ of~$G$, there exists a set~$Y\subseteq
V(H)$ of at most~$k$ vertices such that~$H-Y$ is half-stable,
then~$\chi(G)\leq k+2$.
\end{restatable}

The arguments developed by Folkman to demonstrate \Cref{th:folkman} are nice
and interesting.  However, they are difficult to access and it seems they
deserve more visibility.  The essence of Folkman's argument is not obvious to
see amongst the seventeen lemmas composing its proof, which is witnessed by the
fact that a simpler proof was asked for by Claude Tardif at a workshop  at the
University of Illinois in~2008~\cite{REGS08}.  Our goal is to present a much
more compact and shorter proof of \Cref{th:folkman}, which still relies on
Folkman's original idea, but with refined, factorised and sometimes generalised
statements.

We define the \emph{potential}~$\rho(H)$ of a graph~$H$ to be
$|V(H)|-2\alpha(H)+2$. Note that if a graph has potential~$k+2$ then one
can remove~$k$ vertices (but not fewer) to obtain a half-stable graph.  Given
a graph~$G$, let~$f(G)$ be the maximum of~$\rho(H)$ over all induced
subgraphs~$H$ of~$G$.  Note that if an induced subgraph~$H$ satisfies the property
mentioned in Theorem~\ref{th:folkman}, then~$\rho(H)\le k+2$, and hence
Theorem~\ref{th:folkman} can be reformulated
as~$\chi(G)\leq f(G)$ for every graph~$G$.  An induced
subgraph~$H$ of~$G$ is a \emph{witness} if $\rho(H)=f(G)$.
A $k$-colouring of a graph~$G$ is a mapping~$\varphi\colon V(G)\to\{1,2,\dotsc,k\}$
such that no two adjacent vertices have the same image under~$\varphi$.
If~$X$ is a subset of vertices of a graph~$G$, then~$G[X]$ is the subgraph of~$G$
induced by the vertices in~$X$ and~$G-X$ is the subgraph of~$G$ induced by
the vertices not in~$X$.

To demonstrate \Cref{th:folkman}, we use a simple, seemingly unrelated result,
which is a special case of a theorem proved by Hajnal~\cite{Haj65} in~1965.
A proof is included for completeness (the formulation and the argument are different
from what is customary seen).

\begin{proposition}[Hajnal~\cite{Haj65}]\label{lem:hellylikestables}
    If a graph~$G$ admits an independent set containing more than half of the vertices,
    then there exists a vertex contained in all maximum independent sets of~$G$.
\end{proposition}

\begin{proof}
We proceed by induction on the number~$e$ of edges of~$G$.
The statement is true if~$e$ is zero. Assume that~$e\ge1$ and the statement is true for graphs with fewer than~$e$
edges. Note that the statement is true if~$G$ has an isolated vertex, and hence
    we may assume by induction that~$G$ is connected.  If there is an edge~$e$
    such that~$\alpha(G-e)=\alpha(G)$, then by induction a vertex~$v$ is
    contained in all maximum independent sets of~$G-e$, and hence also in all
    those of~$G$ since each of them is also a maximum independent set of~$G-e$.
Thus it is enough to show that such an edge $e$ exists.
Arguing by contradiction, let us assume that~$\alpha(G-e)>\alpha(G)$ for every edge~$e$ of~$G$.

Let~$x$ be a vertex of~$G$ contained in the largest number of maximum
independent sets of~$G$.  Let~$G'$ be the graph obtained from~$G$ by
deleting~$x$ and all its neighbours. We show that the induction hypothesis can
be applied to~$G'$. Notice that adding~$x$ to any independent set of~$G'$
yields an independent set of~$G$, and hence~$\alpha(G')\le\alpha(G)-1$.  It
follows that~$\alpha(G')=\alpha(G)-1$ because~$x$ is contained in at least one
maximum independent set of~$G$.  Since~$G$ is connected and has more than one
vertex, we know that~$|V(G')|\le|V(G)|-2$, and therefore the induction
hypothesis applies to~$G'$, ensuring the existence of a vertex~$y$ of~$G'$
contained in every maximum independent set of~$G'$.  Consequently, $y$ is
contained in every maximum independent set of~$G$ that contains~$x$. The
definition of~$x$ thus ensures that a maximum independent of~$G$ contains~$x$
if and only if it contains~$y$.

To conclude, let~$z$ be a neighbour of~$x$. Since~$\alpha(G-xz)>\alpha(G)$,
there exists a maximum independent set~$I_x$ of~$G$ that contains~$x$ and such
that the only neighbour of~$z$ in~$I_x$ is~$x$. However, this implies
    that~$(I_x\setminus\{x\})\cup\{z\}$ is a maximum independent set of~$G$
containing~$y$ and not~$x$, a contradiction.
This concludes the proof.
\end{proof}

\section{Proof of \texorpdfstring{\Cref{th:folkman}}{Theorem 1.3}}\label{sec:proof}

We proceed by contradiction. Let~$G$ be a counter-example to
Theorem~\ref{th:folkman} with the fewest vertices. In particular, $\chi(G) \geq
f(G)+1$. If $f(G)=2$, \Cref{obs-bip} implies that~$G$ is bipartite, a contradiction. It follows that $f(G) \geq 3$, and hence~$\chi(G)\ge4$.

Note that every proper induced subgraph of~$G$ admits a $(\chi(G)-1)$-colouring. We
argue below that the graph satisfies a deeper critical property.

\begin{as}\label{lem:almost-critical}
For every subset~$X$ of vertices of~$G$,
\[\chi(G) \geq \chi(G[X])+\chi(G-X)-1.\]
\end{as}
\noindent
In particular,~\eqref{lem:almost-critical} implies that removing a
clique of size~$p$ in~$G$ results in a graph with chromatic number
either~$\chi(G)-p$ or~$\chi(G)-p+1$.

\begin{proof}[Proof of~\eqref{lem:almost-critical}]
The statement holds trivially if~$X$ or~$G-X$ is empty. Therefore,
    both~$G_1\coloneqq G[X]$ and~$G_2\coloneqq G-X$ have fewer
    vertices than~$G$. The minimality of~$G$ thus implies that none of~$G_1$
    and~$G_2$ is a counter-example to the statement of \Cref{th:folkman}.  For
    each~$i\in\{1,2\}$, let~$H_i$ be a witness of~$G_i$.  We
    have~$\rho(H_i)=f(G_i) \geq \chi(G_i)$.  We observe that $f(G) \geq
    \rho(G[V(H_1) \cup V(H_2)]) \geq \rho(H_1)+\rho(H_2)-2$, and hence~$f(G)
    \geq \chi(G_1)+\chi(G_2)-2$.  Since~$\chi(G) \geq f(G)+1$ by assumption,
the conclusion follows.
\end{proof}

\begin{as}\label{lem:evenholefree}
The graph~$G$ has no induced even cycle.
\end{as}
\begin{proof}
We proceed by contradiction. Assume that~$C$ is an induced even cycle of~$G$,
    and let~$2p$ be its length. Let~$A$ and~$B$ be the two maximum independent
    sets of~$C$.  We consider the graph~$G'$ obtained from~$G$ by merging all
    vertices of~$A$ in a single vertex~$a$ and all vertices of~$B$ in a single
    vertex~$b$, replacing every multi-edge that arises by a single edge (see
    Figure~\ref{fig:IllustrationA}).

Note that~$G'$ has fewer vertices than~$G$ and thus satisfies
    the conclusion of \Cref{th:folkman}.  It follows that
    \[f(G') \geq \chi(G') \geq \chi(G) \geq f(G)+1.\]

    \begin{figure}[h]
  \centering
  \begin{tikzpicture}
    \tikzstyle{whitenode}=[draw,circle,fill=white,minimum size=9pt,inner sep=0pt]
    \tikzstyle{ghost}=[draw=white,circle,inner sep=0pt]
    \tikzstyle{blacknode}=[draw,circle,fill=black,minimum size=7pt,inner sep=0pt]
    \tikzstyle{rednode}=[draw,circle,fill=red,minimum size=9pt,inner sep=0pt]
    \tikzstyle{greennode}=[draw,circle,fill=green,minimum size=9pt,inner sep=0pt]
    \tikzstyle{bluenode}=[draw,circle,fill=black!20!blue,minimum size=9pt,inner sep=0pt]
    \tikzstyle{texte}=[minimum size=0pt,inner sep=0pt]
\draw (0,0) node[blacknode] (a1) {}
--++ (45:1cm) node[blacknode] (b1) {}
--++ (180-45:1cm) node[blacknode] (a2) {}
--++ (180+45:1cm) node[blacknode] (b2) {};
\draw (a1) -- (b2);
\draw (a1)
--++ (-90:0.8cm) node[whitenode] (a1n) {};
\draw (b1)
--++ (0:0.8cm) node[whitenode] (b1n) {};
\draw (a2)
--++ (90:0.8cm) node[whitenode] (a2n) {};
\draw (b2)
--++ (180:0.8cm) node[whitenode] (b2n) {};
\draw[bend left=10,dotted,thick] (a1) edge node {} (a2);
\draw[dotted,thick] (b1) -- (b2);

\draw (b1)
++ (0:1.85cm) node (x) {$\leadsto$};

\draw (a1)
++ (0:5cm) node[ghost] (ta1) {}
++ (45:1cm) node[ghost] (tb1) {}
++ (180-45:1cm) node[ghost] (ta2) {}
++ (180+45:1cm) node[ghost] (tb2) {};
\draw (ta1)
++ (-90:0.8cm) node[whitenode] (ta1n) {};
\draw (tb1)
++ (0:0.8cm) node[whitenode] (tb1n) {};
\draw (ta2)
++ (90:0.8cm) node[whitenode] (ta2n) {};
\draw (tb2)
++ (180:0.8cm) node[whitenode] (tb2n) {};

\draw (b1)
++ (3:3.89cm) node[blacknode][label=90+45:$a$] (a) {};
\draw (b1)
++ (0:4.69cm) node[blacknode][label=45:$b$] (b) {};

\draw[bend left=10] (a) edge node {} (ta2n);
\draw[bend right=10] (a) edge node {} (ta1n);
\draw (a) -- (b) -- (tb1n);
\draw (b) edge node {} (tb2n);
  \end{tikzpicture}
  \caption{An example of the reduction from~$G$ to~$G'$ for~(\ref{lem:evenholefree}).}\label{fig:IllustrationA}
\end{figure}

Let~$H'$ be a witness of~$G'$, so~$\rho(H')\geq f(G)+1$.
    Let us consider the subgraph~$H$ of~$G$ induced by~$(V(H')\setminus\{a,b\})\cup V(C)$.
The potential~$\rho(H)$ of~$H$ can be bounded as follows.
\begin{align}\label{eq:fG}
    f(G) &\geq \rho(H)\notag\\
    &\geq \rho(H') + |V(C)|-2 - 2 (\alpha(H)-\alpha(H'))\notag\\
    &\geq f(G) + 2p-1 - 2 (\alpha(H)-\alpha(H')).
\end{align}

Clearly, $\alpha(H)-\alpha(H') \leq \alpha(C)=p$.
In fact, we must have $\alpha(H)-\alpha(H') \leq p-1$, as we now explain.
    Let~$I$ be a maximum independent set of~$H$. If~$|I\cap V(C)|\le p-1$,
    then~$I\cap V(H')$ is an independent set of~$H'$ of size at least~$\alpha(H)-(p-1)$.
    Otherwise, $I\cap V(C)\in\{A,B\}$, and hence one of~$(I\setminus V(C))\cup\{a\}$
    and~$(I\setminus V(C))\cup\{b\}$ is an independent set of~$H$ of size at least~$\alpha(H)-(p-1)$.

Plugging the inequality~$\alpha(H)-\alpha(H') \leq p-1$ into~\eqref{eq:fG} yields that
\[
f(G) \geq f(G)+2p-1 - 2 (p-1) > f(G),
\]
which is the desired contradiction.
\end{proof}

\noindent
We call \emph{diamond} the graph obtained from the complete graph on~$4$ vertices
by deleting an edge (see the graph induced by $u,v,x,y$ in Figure~\ref{fig:IllustrationC}).
\begin{as}\label{lem:nodiamond}
No induced subgraph of~$G$ is a diamond.
\end{as}

\begin{proof}
Let~$xy$ be an edge of~$G$. Let~$A$ be the set of common neighbors of~$x$
    and~$y$, and assume for a contradiction that~$A$ does not induce a clique.
    For every two distinct vertices~$u$ and~$v$ in~$A$ such that $uv \not\in
    E(G)$, let~$G_{uv}$ be the graph obtained from~$G-\{x,y\}$ by merging the
    two vertices~$u$ and~$v$ into a vertex, once again replacing every multi-edge
    that arises by a single edge (see Figure~\ref{fig:IllustrationC}).

\begin{figure}[h]
  \centering
  \begin{tikzpicture}
    \tikzstyle{whitenode}=[draw,circle,fill=white,minimum size=9pt,inner sep=0pt]
    \tikzstyle{ghost}=[draw=white,circle,inner sep=0pt]
    \tikzstyle{blacknode}=[draw,circle,fill=black,minimum size=5pt,inner sep=0pt]
    \tikzstyle{rednode}=[draw,circle,fill=red,minimum size=9pt,inner sep=0pt]
    \tikzstyle{greennode}=[draw,circle,fill=green,minimum size=9pt,inner sep=0pt]
    \tikzstyle{bluenode}=[draw,circle,fill=black!20!blue,minimum size=9pt,inner sep=0pt]
    \tikzstyle{texte}=[minimum size=0pt,inner sep=0pt]
\draw (0,0) node[blacknode][label=90:$x$] (x) {}
--++ (0:1cm) node[blacknode][label=90:$y$] (y) {};
\draw (x)
--++(-63.43:1.118cm) node [blacknode][label=-45:$v$] (v) {};
\draw (y) -- (v);

\draw (v)
++(0:0.75cm) node [whitenode] (w) {};
\draw (v)
++(180:0.6cm) node [blacknode][label=-90-45:$u$] (u) {};
\draw[dotted, thick] (u) -- (v);
\draw (x) -- (u) -- (y) -- (w) -- (x);
\draw (u)
--++(-90:1cm) node [whitenode] (un) {};
\draw (v)
--++(-90:1cm) node [whitenode] (vn) {};
\draw (x)
--++ (180:1cm) node [whitenode] (xn) {};
\draw (y)
--++ (0:1cm) node [whitenode] (yn) {};

\draw (v)
++ (0:2.5cm) node (z) {$\leadsto$};

\draw (x)
++ (0:5cm) node[ghost] (tx) {}
++ (0:1cm) node[ghost] (ty) {};
\draw (tx)
++(-63.43:1.118cm) node [ghost] (tv) {};

\draw (tv)
++(0:0.75cm) node [whitenode] (tw) {};
\draw (tv)
++(180:0.6cm) node [ghost] (tu) {};
\draw (tu)
++(-90:1cm) node [whitenode] (tun) {};
\draw (tv)
++(-90:1cm) node [whitenode] (tvn) {};
\draw (tx)
++ (180:1cm) node [whitenode] (txn) {};
\draw (ty)
++ (0:1cm) node [whitenode] (tyn) {};

\draw (u)
++ (0:5.3cm) node[blacknode][label=90:$w$] (tuv) {};
\draw (tun) -- (tuv) -- (tvn);

  \end{tikzpicture}
  \caption{An example of the reduction from $G$ to $G_{uv}$ for (\ref{lem:nodiamond}).}\label{fig:IllustrationC}
\end{figure}
\bigskip

\noindent
We prove the following statement.
\begin{sas}\label{cl:chi2}
For every two distinct vertices~$u$ and~$v$ in~$A$ that are not adjacent in~$G$,
\begin{enumerate}[(1)]
    \item\label{prop1}
    $\chi(G_{uv}) = \chi(G)-2$; and
    \item\label{prop2}
    in every $(\chi(G)-2)$-colouring of~$G_{uv}$, all colours appear on~$A$.
\end{enumerate}
\end{sas}

\begin{proof}
Let~$w$ be the vertex resulting from the identification of~$u$ and~$v$.  We
    first prove~\eqref{prop1}.  Let~$H$ be a witness of~$G_{uv}$. If~$H$
    contains~$w$, then we let~$H'$ be the subgraph of~$G$ induced by~$(V(H) \setminus
    \{w\}) \cup \{u,v,x,y\}$.  If~$H$ does not contain~$w$, then we let~$H'$ be
    the subgraph of~$G$ induced by~$V(H) \cup \{u,x,y\}$.  In either case, we observe
    that~$\rho(H')>\rho(H)$ because~$\alpha(H')\le\alpha(H)+1$. Consequently,
    we derive that $f(G_{uv})\leq f(G)-1 \leq \chi(G)-2$.

Because~$G_{uv}$ has fewer vertices than~$G$, we have $f(G_{uv})\geq
    \chi(G_{uv})$, and hence $\chi(G_{uv}) \leq \chi(G)-2$.  On the other hand,
    $\chi(G_{uv}) \geq \chi(G)-2$ also holds (from a $\chi(G_{uv})$-colouring
    of~$G_{uv}$, it suffices to keep the same colour on the vertices belonging
    to both graphs, assign the colour of~$w$ to each of~$u$ and~$v$, and the
    colours~$\chi(G_{uv})+1$ and~$\chi(G_{uv})+2$ to~$x$ and~$y$, respectively,
    to obtain a~$(\chi(G_{uv})+2)$-colouring of~$G$).  Therefore, $\chi(G_{uv})
    = \chi(G)-2$.

Let us now prove~\eqref{prop2}.  Suppose, on the contrary, that there is a
$(\chi(G)-2)$-colouring~$\varphi$ of~$G_{uv}$ contradicting~\eqref{prop2},
    and let~$c\in\varphi(V(G_{uv}))\setminus\varphi(A)$.  We derive from~$\varphi$ a
    $(\chi(G)-1)$-colouring of~$G$, which is a contradiction.
    Set~$c'=\chi(G)-1$, so~$c'\notin\varphi(V(G_{uv}))$.  We
    define~$\phi$ to be the colouring of~$G$ obtained from~$\varphi$ by
    colouring~$u$ and~$v$ with~$\varphi(w)$, colouring~$x$ with~$c$ and~$y$
    with~$c'$, and changing the colour of every neighbour of~$x$ that belongs
    to~${\varphi}^{-1}(\{c\})$ to~$c'$.  As~${\varphi}^{-1}(\{c\})$
    is an independent set disjoint from~$A$, and all common neighbours of~$x$ and~$y$
    belong to~$A$, we infer that~$\phi$ is a proper $(\chi(G)-1)$-colouring
    of~$G$.\renewcommand{\qed}{\cqedsymbol}
\end{proof}

We now consider the graph~$G'$ obtained from~$G-\{x,y\}$ by creating a
    vertex~$z$ with neighbourhood~$A$.  We observe that the existence of a
    $(\chi(G)-2)$-colouring of~$G'$ would contradict~\eqref{cl:chi2}.
    Indeed,~\eqref{cl:chi2} implies that~$|A|\ge\chi(G)-1$. It follows that
    if~$\varphi$ is a $(\chi(G)-2)$-colouring of~$G'$, then there exist two
    vertices~$u$ and~$v$ in~$A$ such that~$\varphi(u)=\varphi(v)$.
    Consequently,~$u$ and~$v$ are not adjacent in~$G$ and thus~$\varphi$ readily
    yields a $(\chi(G)-2)$-colouring of~$G_{uv}$ such that one colour,
    namely~$\varphi(z)$, does not appear on~$A$.  Therefore,~$\chi(G')\geq
    \chi(G)-1$, and hence~$f(G')\geq \chi(G') \geq f(G)$.

\begin{figure}[h]
  \centering
  \begin{tikzpicture}
    \tikzstyle{whitenode}=[draw,circle,fill=white,minimum size=9pt,inner sep=0pt]
    \tikzstyle{ghost}=[draw=white,circle,inner sep=0pt]
    \tikzstyle{blacknode}=[draw,circle,fill=black,minimum size=5pt,inner sep=0pt]
    \tikzstyle{rednode}=[draw,circle,fill=red,minimum size=9pt,inner sep=0pt]
    \tikzstyle{greennode}=[draw,circle,fill=green,minimum size=9pt,inner sep=0pt]
    \tikzstyle{bluenode}=[draw,circle,fill=black!20!blue,minimum size=9pt,inner sep=0pt]
    \tikzstyle{texte}=[minimum size=0pt,inner sep=0pt]
\draw (0,0) node[blacknode][label=90:$x$] (x) {}
--++ (0:1cm) node[blacknode][label=90:$y$] (y) {};
\draw (x)
--++(-63.43:1.118cm) node [blacknode][label=-45:$v$] (v) {};
\draw (y) -- (v);

\draw (v)
++(0:0.75cm) node [whitenode] (w) {};
\draw (v)
++(180:0.6cm) node [blacknode][label=-90-45:$u$] (u) {};
\draw[dotted, thick] (u) -- (v);
\draw (x) -- (u) -- (y) -- (w) -- (x);
\draw (u)
--++(-90:1cm) node [whitenode] (un) {};
\draw (v)
--++(-90:1cm) node [whitenode] (vn) {};
\draw (x)
--++ (180:1cm) node [whitenode] (xn) {};
\draw (y)
--++ (0:1cm) node [whitenode] (yn) {};

\draw (v)
++ (0:2.5cm) node (z) {$\leadsto$};

\draw (x)
++ (0:5cm) node[ghost] (tx) {}
++ (0:1cm) node[ghost] (ty) {};
\draw (tx)
++(-63.43:1.118cm) node [blacknode][label=-45:$v$] (tv) {};

\draw (tv)
++(0:0.75cm) node [whitenode] (tw) {};
\draw (tv)
++(180:0.6cm) node [blacknode][label=-90-45:$u$] (tu) {};
\draw (tu)
--++(-90:1cm) node [whitenode] (tun) {};
\draw (tv)
--++(-90:1cm) node [whitenode] (tvn) {};
\draw (tx)
++ (180:1cm) node [whitenode] (txn) {};
\draw (ty)
++ (0:1cm) node [whitenode] (tyn) {};

\draw (x)
++ (0:5.5cm) node[blacknode][label=90:$z$] (txy) {};
\draw (tu) -- (txy) -- (tv);
\draw (txy) -- (tw);
\draw[dotted, thick] (tu) -- (tv);
  \end{tikzpicture}
  \caption{An example of the reduction from~$G$ to~$G'$ for~(\ref{lem:nodiamond}).}\label{fig:IllustrationC2}
\end{figure}

Let~$H'$ be a witness of~$G'$, so~$\rho(H')\geq f(G)$. If~$z \in V(H')$, then
    the potential of the subgraph~$H_0$ of~$G$ induced by~$(V(H') \setminus \{z\}) \cup
    \{x,y\}$ is larger than that of~$H'$ because~$\alpha(H_0)\le\alpha(H')$. This
    is a contradiction since~$f(G)\le f(G')=\rho(H')$. In particular,~$H'$ is
    thus an induced subgraph of~$G-\{x,y\}$ and consequently we deduce
    that~$f(G)=\rho(H')$.  We also deduce that the potential of the subgraph
    of~$G'$ induced by~$V(H') \cup \{z\}$ is less than that of~$H'$, so there
    exists a maximum independent set of~$H'$ that is disjoint from~$A$.  If
    there is a vertex~$w \in A\setminus V(H')$, then the potential of the
    subgraph of~$G$ induced by~$V(H') \cup \{w,x,y\}$ is larger than that
    of~$H'$, a contradiction.
    Therefore~$A \subseteq V(H')$, and~$z \not\in V(H')$.

Let~$U = V(H') \setminus A$. We note that $|U|=|V(H')|-|A|$.
    From~\eqref{cl:chi2}, we derive that $|A|\geq \chi(G)-1 \geq f(G)=\rho(H')$.
    Therefore, $|U|\leq 2 \alpha(H')-2$. Set~$G_U = H'-A$, so~$G_U$ is
    the subgraph of~$G$ induced by~$U$.
It follows from the previous paragraph
    that~$\alpha(G_U)=\alpha(H')$, which is greater than~$\frac12\cdot|U|$.
    Proposition~\ref{lem:hellylikestables} therefore implies the existence of a
    vertex~$w$ in~$U$ such that every independent set of~$G_U$ that has
    size~$\alpha(H')$ contains~$w$.

We consider the subgraph~$H$ of~$G$ induced by~$(V(H') \setminus \{w\}) \cup
    \{x,y\}$.  Since its potential is at most~$f(G)$, there is a maximum
    independent set~$I$ in~$H$ of size~$\alpha(H')+1$. We observe that~$I$
    contains exactly one of~$\{x,y\}$, say~$x$ without loss of generality. We
    derive that~$I \setminus \{x\}$ is disjoint from~$A$, which is contained in
    the neighbourhood of~$x$. We note that $I \setminus \{x\}$ is an
    independent set of size $\alpha(H')=\alpha(G_U)$ that is contained in~$U$
    and does not contain~$w$, a contradiction.
\end{proof}

Equipped with all these properties, we may now finish the proof of
Theorem~\ref{th:folkman}. We start by proving that~$G$ has no triangle.
Choose a maximum clique~$K$ of~$G$, and let~$\omega$
be its size. We let~$u_1,u_2, \dotsc, u_\omega$ be the vertices of~$K$ and we
set~$G_K = G-K$.  For every~$i\in \{1,2,\dotsc,\omega\}$, we let~$N_i$ be
the neighbourhood of~$u_i$ in~$G_K$. By~\eqref{lem:nodiamond}, and because~$K$
is maximum, the sets~${(N_i)}_{1\le i\le \omega}$ are pairwise disjoint.
Moreover,~\eqref{lem:evenholefree} implies that they are pairwise non-adjacent,
that is, if~$G$ has an edge with one end-vertex in~$N_i$ and the other
in~$N_j$, then~$i=j$.

\begin{figure}[h]
  \centering
  \begin{tikzpicture}
    \tikzstyle{whitenode}=[draw,circle,fill=white,minimum size=9pt,inner sep=0pt]
    \tikzstyle{ghost}=[draw=white,circle,inner sep=0pt]
    \tikzstyle{blacknode}=[draw,circle,fill=black,minimum size=5pt,inner sep=0pt]
    \tikzstyle{rednode}=[draw,circle,fill=red,minimum size=9pt,inner sep=0pt]
    \tikzstyle{greennode}=[draw,circle,fill=green,minimum size=9pt,inner sep=0pt]
    \tikzstyle{bluenode}=[draw,circle,fill=black!20!blue,minimum size=9pt,inner sep=0pt]
    \tikzstyle{texte}=[minimum size=0pt,inner sep=0pt]
\draw (0,0) node[blacknode][label=110:$u_2$] (v2) {}
--++ (0:1cm) node[blacknode][label=70:$u_1$] (v1) {};
\draw (0.5,0.85) node [blacknode][label=45:$u_3$] (v3) {};
\draw (v1) -- (v3) -- (v2);
\draw (v3)
--++ (90:1cm) node[whitenode] (nv3) {$\ 3\ $};
\draw (v1)
--++ (0:1cm) node[whitenode] (n1v1) {$\ 1\ $};
\draw (v1)
--++ (-60:1cm) node[whitenode] (n2v1) {$\ 1\ $};
\draw (v2)
--++ (180:1cm) node[whitenode] (n1v2) {$\ 1\ $};
\draw (v2)
--++ (180+60:1cm) node[whitenode] (n2v2) {$\ 4\ $};
\draw (n1v2) -- (n2v2);

\draw (v1)
++ (0:1.8cm) node (z) {$\leadsto$};

\draw (4.6,0) node[whitenode] (dv2) {$\ 2\ $}
--++ (0:1cm) node[whitenode] (dv1) {$\ 1\ $};
\draw (0.5+4.6,0.85) node [whitenode] (dv3) {$\ 3\ $};
\draw (dv1) -- (dv3) -- (dv2);
\draw (dv3)
--++ (90:1cm) node[whitenode] (dnv3) {$\ 3\ $};
\draw (dv1)
--++ (0:1cm) node[whitenode] (dn1v1) {$\ 1\ $};
\draw (dv1)
--++ (-60:1cm) node[whitenode] (dn2v1) {$\ 1\ $};
\draw (dv2)
--++ (180:1cm) node[whitenode] (dn1v2) {$\ 1\ $};
\draw (dv2)
--++ (180+60:1cm) node[whitenode] (dn2v2) {$\ 4\ $};
\draw[densely dotted, very thick,red] (dv3) -- (dnv3);
\draw[densely dotted, very thick,red] (dv1) -- (dn1v1);
\draw[densely dotted, very thick,red] (dv1) -- (dn2v1);

\draw (dv1)
++ (0:1.8cm) node (dz) {$\leadsto$};

\draw (9.2,0) node[whitenode] (tv2) {$\ 2\ $}
--++ (0:1cm) node[whitenode] (tv1) {$\ 1\ $};
\draw (0.5+9.2,0.85) node [whitenode] (tv3) {$\ 3\ $};
\draw (tv1) -- (tv3) -- (tv2);
\draw (tv3)
--++ (90:1cm) node[whitenode] (tnv3) {$\ c\ $};
\draw (tv1)
--++ (0:1cm) node[whitenode] (tn1v1) {$\ c\ $};
\draw (tv1)
--++ (-60:1cm) node[whitenode] (tn2v1) {$\ c\ $};
\draw (tv2)
--++ (180:1cm) node[whitenode] (tn1v2) {$\ 1\ $};
\draw (tv2)
--++ (180+60:1cm) node[whitenode] (tn2v2) {$\ 4\ $};

\draw (dn1v2) -- (dn2v2);
\draw (tn1v2) -- (tn2v2);
  \end{tikzpicture}
  \caption{An example of the colouring extension when $\omega(G) \geq 3$.}\label{fig:IllustrationClique}
\end{figure}

Suppose, for a contradiction, that~$\omega\ge3$.
We deduce from~\eqref{lem:almost-critical} that $\chi(G_K) \leq \chi(G)-2$.
Let~$\varphi$ be a $(\chi(G)-2)$-colouring of~$G_K$.  We argue how to obtain
from~$\varphi$ a $(\chi(G)-1)$-colouring of~$G$, which would be a contradiction.
Set~$c = \chi(G)-1$, so~$c\notin\varphi(V(G_K))$. Colour every
vertex $v$ not in~$K$ with~$\varphi(v)$.  For each~$i\in\{1,2,\dotsc,\omega\}$, colour~$u_i$
with colour~$i$, and next recolour every vertex in~$N_i\cap{\varphi}^{-1}(\{i\})$
with colour~$c$.  Since the sets~${(N_i)}_{1\le i\le \omega}$ are pairwise
non-adjacent and we recolour an independent set in each set~$N_i$, we obtain a
proper colouring of~$G$. And since~$\chi(G)-1\ge\omega$, because~$\chi(G)>f(G)\ge\omega$,
this colouring uses less than~$\chi(G)$ colours, a contradiction.
Therefore, the graph~$G$ contains no triangle.

Consider a shortest cycle~$C$ in~$G$ (there is one since $\chi(G)> f(G) \geq
2$). By~\eqref{lem:evenholefree} and the previous argument, we have
$|V(C)|=2p+1$ where $p \geq 2$. Let $v_1,v_2,\dotsc, v_{2p+1}$ be the vertices
on~$C$, consecutively. Let~$N'_i$ be the set of neighbours of~$v_i$ not in~$C$.
Note that every vertex not in~$C$ has at most one neighbour in~$C$, for
otherwise~$G$ would contain either an odd cycle shorter than~$C$ or an induced
even cycle, thereby contradicting~\eqref{lem:evenholefree}.  Consequently, the
sets~${(N'_i)}_{1\le i\le 2p+1}$ are pairwise disjoint.  It also follows
from~\eqref{lem:evenholefree} that the sets~${(N'_i)}_{1\le i\le 2p+1}$ are
pairwise non-adjacent.

Let~$G_C = G-C$.
By~\eqref{lem:almost-critical}, we obtain a $(\chi(G)-2)$-colouring~$\varphi$
of~$G_C$. Similarly as before, we argue how to deduce from~$\varphi$ a
$(\chi(G)-1)$-colouring~$\phi$ of~$G$, hence obtaining the final
contradiction. Recall that~$\chi(G)\ge4$.  For~$i \in \{1,2,\dotsc,p\}$, we
colour~$v_{2i}$ with colour~$1$ and~$v_{2i-1}$ with colour~$2$. We
colour~$v_{2p+1}$ with colour~$3$.  Set~$c = \chi(G)-1$,
so~$c\notin\varphi(V(G_C))$.  For each~$i\in\{1,2,\dotsc,2p+1\}$, every vertex
in~$N'_i\cap {\varphi}^{-1}(\phi(v_i))$ is coloured with colour~$c$. We
define~$\phi$ to be equal to~$\varphi$ on all the remaining vertices of~$G$.
Similarly as before, the properties of the sets~${(N'_i)}_{1\le i\le 2p+1}$
ensure that~$\phi$ is a proper~$(\chi(G)-1)$-colouring of~$G$.  This
contradiction concludes the proof of the theorem.

\section{Conclusion}

With now a clear understanding of why Theorem~\ref{th:folkman} holds, it is tempting to look for a strengthening of the theorem. We already discussed in Section~\ref{sec:intro} some natural generalisations of the statement that unfortunately do not hold.
In this section, we conclude this work with a discussion of other potential generalisations.
Let us first restate Theorem~\ref{th:folkman} as follows, where the notation~$H \subseteq_i G$ means that~$H$ is an induced subgraph of~$G$.

\begin{usethmcounterof}{th:folkman}[Folkman~\cite{Fol69}]
For every graph~$G$,
    \begin{equation}\label{eq-folkman}
\chi(G) \leq \max_{H \subseteq_i G} ( |V(H)|-2\cdot(\alpha(H)-1)).
    \end{equation}
\end{usethmcounterof}

The parameter~$\alpha(H)$ can be interpreted as ``the size of the largest induced subgraph of~$H$ with chromatic number~$1$''.
This suggests a new approach for a generalisation. For every positive integer~$p$, define~$\alpha_p(H)$ as the size of a largest induced subgraph of~$H$ with chromatic number at most~$p$.

\begin{question}\label{que-HigherChi}
Given a positive integer~$p$, does there exist~$c_p > 1$ such that for every graph~$G$,
\[\chi(G) \leq \max_{H \subseteq_i G} \big( |V(H)|-c_p\cdot(\alpha_p(H)-p)\big)?\]
\end{question}

Note that the inequality holds for~$c_p \leq 1$ by taking~$H=G$. Theorem~\ref{th:folkman} answers the case~$p=1$ of Question~\ref{que-HigherChi} in the affirmative, showing that~$c_1$ can even be taken as high as~$2$.
Before considering larger values of~$p$, let us point out that~$c_1=2$ is best possible.
Indeed, suppose that~$c_1>2$ and take~$G$ to be the odd cycle~$C_5$.
Because~$\chi(C_5)=3$ and~$c_1>2$, the maximum in the right side of~\eqref{eq-folkman} must
be attained by~$H$ being the null graph (that is, $V(H)=\varnothing$), implying that $c_1
\geq 3$.  However, the Mycielski graph~$M_{c'_1}$, where~$c'_1 =
\lfloor c_1 \rfloor$, now contradicts the desired inequality.
Since~$\chi(M_{c'_1})=c'_1+1$, taking~$H$ to be the null graph is not
sufficient to ensure the inequality. Moreover, as~$c'_1\ge3$ we know
that~$\mir(M_{c'_1})\ge\frac1{c'_1}$ (as mentioned in the introduction), and
hence~$\alpha(H)\ge|V(H)|/c'_1$ whenever~$H$ is a non-null induced subgraph
of~$M_{c'_1}$. It follows that, in this case, $|V(H)|-c_1(\alpha(H)-1) \leq
|V(H)|-c'_1(\alpha(H)-1)\le c'_1<\chi(M_{c'_1})$, a contradiction.  This shows
that~$c_1=2$ is best possible.

For larger values of~$p$, it turns out that the answer to
Question~\ref{que-HigherChi} is always negative. First note that since
$\alpha_{p+1}(H) \geq \alpha_p(H)+1$ in any graph~$H$ with chromatic number
higher than~$p$, a negative answer for a positive integer~$p_0$ implies a negative answer for
every integer~$p\ge p_0$. We now explain why the answer is negative for~$p=2$.

For simplicity, we define~$f_2(G)$ to be
\[
\max_{H \subseteq_i G} \big( |V(H)|-c_2\cdot(\alpha_2(H)-2)\big).
\]
Let~$\ell \geq 2$.  For~$k\geq 2$, let~$M'_{k,\ell}$ be obtained by
applying~$k-2$ times the Mycielski construction to the cycle on~$2\ell+1$
vertices. Note that~$M'_{k,2}$ is the standard Mycielski graph~$M_k$.

Suppose by contradiction that~$c_2>1$.
We prove by induction on~$k$ that for every~$k \geq 1$, we have~$c_2 \geq \frac{k+1}2$.
For~$k=1$, this is true by our assumption that~$c_2>1$.
For~$k\geq 2$, we consider~$f_2(M'_{k,\ell})$ for~$\ell$ large enough in terms of~$k$.

If the maximum in the definition of~$f_2(M'_{k,\ell})$ is attained on the null
graph, then we obtain~$2 c_2\geq \chi(M'_{k,\ell})=k+1$ as desired.  Thus we
may assume this is not the case.  If the maximum is attained on a proper
non-null induced subgraph~$H$, then~$H$ is $k$-colourable and thus
satisfies~$\alpha_2 (H) \geq \frac{2 |V(H)|}{k}$.  Since~$H$ gives a higher
value than that given by the null graph in the definition
of~$f_2(M'_{k,\ell})$, we deduce that
\[
|V(H)|-c_2\cdot(\alpha_2(H)-2) > 2c_2.
\]
However, using that~$c_2 \geq \frac{k}{2}$ (by induction), we obtain~$\alpha_2
(H) < \frac{2 |V(H)|}{k}$, a contradiction.

It follows that the maximum in the definition of~$f_2(M'_{k,\ell})$ is attained by~$M'_{k,\ell}$ itself.
Observe that $|M'_{k,\ell}|=(\ell+1)\cdot 2^{k-1}-1$ and $\alpha_2 (M'_{k,\ell})=\ell \cdot 2^{k-1}$.
Consequently, \[
f_2(M'_{k,\ell})=
(\ell+1)\cdot 2^{k-1}-1
- c_2 \cdot (\ell \cdot 2^{k-1}-2)
\geq \chi(M'_{k,\ell}) = k+1,
\]
which does not hold for~$\ell$ large enough in terms of~$k$, since $c_2>1$.
Therefore, this last case cannot occur either, and~$c_2 \geq \frac{k+1}2$ holds, as announced.

In summary, we have shown that~$c_2>1$ implies that~$c_2 \geq \frac{k+1}2$ for
every positive integer~$k$, and hence that~$c_2$ is unbounded, a contradiction.  We
conclude that~$c_2 \leq 1$ must hold.

Given this state of affairs, it was suggested to one of the
authors to try and replace~$\alpha_2(H)$ with the maximum size of an induced
subgraph of~$H$ isomorphic to a bipartite cograph.  However, the answer remains
negative even when considering the maximum size of an induced subgraph of~$H$
isomorphic either to a complete bipartite graph with one side of size at
most~$2$ or to~$P_1+P_2$, the graph on three vertices with only one edge. To
see this, it suffices to apply Mycielski's construction once on a large clique,
and to do the arithmetic for various cases depending on the structure of a
subgraph attaining maximum potential (whether it contains more vertices of the
clique than of the maximum stable set, and whether it contains the unique
vertex whose neighbourhood is a stable set). While this supersedes the above
argument that~$c_2 \leq 1$, the proof is decidedly non-illuminating, and we
refrain from including it here. Considering how restricted the replacement
for~$\alpha_2(H)$ is here, generalising Theorem~\ref{th:folkman} in this
direction does not seem feasible either.

Our original motivations for finding a short proof of Theorem~\ref{th:folkman}
were to make sense of the statement and understand what bigger truth it could be
part of. With the new-found insight, Theorem~\ref{th:folkman} seems all the
more to be a truly isolated statement, almost a singularity in the realm of
graph colouring.

\section*{Acknowledgements}
This research was started at the Graph Theory meeting in Oberwolfach in
January~2019. Thanks to the organizers and to the other workshop participants
for creating a productive working atmosphere.
Thanks to Paul Seymour for stimulating discussions on this topic.