Description
We are interested in the following Turan-type problems: determine the maximum number of edges of an vertex-ordered graph on n vertices which does not contain a copy of a certain ordered matching. Forbidding a crossing, nested or separated matching is very natural and these cases have been resolved. The case where the forbidden matching is non-crossing is also understood.
In this talk, we present a full resolution of the non-separated case and prove (close) bounds for the non-nested case. We conjecture an exact answer for the non-nested case which would yield better bounds for a related Ramsey-type question. We also discuss some related results for alternating paths.
This is joint work with Janos Barat and Geza Toth.