What is the minimum length of maximal palindrome of a binary word of length $n$? For example if we have $n=4$ then the minimum length of maximal palindrome is $2$. Here are all four digit possible binary words along with their maximal palindromes:
0000 0000
0001 000
0010 010
0011 00 , 11
0100 010
0101 101
0110 0110
0111 111
1000 000
1001 1001
1010 010
1011 101
1100 11, 00
1101 101
1110 111
1111 1111

Is the solution $[n/2]$? Is there a proof for that?
 A: Whatever the answer is, it's definitely asymptotically much less than $n/2$. For example, suppose you build a string of a single 0, followed by 2 1's, followed by 3 0's, followed by 4 1's, etc. Then the maximal palindrome substring length will be $O(\sqrt{n})$. So the answer is definitely less than or equal to $c \sqrt{n}$ for some universal constant $c$.
A: I wrote a paper with Narad Rampersad back in 2005:  Words avoiding reversed subwords, J. Combin. Math. Combin. Comput., 54 (2005), 157-164.
https://cs.uwaterloo.ca/~shallit/Papers/ras-reversed.pdf
In Theorem 4 we prove the existence of an infinite word w over a binary alphabet with the property that if x is a factor (contiguous subword) and the length of x is at least 5, then the reversal of x does not appear in w.  So for prefixes p of w, there are no palindromes at all in p of length $\geq 5$.  An example of such a word w is (001011) repeated forever.
More recently the topic was taken up again by Fici and Zamboni (see http://arxiv.org/abs/1301.3376 ). 
