##
**Codimension two and three Kneser transversals.**
*(English)*
Zbl 1392.52003

Summary: Let \(k,d,\lambda \geqslant 1\) be integers with \(d\geqslant \lambda \) and let \(X\) be a finite set of points in \(\mathbb{R}^{d}\). A \((d-\lambda)\)-plane \(L\) transversal to the convex hulls of all \(k\)-sets of \(X\) is called a Kneser transversal. If in addition \(L\) contains \((d-\lambda)+1\) points of \(X\), then \(L\) is called a complete Kneser transversal.

In this paper, we present various results on the existence of (complete) Kneser transversals for \(\lambda =2,3\). In order to do this, we introduce the notions of stability and instability for (complete) Kneser transversals. We first give a stability result for collections of \(d+2(k-\lambda)\) points in \(\mathbb{R}^d\) with \(k-\lambda\geqslant 2\) and \(\lambda =2,3\). We then present a description of Kneser transversals \(L\) of collections of \(d+2(k-\lambda)\) points in \(\mathbb{R}^d\) with \(k-\lambda\geqslant 2\) for \(\lambda =2,3\). We show that either \(L\) is a complete Kneser transversal or it contains \(d-2(\lambda-1)\) points and the remaining \(2(k-1)\) points of \(X\) are matched in \(k-1\) pairs in such a way that \(L\) intersects the corresponding closed segments determined by them. The latter leads to new upper and lower bounds (in the case when \(\lambda =2\) and \(3\)) for \(m(k,d,\lambda)\) defined as the maximum positive integer \(n\) such that every set of \(n\) points (not necessarily in general position) in \(\mathbb{R}^{d}\) admit a Kneser transversal. Finally, by using oriented matroid machinery, we present some computational results (closely related to the stability and unstability notions). We determine the existence of (complete) Kneser transversals for each of the \(246\) different order types of configurations of \(7\) points in \(\mathbb{R}^3\).

In this paper, we present various results on the existence of (complete) Kneser transversals for \(\lambda =2,3\). In order to do this, we introduce the notions of stability and instability for (complete) Kneser transversals. We first give a stability result for collections of \(d+2(k-\lambda)\) points in \(\mathbb{R}^d\) with \(k-\lambda\geqslant 2\) and \(\lambda =2,3\). We then present a description of Kneser transversals \(L\) of collections of \(d+2(k-\lambda)\) points in \(\mathbb{R}^d\) with \(k-\lambda\geqslant 2\) for \(\lambda =2,3\). We show that either \(L\) is a complete Kneser transversal or it contains \(d-2(\lambda-1)\) points and the remaining \(2(k-1)\) points of \(X\) are matched in \(k-1\) pairs in such a way that \(L\) intersects the corresponding closed segments determined by them. The latter leads to new upper and lower bounds (in the case when \(\lambda =2\) and \(3\)) for \(m(k,d,\lambda)\) defined as the maximum positive integer \(n\) such that every set of \(n\) points (not necessarily in general position) in \(\mathbb{R}^{d}\) admit a Kneser transversal. Finally, by using oriented matroid machinery, we present some computational results (closely related to the stability and unstability notions). We determine the existence of (complete) Kneser transversals for each of the \(246\) different order types of configurations of \(7\) points in \(\mathbb{R}^3\).

### MSC:

52A35 | Helly-type theorems and geometric transversal theory |

52C40 | Oriented matroids in discrete geometry |

52B55 | Computational aspects related to convexity |

68-04 | Software, source code, etc. for problems pertaining to computer science |

PDF
BibTeX
XML
Cite

\textit{J. Chappelon} et al., SIAM J. Discrete Math. 32, No. 2, 1351--1363 (2018; Zbl 1392.52003)

### References:

[1] | J.L. Arocha, J. Bracho, L. Montejano, and J.L. Ramírez Alfonsín, Transversals to the convex hulls of all \(k\)-sets of discrete subsets of \(\mathbb{R}^{n}\), J. Combin. Theory Ser. A, 118 (2010), pp. 197–207. · Zbl 1231.05046 |

[2] | A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G. Ziegler, Oriented Matroids, 2nd ed., Encyclopedia Math. Appl., 46, Cambridge University Press, Cambridge, 1999. |

[3] | B. Bukh, J. Matou\vsek, and G. Nivasch, Stabbing simplices by points and flats, Discrete Comput. Geom., 43 (2010), pp. 321–338. · Zbl 1186.52001 |

[4] | B. Bukh and G. Nivasch, Upper bounds for centerlines, J. Comput. Geom., 3 (2012), pp. 20–30. · Zbl 1408.52039 |

[5] | J. Chappelon, L. Martínez-Sandoval, L. Montejano, L.P. Montejano, and J.L. Ramírez Alfonsín, Complete Kneser transversals, Adv. Appl. Math., 82 (2017), pp. 83–101. · Zbl 1352.52017 |

[6] | V.L. Dol’nikov, On transversals of families of convex sets, in Research in Theory of Functions of Several Real Variables, Yaroslavl State University, Yaroslavl, Russia, 1981, pp. 30–36 (in Russian). |

[7] | L. Finschi, Catalog of Oriented Matroids, · Zbl 1005.52013 |

[8] | L. Lovász, Kneser conjecture, chromatic number and homotopy, J. Combin. Theory Ser. A, 25 (1978), pp. 319–324. |

[9] | A. Magazinov and A. Pór, An Improvement on the Trivial Lower Bound for the Depth of a Centerline, arXiv:1603.01641v1, 2016. |

[10] | R. Rado, A theorem on general measure, J. Lond. Math. Soc., 22 (1947), pp. 291–300. · Zbl 0061.09606 |

[11] | M. Tancer, private communication, 2014–2015. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.