In this paper, we consider saturation problems related to the celebrated Erdős--Szekeres convex polygon problem. For each $n \ge 7$, we construct a planar point set of size $(7/8) \cdot 2^{n-2}$ which is saturated for convex $n$-gons. That is, the set contains no $n$ points in convex position while the addition of any new point creates such a configuration. This demonstrates that the saturation number is smaller than the Ramsey number for the Erdős--Szekeres problem. The proof also shows that the original Erdős--Szekeres construction is indeed saturated. Our construction is based on a similar improvement for the saturation version of the cups-versus-caps theorem. Moreover, we consider the generalization of the cups-versus-caps theorem to monotone paths in ordered hypergraphs. In contrast to the geometric setting, we show that this abstract saturation number is always equal to the corresponding Ramsey number.

Abstract. We prove that every family of (not necessarily distinct) even cycles [Formula: see text] on some fixed [Formula: see text]-vertex set has a rainbow even cycle (that is, a set of edges from distinct [Formula: see text]’s, forming an even cycle). This resolves an open problem of Aharoni, Briggs, Holzman and Jiang. Moreover, the result is best possible for every positive integer [Formula: see text].

Let $G$ be a graph on $n$ vertices of independence number $\alpha(G)$ such that every induced subgraph of $G$ on $n-k$ vertices has an independent set of size at least $\alpha(G) - \ell$. What is the largest possible $\alpha(G)$ in terms of $n$ for fixed $k$ and $\ell$? We show that $\alpha(G) \le n/2 + C_{k, \ell}$, which is sharp for $k-\ell \le 2$. We also use this result to determine new values of the Erdös--Rogers function.

Long-range and short-range temporal modeling are two complementary and crucial aspects of video recognition. Most of the state-of-the-arts focus on short-range spatio-temporal modeling and then average multiple snippet-level predictions to yield the final video-level prediction. Thus, their video-level prediction does not consider spatio-temporal features of how video evolves along the temporal dimension. In this paper, we introduce a novel Dynamic Segment Aggregation (DSA) module to capture relationship among snippets. To be more specific, we attempt to generate a dynamic kernel for a convolutional operation to aggregate long-range temporal information among adjacent snippets adaptively. The DSA module is an efficient plug-and-play module and can be combined with the off-the-shelf clip-based models (i.e., TSM, I3D) to perform powerful long-range modeling with minimal overhead. The final video architecture, coined as DSANet. We conduct extensive experiments on several video recognition benchmarks (i.e., Mini-Kinetics-200, Kinetics-400, Something-Something V1 and ActivityNet) to show its superiority. Our proposed DSA module is shown to benefit various video recognition models significantly. For example, equipped with DSA modules, the top-1 accuracy of I3D ResNet-50 is improved from 74.9% to 78.2% on Kinetics-400. Codes are available at https://github.com/whwu95/DSANet.