\documentclass[11pt]{article} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{amsmath,amssymb,amsthm,mathrsfs} \usepackage[a4paper,hmargin=23mm,vmargin=25mm]{geometry} \usepackage{lmodern,microtype,xcolor} \usepackage{tikz,needspace} \usetikzlibrary{arrows.meta} \usepackage{hyperref} \hypersetup{pdftitle={Sharp fractional Helly bounds for common affine flats},pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník},colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue} \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{question}[theorem]{Question} \newtheorem{example}[theorem]{Example} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \DeclareMathOperator{\conv}{conv} \newcommand{\R}{\mathbb R} \newcommand{\Z}{\mathbb Z} \newcommand{\Kcal}{\mathcal K} \newcommand{\Ncal}{\mathcal N} \title{Sharp fractional Helly bounds for common affine flats\thanks{This work was produced within the Bolzano project (\url{https://bolzano.app}), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking.}} \author{Mat\v{e}j Kripner \qquad V\'{a}clav Rozho\v{n} \qquad Robert \v{S}\'{a}mal\\[0.4em] Martin \v{S}indel\'{a}\v{r} \qquad Adri\'{a}n Z\'{a}me\v{c}n\'{i}k} \date{} % Collection typography. \definecolor{BolzanoInk}{HTML}{24445C} \hypersetup{colorlinks=true,linkcolor=BolzanoInk,citecolor=BolzanoInk, urlcolor=BolzanoInk,pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník},pdflang={en-US}} \urlstyle{same} \setlength{\emergencystretch}{1em} \let\BolzanoBibliography\thebibliography \renewcommand{\thebibliography}[1]{\Needspace{38\baselineskip}\BolzanoBibliography{#1}\small\raggedright} \begin{document} \maketitle \begin{abstract} If an $\alpha$ fraction of the $(d-k+1)$-tuples of closed convex sets in $\R^d$ have an intersection containing a whole affine $k$-flat, then a fraction $1-(1-\alpha)^{1/(d-k+1)}$ of the sets share such a flat. This coefficient is best possible, resolving the sharp fractional De Santis question of Ludwigson and Sober\'on. The geometric result behind the bound is $(d-k)$-collapsibility of the common-flat complex, proved by coordinating convex sweeps in varying quotient spaces. \end{abstract} \section{Introduction} \subsection{Background and the source problem} Helly's theorem says that a finite family of convex sets in the plane has a common point whenever every three or fewer members do; in $\R^d$, the corresponding number is $d+1$~\cite{Helly}. The fractional question is what remains true if only a proportion $\alpha$ of those small subfamilies intersect. The fractional Helly theorem guarantees a point belonging to a positive fraction of all the sets~\cite{KL}. Its sharp form gives the fraction $1-(1-\alpha)^{1/(d+1)}$~\cite{Kalai,Eckhoff}. Thus local intersection data forces a large subfamily with a common point. As the proportion of intersecting tuples tends to one, the guaranteed fraction of sets sharing a point also tends to one. Here the object to be shared is a whole affine flat. An affine $k$-flat is a translate of a $k$-dimensional linear subspace: a point when $k=0$, a line when $k=1$, and a plane when $k=2$. We ask for such a flat to be \emph{contained in every set of a subfamily}. This is stronger than asking the intersection to have dimension at least $k$: a disk has dimension two but contains no whole line. It also differs from finding a flat that merely meets each set, the transversal problem discussed, for example, in~\cite[Section~6]{Soberon}. Parallel strips in the plane give the simplest picture. Their intersection contains a line exactly when their projected intervals on the common normal line intersect. This reduces the question to one dimension. Two strips with different directions, however, can have a two-dimensional bounded intersection and still share no line; see Figure~\ref{fig:strips}. In a general family the directions may vary, so there need not be a single projection that works for all subfamilies. \begin{figure}[ht] \centering \begin{tikzpicture}[x=1cm,y=1cm,>=Latex,font=\small] \begin{scope} \fill[blue!12] (-2.3,-.55) rectangle (2.3,.45); \fill[orange!18] (-2.3,-.05) rectangle (2.3,.95); \draw[blue!65!black] (-2.3,-.55)--(2.3,-.55) (-2.3,.45)--(2.3,.45); \draw[orange!80!black] (-2.3,-.05)--(2.3,-.05) (-2.3,.95)--(2.3,.95); \draw[<->,very thick,red!65!black] (-2.45,.2)--(2.45,.2); \node at (0,1.3) {Parallel strips}; \node at (0,-1.0) {A whole common line}; \end{scope} \begin{scope}[xshift=6.2cm] \fill[blue!12] (-2.3,-.55) rectangle (2.3,.45); \fill[orange!18] (-.5,-.85) rectangle (.5,1.05); \fill[red!18] (-.5,-.55) rectangle (.5,.45); \draw[blue!65!black] (-2.3,-.55)--(2.3,-.55) (-2.3,.45)--(2.3,.45); \draw[orange!80!black] (-.5,-.85)--(-.5,1.05) (.5,-.85)--(.5,1.05); \node at (0,1.3) {Different directions}; \node at (0,-1.2) {A bounded common rectangle}; \end{scope} \end{tikzpicture} \caption{Two strip configurations, shown inside a drawing window. A two-dimensional intersection need not contain a line: the common translation directions determine whether it does.} \label{fig:strips} \end{figure} Nevertheless, the correct dimension is the codimension $q=d-k$. De Santis~\cite{DS}, restated in~\cite[Theorem~1]{LS}, proved that if every $q+1$ or fewer members of a finite family of \emph{closed} convex sets contain a common $k$-flat, then the entire family does. Ludwigson and Sober\'on~\cite[Theorem~5]{LS} established a fractional version: if an $\alpha$ fraction of the $(q+1)$-tuples have this property, at least an $\alpha/(q+1)$ fraction of the sets share a $k$-flat. Their Section~6 asks for the optimal coefficient. \begin{question}[{\cite[Section~6]{LS}}]\label{q:source} For closed convex sets in $\R^d$, does the fractional De Santis theorem hold with the sharp ordinary fractional Helly coefficient in dimension $q=d-k$, namely \begin{equation}\label{eq:beta} \beta=1-(1-\alpha)^{1/(q+1)}? \end{equation} \end{question} The difference is substantial when most tuples are good. For common lines in the plane, $q=1$: if $99\%$ of the pairs contain a common line, the proposed coefficient guarantees one line contained in at least $90\%$ of all sets. The earlier coefficient guarantees only $49.5\%$. More generally, the proposed bound tends to one as $\alpha\to1$, as the non-fractional De Santis theorem suggests. \subsection{Contribution} The sharp coefficient is valid. In fact, the intersection patterns have a stronger combinatorial property that explains the dimension reduction and gives an exact finite counting bound. \begin{enumerate} \item Theorem~\ref{thm:fractional-main} answers Question~\ref{q:source}. Theorem~\ref{thm:finite} gives its exact finite form, and Theorem~\ref{thm:construction} supplies matching examples with distinct closed convex sets. \item Theorem~\ref{thm:collapsible} proves that the complex of common-$k$-flat subfamilies is $q$-collapsible. This answers the closed-convex version of the second question in~\cite[Section~6]{LS}. \end{enumerate} \begin{theorem}[Sharp fractional Helly theorem for common flats] \label{thm:fractional-main} Let $0\le k0$. The counting step is established topology. A $q$-collapsible complex is $q$-Leray: every induced subcomplex has zero reduced homology in degrees at least $q$. Kalai's upper-bound theorem, in the integral formulation of Alon, Kalai, Matou\v sek and Meshulam~\cite[Section~6, Theorems~12 and~13]{AKMM}, then gives the exact finite inequality and the coefficient~\eqref{eq:beta}. Accordingly, the coefficient itself is classical; the contribution is to place the common-flat complex in the class to which that coefficient applies. The equality construction is the classical hyperplane pattern, realized here by distinct sets and lifted by taking products with $\R^k$. Kalai and Meshulam's topological colorful Helly theorem~\cite{KM05} and their work on Leray numbers under projections~\cite{KM08} provide related ways to derive Helly consequences from intersection topology. More recent optimal colorful fractional theorems for collapsible complexes~\cite[Theorems~1.4 and~1.5]{CCKK} and Leray complexes~\cite[Theorem~1.9]{McGinnis} also apply once the geometric property is established. Ludwigson and Sober\'on already give a selection-structure theorem for common flats~\cite[Theorem~6]{LS}, extending the framework of~\cite[Theorem~6]{Soberon}. Results prescribing only the dimension of an intersection, such as~\cite[Theorem~1.5]{Rao}, concern a different geometric condition, as the strip example shows. \section{Translation invariance}\label{sec:translation} For a nonempty closed convex set $C$, define its lineality space by \[ L(C)=\{v\in\R^d:x+tv\in C\text{ for all }x\in C,\ t\in\R\}. \] The space $L(C)$ is linear. Scalar closure follows from the definition, and if $v,w\in L(C)$ then translating first by $tv$ and then by $tw$ shows $v+w\in L(C)$. The translation statement in the next lemma is a special case of the cone-translation observation in~\cite[Lemma~4.1]{Barany}. \begin{lemma}\label{lem:lineality} If a nonempty closed convex set $C$ contains $a+\R v$, then $v\in L(C)$. Consequently, for nonempty closed convex sets $C_i$, $i\in I$, their intersection contains a $k$-flat if and only if \begin{equation}\label{eq:rank} \bigcap_{i\in I}C_i\ne\varnothing \quad\text{and}\quad \dim\left(\sum_{i\in I}L(C_i)^\perp\right)\le d-k. \end{equation} \end{lemma} \begin{proof} Fix $x\in C$ and $t\in\R$. For each positive integer $N$, convexity gives \[ \left(1-\frac1N\right)x+\frac1N(a+Ntv) =x+tv+\frac{a-x}{N}\in C. \] Closedness then gives $x+tv\in C$ on letting $N\to\infty$. This proves the first assertion. If a common flat is $x+V$, where $\dim V=k$, its lines show $V\subseteq L(C_i)$ for every $i$. Conversely, if $x$ lies in the intersection and $\bigcap_iL(C_i)$ has dimension at least $k$, any $k$-dimensional subspace $V$ of that intersection gives $x+V\subseteq C_i$ for all $i$. Finally, \[ \left(\sum_{i\in I}L(C_i)^\perp\right)^\perp=\bigcap_{i\in I}L(C_i), \] which proves~\eqref{eq:rank}. The empty family also satisfies the equivalence, with the empty sum interpreted as the zero subspace. \end{proof} For a concrete instance of \eqref{eq:rank}, take the three coordinate slabs $C_i=\{x\in\R^3:|x_i|\le1\}$, $i=1,2,3$, and ask for common lines. Here $L(C_i)^\perp$ is spanned by the $i$th coordinate vector. Every pair has a common line in the remaining coordinate direction, but the triple intersection is a bounded cube. All ordinary intersections are nonempty; it is the growth of the sum of normal spaces from dimension two to dimension three that destroys the common line. This is exactly the additional information that the common-flat complex must record. \begin{remark} Closedness in Lemma~\ref{lem:lineality} cannot simply be omitted. The convex set \[ C=\{(x,y)\in\R^2:y>0\}\cup\{(0,0)\} \] contains the horizontal line at height one, but horizontal translation does not preserve its boundary point $(0,0)$. Convexity follows because every nontrivial convex combination involving a point with positive second coordinate still has positive second coordinate. This example explains the use of the closedness assumption in~\cite[Theorem 5]{LS}. \end{remark} \section{Polyhedral cylinders and collapsibility}\label{sec:collapse} Fix integers $0\le k\le d$ and put $q=d-k$. Families are indexed by $[n]=\{1,\ldots,n\}$; repetitions and empty members are allowed. Their common-$k$-flat complex is \begin{equation}\label{def:complex} \Kcal=\left\{I\subseteq[n]:\bigcap_{i\in I}C_i \text{ contains an affine }k\text{-flat}\right\}. \end{equation} The empty intersection is $\R^d$, so the empty face belongs to $\Kcal$. A label whose set contains no $k$-flat is not a vertex. An elementary $q$-collapse removes an interval $[B,T]=\{I:B\subseteq I\subseteq T\}$, where $B$ is contained in the unique maximal face $T$ of the current complex and $|B|\le q$. A complex is $q$-collapsible if such removals reduce it to the void complex. The empty face is allowed as $B$; in particular, a simplex is $0$-collapsible. This is the convention in~\cite[Section 2]{Tancer}. For $k=0$ the theorem below is Wegner's convex-nerve theorem; the proof coordinates the usual polyhedral sweep across different normal spaces when $k>0$. \begin{lemma}[Reduction to bounded-base polyhedral cylinders] \label{lem:cylinder-reduction} The common-$k$-flat complex of a finite family of closed convex sets can also be realized by sets $D_i=P_i+L_i$, where $P_i$ is a compact polytope and $L_i$ is a linear subspace. Labels which are not vertices can be omitted. Furthermore, the $D_i$ can be chosen full-dimensional, with every nonempty intersection having interior, and with finite inequality descriptions \begin{equation}\label{eq:cylinder-inequalities} D_i=\{x:a_h\cdot x\le b_h\quad(h\in H_i)\} \end{equation} in which no linearly dependent collection of the labelled normals $a_h$ has a common point on all its bounding hyperplanes. The labels in different $H_i$ are distinct, even if the original sets were equal. The normals of $D_i$ span $L_i^\perp$. \end{lemma} \begin{proof} Discard labels which are not vertices of the common-flat complex. For each nonempty face $I$, choose a contained flat $x_I+V_I$ with $\dim V_I=k$. For each remaining label put \[ P_i^0=\operatorname{conv}\{x_I:i\in I\},\qquad L_i=\sum_{I\ni i}V_I,\qquad D_i^0=P_i^0+L_i. \] Lemma~\ref{lem:lineality} gives $L_i\subseteq L(C_i)$, so $D_i^0\subseteq C_i$. Every chosen witness flat is retained. Consequently these cylinders have exactly the original common-flat complex. The sum of a compact polytope and a subspace is closed: it is the inverse image of a compact polytope under projection onto $L_i^\perp$. Its lineality is exactly $L_i$. We justify small perturbations without an assumption of boundedness in the ambient space. Put $A_i=L_i^\perp$. For a subfamily $I$ write $W_I=\sum_{i\in I}A_i$. The linear map \[ W_I\longrightarrow\bigoplus_{i\in I}A_i, \qquad x\longmapsto(\pi_{A_i}x)_{i\in I} \] is injective: a vector in its kernel lies both in $W_I$ and in $\bigcap_{i\in I}L_i=W_I^\perp$. In finite dimensions its inverse on its image is bounded. Thus bounded projections onto all $A_i$ bound the norm of a vector in $W_I$. The ordinary nerve records subfamilies with nonempty intersection. Replace $D_i^0$ by $D_i^0+\varepsilon[-1,1]^d$. For all sufficiently small common $\varepsilon>0$, this preserves that nerve. Indeed, if an originally empty intersection became nonempty for $\varepsilon_j\downarrow0$, project witnesses onto $W_I$. Their projections onto each $A_i$ remain bounded, because $\pi_{A_i}D_i^0$ is compact. The preceding injectivity makes the witnesses bounded. A convergent subsequence would give a point of the originally empty intersection. There are only finitely many subfamilies. Existing intersections remain nonempty and now contain an open ball, since any old common point has an $\varepsilon$-ball in every thickened member. Lineality spaces stay equal to $L_i$. The lineality criterion therefore preserves the common-flat complex. Each thickened member has a full-dimensional compact polytope as its quotient by $L_i$, so it has a finite description \eqref{eq:cylinder-inequalities}, with nonzero normals in $A_i$. Those normals span $A_i$, and their common recession cone is $L_i$. There is an open neighborhood of the right-hand-side vector in which the entire ordinary nerve is constant. Feasible intersections retain a point satisfying all inequalities strictly. Infeasible intersections cannot become feasible along a sequence converging to the original right-hand side: the quotient of each member is uniformly bounded in such a sequence. To verify this last assertion, an unbounded sequence in $A_i$ with bounded right-hand sides would, after normalization and passage to a subsequence, give a nonzero recession vector in $A_i$, contradicting boundedness of the quotient. The injective projection map above then bounds joint witnesses in $W_I$, and a limit gives the claimed contradiction. Finally choose the right-hand sides generically inside this open neighborhood. For each linearly dependent collection $J$ of normals, choose a nonzero vector $(c_h)_{h\in J}$ with $\sum_{h\in J}c_ha_h=0$ and avoid the proper hyperplane $\sum_{h\in J}c_hb_h=0$ in parameter space. Finitely many proper hyperplanes cannot cover an open set. The resulting bounding hyperplanes of a dependent collection have no common point. Recession and lineality depend only on the normals, so they are unchanged. The nerve and common-flat complex are unchanged as well. \end{proof} \begin{theorem}[Collapsibility of the common-flat complex] \label{thm:collapsible} For $0\le k\le d$, the common-$k$-flat complex of a finite family of closed convex sets in $\mathbb R^d$ is $(d-k)$-collapsible. \end{theorem} \begin{proof} Use Lemma~\ref{lem:cylinder-reduction} and its labelled inequalities. For each nonempty feasible subfamily $I$, put \[ W_I=\sum_{i\in I}A_i,\qquad P_I=W_I\cap\bigcap_{i\in I}D_i. \] Then $P_I$ is a full-dimensional compact polytope in $W_I$. Boundedness follows from the injective projection argument in the lemma, and full dimension follows by projecting an interior point of the intersection onto $W_I$. Moreover $\bigcap_{i\in I}D_i=P_I+W_I^\perp$. The common-flat faces are precisely the feasible $I$ with $\dim W_I\le q=d-k$. Include $I=\varnothing$ with $W_I=0$ and $P_I=\{0\}$. At a vertex of $P_I$, the active labelled normals are linearly independent by general position. They span $W_I$, since otherwise a nonzero direction in $W_I$ perpendicular to all active normals could be followed a short distance in both directions while preserving every inequality, contrary to extremality. Thus exactly $r=\dim W_I$ labelled inequalities are active at each vertex. Choose a vector $u\in\mathbb R^d$ with two generic properties. First, for each fixed space $W$, require $u\cdot v\ne u\cdot w$ for any distinct vertices $v,w$ among all polytopes $P_I$ with $W_I=W$. Second, for every independent collection of active normals spanning a space $W$, $\pi_Wu$ does not belong to the span of any proper subcollection. Each forbidden condition is a proper linear subspace or hyperplane; there are finitely many, so such $u$ exists. Let $v_I$ be the unique vertex maximizing $u\cdot x$ on $P_I$. Fix a possible pair $(W,v)=(W_I,v_I)$, with $r=\dim W$. Let $J$ be the $r$ active inequalities of $I$ at $v$, and let $B$ be the set of their owner labels. Then $|B|\le r\le q$ and $\sum_{i\in B}A_i=W$. Write $\pi_Wu=\sum_{h\in J}\lambda_ha_h$. Every coefficient is positive. For if $w_h\in W$ is dual to the active normals, so that $a_j\cdot w_h=\mathbf1_{j=h}$, then $v-tw_h$ is feasible for small positive $t$. Optimality forces $\lambda_h\ge0$, and the second generic property rules out zero. No additional labelled inequality with its normal in $W$ can be active at $v$: together with $J$ it would be a dependent collection of hyperplanes through the same point. Define \[ T=\{i:A_i\subseteq W\text{ and }v\in D_i\}. \] The faces with pair $(W,v)$ are exactly the interval $[B,T]$. To prove one inclusion, if $B\subseteq S\subseteq T$, the active normals force $W_S=W$ and $v\in P_S$. For every $x\in P_S$, \[ u\cdot(x-v)=\sum_{h\in J}\lambda_h(a_h\cdot x-b_h)\le0. \] Equality forces all $r$ active equations, and hence $x=v$. Thus $v_S=v$. Conversely, a face $S$ with the same pair is contained in $T$. Its optimum must use all $r$ active inequalities in $J$: these are the only possible active inequalities with normals in $W$. If one were absent, the corresponding dual direction would give a feasible local increase of the objective, since the missing coefficient $\lambda_h$ is positive. Therefore $B\subseteq S$. The interval description also shows that $B,T$ do not depend on the initial choice of $I$ with this pair. Order these pairs first by decreasing $\dim W$, then by any fixed order among spaces of the same dimension, and finally, for a fixed $W$, by increasing $u\cdot v$. Remove their intervals in this order. At the moment $[B,T]$ is removed, any remaining face $S$ containing $B$ has $W\subseteq W_S$. A larger dimension has already been removed, so $W_S=W$. The intersection for $S$ is contained in that for $B$, giving $u\cdot v_S\le u\cdot v$. A strict inequality has also already been processed. Equality identifies the same vertex, by the first generic property; hence $S\subseteq T$. Thus $T$ is the unique maximal remaining face containing $B$. Each interval removal is an elementary $q$-collapse. The intervals partition all faces, so the procedure reaches the void complex. The last, zero-dimensional interval consists of the simplex on whole-space members and uses $B=\varnothing$. \end{proof} For a complex $X$ on a specified ground set, write $X[S]=\{I\in X:I\subseteq S\}$ for its induced subcomplex. It is $q$-Leray if $\widetilde H_j(X[S];\Z)=0$ for all $j\ge q$ and all $S$. Only nonnegative homological degrees enter this definition. The following standard implication is included with integral coefficients, as required by the formulation of the upper-bound theorem in~\cite[Section~6]{AKMM}. \begin{lemma}[The homological consequence]\label{lem:collapse-leray} A $q$-collapsible complex is $q$-Leray over $\mathbb Z$. \end{lemma} \begin{proof} Restrict a collapse $[B,T]$ to a ground-set subset $S$. If $B\nsubseteq S$, nothing is removed. Otherwise the restricted removal is $[B,T\cap S]$, again with a unique maximal face and $|B|\le q$. Thus every induced subcomplex is $q$-collapsible. For one collapse $X\to X'$, the relative augmented chain complex is generated by faces $B\cup J$, $J\subseteq T\setminus B$. If $T\setminus B\ne\varnothing$, this is a shifted augmented chain complex of a nonempty simplex and is acyclic; a contraction is obtained by adjoining a fixed vertex of $T\setminus B$ to faces not already containing it, with the simplicial boundary sign. If $T=B$, its only generator has degree $|B|-1