Description
In 2006, we proved with Adam Marcus the following fact: If we have $n$ subsets of an underlying $n$-element set, each with a fixed cyclic order such that for each pair of the subsets the common elements come
in reverse cyclic order, then the sum of the sizes of the subsets is $O(n^{3/2}\log n)$. Note that this is tight up to the logarithmic term, as there are $n$ subsets of size $\Theta(\sqrt n)$ with each pair intersecting in at most one element, making the intersection reverse property hold irrespective of the cyclic orders we choose.
Last year, we improved on this result with Barnabas Janzer, Oliver Janzer, and Abhishek Methuku. The improvement is twofold: we get rid of the logarithmic term (making the result tight up to a constant factor) and we also make the intersection-reverse property weaker: we assume that the subsets are linearly ordered and we only assume that no three elements appear in two subsets in the same order.
The talk will include some applications too: the applications of the old result got stronger by losing the log factor, and the weaker assumption allows for some new applications too.