The second week I was still mostly reading up on the background of what I am studying. As I mentioned previously, there is a beautiful new result by Michail Lampis on \(MSO_1\) model checking lower bounds for simple graphs (such as paths) which, as a corollary, contains the hardness result for cliques I was looking for (basically saying \(MSO_2\) model checking on cliques is not even in XP).

The idea of the result is actually simple enough for me to sum it up here. We want to prove that deciding some \(MSO_1\) -definable properties is hard already on paths. These are just about the simplest structures one can get -- their only distinguishable property is their length. The complexity assumption we're using for our proof is something a bit weaker than the usual \(P \neq NP\) -- this time we're assuming that \(P_1 \neq NP_1\) (where \(P_1\) and \(NP_1\) are the classes of unary languages decidable in polynomial deterministic / non-deterministic time). This assumption is equivalent to \(EXP \neq NEXP\) . For example assume that \(P_1 = NP_1\) -- then we can unary-code any language \(L \in NEXP\) with at most exponential blow-up and since this new \(L_{exp}\) is unary, we have \(L_{exp} \in NP_1 = P_1\) and thus \(L \in EXP\) .

What Lampis does in his paper then is to show that the rules for a
computation of a Turing machine can be encoded in a \(MSO_1\)
sentence
and this computation can be carried out *in unary*. It was previously
known that if we allow labelled paths (e.g. every vertex is either
black or white, encoding zeros and ones), paths can be viewed as
computations. The new result in Lampis' paper is that it can also be
done in unary. To achieve this Lampis had to show the existence of
some very concise formulas to compare the length of path segments; the
described construction is interesting in itself.

But the theorem I was looking for is not concerned with paths (remember that graphs with bounded neighborhood diversity have bounded diameter); it talks about the complexity of \(MSO_2\) (that is, formulas containing edge set quantifiers) model checking. But that follows from the theorem above easily: take an arbitrarily big clique and preface the formula with an \(\exists P \subseteq E, \varphi_{\text{path}}(P)\) , where \(\varphi_{\text{path}}(P)\) is a FO formula assuring that \(P\) is a path. Now use the previously described result.

Thus the answer is: yes, there is a \(MSO_2\)
definable problem, which
is hard (not even XP) already on cliques. But is that really what we
care about? How many natural problems model the computation of a
Turing machine? This remains an open question for us: is there a
*natural* W[1]-hard problem on graphs with bounded neighborhood
diversity when only the graph is the input? Also, Lampis' result seems
to be more of an evidence that \(MSO\)
logics are way stronger than we
need in most cases, rather than paths or cliques being complicated
graphs. Perhaps there are other logics that behave more nicely? Recent
paper by Michał Pilipczuk seems to
be going in that direction (but with regard to treewidth). So we have
some cues, but no specific results yet.

The rest of my time was dedicated to the study of *shrub-depth*, a
parameter generalizing neighborhood diversity. A fair amount of time
was consumed merely by getting familiar and comfortable with the
definitions, which I finally can claim to be. The goal I am trying to
achieve now is to generalize the coloring algorithm for graphs of
bounded neighborhood diversity to graphs of bounded shrub-depth,
specifically (to make matters simple) of shrub-depth 2.

I would like to explain the motivation in a bit more detail. The
hierarchy of discussed parameters is such that *clique-width* is the
most general and *vertex cover* is the most restrictive. The coloring
problem is W[1]-hard on graphs of bounded clique-width -- but is FPT
on graphs with bounded *tree-width*, which lies under clique-width,
but is incomparable with shrub-depth and neighborhood
diversity. Shrub-depth can be seen as forming a finer hierarchy
between vertex-cover and clique-width (omitting some details). If
coloring is hard for clique-width, but easy for tree-width and
neighborhood diversity, where does shrub-depth fall in? In other
words, where do things *break* -- when we go from neighborhood
diversity to shrub-depth, or when we go from shrub-depth to
clique-width?

To that end I have made some observations, but again, no definitive result yet.

It is worth mentioning that we spend the last three days in Princeton visiting a Spectral Methods mini-course. I have to say that Princeton is a beautiful place well worth seeing; the mini-course had its ups and downs, but overall I've enjoyed it (as did the rest of our group).

That's it for now. Wish me luck.