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

Chappelon, J.; Martínez-Sandoval, L.; Montejano, L.; Montejano, L. P.; Ramírez Alfonsín, J. L.

SIAM J. Discrete Math. 32, No. 2, 1351-1363 (2018).

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\).

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

Keywords:

oriented matroids; cyclic polytope; Kneser transversal; stability; instability

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. · Zbl 0944.52006
[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. · Zbl 0418.05028
[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.