The last section is on “Miscellaneous” problems. There are some weird ones in here, but we start with a pretty straightforward number problem.

**The problem: **Betweenness. This is problem MS1 in the appendix.

**The description: **Given a set C of triples (a,b,c), where each element of each triple comes from a superset A, can we find an ordering of the elements of A such that according to that ordering, each triple is in either increasing or decreasing order?

**Example: **It’s actually hard to do a good example for this because most groups of symbols (digits, letters, subscripts, …) have an implicit ordering of elements, and to go against that would be confusing. Having random symbols without connotations of meaning gets pretty confusing pretty quickly as well.

So let’s lean in and say A = {a,b,c,d,e,f} and our triples are:

(a,d,f)

(f,d,b)

(h,d,a)

(f,g,h)

(d,f,h)

We’re allowed any ordering of the elements of A, and the “normal” lexicographical one with ‘a’ first and ‘f’ last satisfies the betweenness rules.

But now suppose we add the new triple: (b,a,d). That is an illegal triple in our normal order, but if we change our ordering so that ‘b’ is first and ‘a’ is second, we can still satisfy all of the triples.

**Reduction: **The paper by Opatrny uses Hypergraph 2-Colorability (which we called “Set Splitting”). Recall that our reduction only made sets of size 3, so we can start with an instance where each set has at most 3 elements (or, each hyperedge connects at most 3 vertices).

So, suppose we have a set of N vertices s_{1}..s_{n}, a set of J 3-vertex hyperedges (a_{i}, b_{i}, c_{i}), as well as M 2-vertex “regular” edges (d_{i}, e_{i}).

Our first job is to build superset A. It has:

- One symbol for each vertex,
- A new symbol X.
- A set of J new symbols Y
_{k}, one for each 3-vertex hyperedge.

Now we build C.

- Each hyperedge (a
_{k}, b_{k}, c_{k}) generates two triples: (a_{k}, Y_{k}, b_{k}) and (Y_{k}, X, c_{k}) - Each two-vertex edge (d
_{k}, e_{k}) generates the triple (d_{k}, X, e_{k})

Suppose the graph had a 2-coloring. Recall that meant that each vertex had a color (the paper uses red and blue) so that each edge and hyperedge touches vertices of both colors. We need to make an ordering of A that satisfies all triples. The ordering will have positive, negative, and rational ranks.

- X has rank of 0.
- If vertex s
_{i}is red, its rank is i. If it’s blue, its rank is -i. - Each Y
_{i}was associated with a hyperedge (a_{i}, b_{i}, c_{i}).- If a
_{i}and b_{i}have the same color (and so the same sign), Y_{i}‘s rank is min(rank(a_{i}), rank(b_{i})) + . - If they have different colors, the rank is if c
_{i}is blue, and if c_{i}is red

- If a

So, suppose every edge had 2 colors. We know:

- If a
_{i}and b_{i}are the same color, they are the same sign, and Y_{i}is between them, satisfying the (a_{k}, Y_{k}, b_{k}) triple. - If a
_{i}and b_{i}are the same color, c_{i}must be the other color (and the other sign from Y_{i}), satisfying the (Y_{k}, X, c_{k}) triple. - If a
_{i}and b_{i}are different colors, they are different signs. Setting Y_{i}to a value between 1 and -1 satisfies the (a_{k}, Y_{k}, b_{k}) triple. - If a
_{i}and b_{i}are different colors, c_{i}can be either color, so making Y_{i}the opposite sign as c_{i}satisfies the (Y_{k}, X, c_{k}) triple. - An edge with just 2 vertices needs both vertices opposite colors, and thus opposite signs, so the (d
_{k}, X, e_{k}) triple is satisfied.

So far, so good. In the opposite direction, suppose we have a solution to the betweenness instance. We’ll assign colors to vertices such that a vertex’s color is red if its rank is > X’s rank. Otherwise, it will be assigned blue. Our triples will now allow any set of a_{i}, b_{i}, and c_{i} to all be greater than or less than X (or for both d_{i} and e_{i} to be greater than or less than X), which means that every edge in the hypergraph has both a red and a blue vertex.

**Difficulty: **7. It’s relatively easy to see what you need to do. It’s harder to make the numbers actually work. Even this paper has to resort to using rational numbers for the ranks, which is a fixable problem, but certainly not obvious.