Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs (Q795067): Difference between revisions

Suppose we label the edges of the complete graph on n vertices with distinct integer labels. How long a simple increasing path must exist in the resulting graph if the labeling is done diabolically to keep such paths down? In this paper it is shown that the longest path can be forced to have only a few more than half the vertices for large n, this improves the previous bound of 7n/12. The best lower bound on how long a path can be found is much lower. It is also shown that between 23/48ths and a little more than half the vertices of the n cube, each represented as a binary sequence of length n, can be ordered in increasing order, considering the sequences as numbers, so that any consecute sequence in the ordering has some component that sums to an odd number. This latter result is obtained by recursion relating the maximum length with the same where the last condition is applied only to even length sequences. It is used to derive the first result mentioned here.