Oct 2026· International mathematics research notices· 0 citations· 26 references
Abstract
A $k$-configuration is a collection of $k$ distinct integers $x_{1},\ldots ,x_{k}$ together with their pairwise arithmetic means $\frac{x_{i}+x_{j}}{2}$ for $1 \leq i < j \leq k$. Building on recent work of Filmus, Hatami, Hosseini, and Kelman on binary systems of linear forms and of Kelley and Meka on Roth’s theorem on arithmetic progressions, we show that, for $N \geq \exp ((k\log (2/\alpha ))^{O(1)})$, any subset $A \subseteq [N]$ of density at least $\alpha $ contains a $k$-configuration. This improves on the previously best known bound $N \geq \exp ((2/\alpha )^{O(k^{2})})$, due to Shao. As a consequence, it follows that any finite non-empty set $A \subseteq \mathbb{Z}$ contains a subset $B \subseteq A$ of size at least $(\log |A|)^{1+\Omega (1)}$ such that $b_{1}+b_{2} \not \in A$ for any distinct $b_{1},b_{2} \in B$. This provides a new proof of a lower bound for the Erdős–Moser sum-free set problem of the same shape as the best known bound, established by Sanders.
For a fixed finite collection of graphs $\mathcal{F}$, the $\mathcal{F}$-Minor-Free Deletion problem asks, given a graph $G$ and an integer $k$, whether there is a set $S\subseteq V(G)$ with $|S|\leq k$ such that $G-S$ contains no graph of $\mathcal{F}$ as a minor. This generalizes Vertex Cover, Feedback Vertex Set, an...
Jongseo Lee, Roohani Sharma, Sebastian Wiederrecht· 0 citations
The Ramsey number $r_k(s,n)$ is the smallest integer $N$ such that every $N$-vertex $k$-graph contains either a copy of $K_s^{(k)}$ or an independent set of size $n$. Erd\H{o}s and Hajnal conjectured that for every fixed $s>k\ge 4$, one has $r_k(s,n)\ge \operatorname{twr}_{k-1}(\Omega(n))$. This conjecture was independ...
Long-Ma Du, Xin-Yu Hu, Rui-Long Liu et al.· 0 citations
For a fixed $k$-uniform hypergraph $F$, let $\mathrm{ex}_k(n,F)$ denote the maximum number of edges in an $F$-free $k$-uniform hypergraph on $n$ vertices. We prove that for every integer $k\ge2$ and every rational $r\in[0,1]$ there exists a $k$-uniform hypergraph $F_{k,r}$ such that \begin{equation*} \mathrm{ex}_k(n,F_...
For a family $\mathcal{F}$ of $k$-graphs, $ex_k(n,\mathcal{F})$ denotes the maximum number of edges in an $n$-vertex $\mathcal{F}$-free $k$-graph. Let $M_{s+1}^k$ denote a matching of size $s+1$ in $k$-uniform hypergraphs. Recently, Alon and Frankl (JCTB, 2024) determined $ex_2(n,\{M_{s+1}^2,K_{\ell+1}\})$ for all $n\g...
For an integer $k\ge 2$ and $r^2>2(2k-1)\ln (2k-1)$, we construct a bipartite graph $G$ whose two vertex classes are disjoint copies of the family of all $k$-subsets of a $(2k-1)$-element set, two vertices being adjacent when their sets intersect in at most $r$ elements. Assigning each vertex its corresponding subset a...
For an integer $k\ge 3$, let $w(3,k)$ be the least $n$ such that every red-blue coloring of $[n]$ contains either a nontrivial three-term arithmetic progression in blue or a nontrivial $k$-term arithmetic progression in red. A recent breakthrough of Green proved that $w(3,k)\ge k^{\Omega\left(\left(\frac{\log k}{\log\l...
Hai-Tao Cao· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.