Given a family of sets on the plane, we say that the family is intersecting if for any two sets from the family their interiors intersect. In this paper, we study intersecting families of triangles with vertices in a given set of points. In particula
r, we show that if a set $P$ of $n$ points is in convex position, then the largest intersecting family of triangles with vertices in $P$ contains at most $(frac{1}{4}+o(1))binom{n}{3}$ triangles.
Given a graph $G$ on the vertex set $V$, the {em non-matching complex} of $G$, $NM_k(G)$, is the family of subgraphs $G subset G$ whose matching number $ u(G)$ is strictly less than $k$. As an attempt to generalize the result by Linusson, Shareshian
and Welker on the homotopy types of $NM_k(K_n)$ and $NM_k(K_{r,s})$ to arbitrary graphs $G$, we show that (i) $NM_k(G)$ is $(3k-3)$-Leray, and (ii) if $G$ is bipartite, then $NM_k(G)$ is $(2k-2)$-Leray. This result is obtained by analyzing the homology of the links of non-empty faces of the complex $NM_k(G)$, which vanishes in all dimensions $dgeq 3k-4$, and all dimensions $d geq 2k-3$ when $G$ is bipartite. As a corollary, we have the following rainbow matching theorem which generalizes the result by Aharoni et. al. and Driskos theorem: Let $E_1, dots, E_{3k-2}$ be non-empty edge subsets of a graph and suppose that $ u(E_icup E_j)geq k$ for every $i e j$. Then $E=bigcup E_i$ has a rainbow matching of size $k$. Furthermore, the number of edge sets $E_i$ can be reduced to $2k-1$ when $E$ is the edge set of a bipartite graph.
In a nutshell, we show that polynomials and nested polytopes are topological, algebraic and algorithmically equivalent. Given two polytops $Asubseteq B$ and a number $k$, the Nested Polytope Problem (NPP) asks, if there exists a polytope $X$ on $k$ v
ertices such that $Asubseteq X subseteq B$. The polytope $A$ is given by a set of vertices and the polytope $B$ is given by the defining hyperplanes. We show a universality theorem for NPP. Given an instance $I$ of the NPP, we define the solutions set of $I$ as $$ V(I) = {(x_1,ldots,x_k)in mathbb{R}^{kcdot n} : Asubseteq text{conv}(x_1,ldots,x_k) subseteq B}.$$ As there are many symmetries, induced by permutations of the vertices, we will consider the emph{normalized} solution space $V(I)$. Let $F$ be a finite set of polynomials, with bounded solution space. Then there is an instance $I$ of the NPP, which has a rationally-equivalent normalized solution space $V(I)$. Two sets $V$ and $W$ are rationally equivalent if there exists a homeomorphism $f : V rightarrow W$ such that both $f$ and $f^{-1}$ are given by rational functions. A function $f:Vrightarrow W$ is a homeomorphism, if it is continuous, invertible and its inverse is continuous as well. As a corollary, we show that NPP is $exists mathbb{R}$-complete. This implies that unless $exists mathbb{R} =$ NP, the NPP is not contained in the complexity class NP. Note that those results already follow from a recent paper by Shitov. Our proof is geometric and arguably easier.
We study the problem of deciding if a given triple of permutations can be realized as geometric permutations of disjoint convex sets in $mathbb{R}^3$. We show that this question, which is equivalent to deciding the emptiness of certain semi-algebraic
sets bounded by cubic polynomials, can be lifted to a purely combinatorial problem. We propose an effective algorithm for that problem, and use it to gain new insights into the structure of geometric permutations.
In the Art Gallery Problem we are given a polygon $Psubset [0,L]^2$ on $n$ vertices and a number $k$. We want to find a guard set $G$ of size $k$, such that each point in $P$ is seen by a guard in $G$. Formally, a guard $g$ sees a point $p in P$ if t
he line segment $pg$ is fully contained inside the polygon $P$. The history and practical findings indicate that irrational coordinates are a very rare phenomenon. We give a theoretical explanation. Next to worst case analysis, Smoothed Analysis gained popularity to explain the practical performance of algorithms, even if they perform badly in the worst case. The idea is to study the expected performance on small perturbations of the worst input. The performance is measured in terms of the magnitude $delta$ of the perturbation and the input size. We consider four different models of perturbation. We show that the expected number of bits to describe optimal guard positions per guard is logarithmic in the input and the magnitude of the perturbation. This shows from a theoretical perspective that rational guards with small bit-complexity are typical. Note that describing the guard position is the bottleneck to show NP-membership. The significance of our results is that algebraic methods are not needed to solve the Art Gallery Problem in typical instances. This is the first time an $existsmathbb{R}$-complete problem was analyzed by Smoothed Analysis.
We introduce a geometric generalization of Halls marriage theorem. For any family $F = {X_1, dots, X_m}$ of finite sets in $mathbb{R}^d$, we give conditions under which it is possible to choose a point $x_iin X_i$ for every $1leq i leq m$ in such a w
ay that the points ${x_1,...,x_m}subset mathbb{R}^d$ are in general position. We give two proofs, one elementary proof requiring slightly stronger conditions, and one proof using topological techniques in the spirit of Aharoni and Haxells celebrated generalization of Halls theorem.
We introduce combinatorial types of arrangements of convex bodies, extending order types of point sets to arrangements of convex bodies, and study their realization spaces. Our main results witness a trade-off between the combinatorial complexity of
the bodies and the topological complexity of their realization space. First, we show that every combinatorial type is realizable and its realization space is contractible under mild assumptions. Second, we prove a universality theorem that says the restriction of the realization space to arrangements polygons with a bounded number of vertices can have the homotopy type of any primary semialgebraic set.
We give the following extension of Baranys colorful Caratheodory theorem: Let M be an oriented matroid and N a matroid with rank function r, both defined on the same ground set V and satisfying rank(M) < rank(N). If every subset A of V with r(V - A)
< rank (M) contains a positive circuit of M, then some independent set of N contains a positive circuit of M.
In 1940, Luis Santalo proved a Helly-type theorem for line transversals to boxes in R^d. An analysis of his proof reveals a convexity structure for ascending lines in R^d that is isomorphic to the ordinary notion of convexity in a convex subset of R^
{2d-2}. This isomorphism is through a Cremona transformation on the Grassmannian of lines in P^d, which enables a precise description of the convex hull and affine span of up to d ascending lines: the lines in such an affine span turn out to be the rulings of certain classical determinantal varieties. Finally, we relate Cremona convexity to a new convexity structure that we call frame convexity, which extends to arbitrary-dimensional flats.
