1
$\begingroup$

Let $\Sigma$ be a finite alphabet, and consider the free monoid $\Sigma^*$. Given $w, w' \in \Sigma^*$ we say that $w$ overlaps $w'$ if there exist non-empty words $u, v, u'$ such that $w = uv$ and $w' = vu'$. Given a finite set of words $S$, define the overlap graph $OG(S)$ to be the simple graph with vertex set $S$ and an edge between two words in $S$ if one overlaps the other. In general this is defined as a weighted directed graph but in this case I do not care about direction or size of the overlaps.

I would like to understand better the cliques in $OG(S)$. In particular, I would like to know:

  1. Given a large enough clique, can we find a large subclique with some nicer properties?

  2. Is there a bound on the chromatic number $\chi(OG(S))$ in terms of the clique number $\omega(OG(S))$ and $| \Sigma |$?

These questions can be asked with some additional hypotheses on the words in $S$. In particular:

  1. What if all words in $S$ are unbordered? A word $w$ is bordered if there exist words $u, v$ such that $w = uvu$ and $u \neq \epsilon$.

  2. What if all words in $S$ are Lyndon words? A word $w$ is Lyndon for a given total order $\preceq$ on $\Sigma$ if it is primitive (i.e., not a positive power of another word) and smaller than all of its proper suffixes for the corresponding lexicographic order. All Lyndon words are unbordered.

All partial answers, as well as links to relevant literature, are welcome.

$\endgroup$
1
$\begingroup$

At least one of the questions admit counterexamples. Namely, let $\Sigma = \{a, b, c, d \}$, and $S = \{ ab^nc d ab^mc : n > m \}$. Then all words in $S$ are Lyndon, $OG(S)$ is triangle-free and has infinite chromatic number. I can give more details if anyone is interested.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.