Source author record

Andreas F. Holmsen

Andreas F. Holmsen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.MG math.CO

Catalog footprint

What is connected

7works

2topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Leray numbers of complexes of graphs with bounded matching number

Given a graph $G$ on the vertex set $V$, the non-matching complex of $G$, $\mathsf{NM}_k(G)$, is the family of subgraphs $G' \subset G$ whose matching number $ν(G')$ is strictly less than $k$. As an attempt to generalize the result by Linusson, Shareshian and Welker on the homotopy types of $\mathsf{NM}_k(K_n)$ and $\mathsf{NM}_k(K_{r,s})$ to arbitrary graphs $G$, we show that (i) $\mathsf{NM}_k(G)$ is $(3k-3)$-Leray, and (ii) if $G$ is bipartite, then $\mathsf{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 $\mathsf{NM}_k(G)$, which vanishes in all dimensions $d\geq 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, Berger, Chudnovsky, Howard and Seymour: Let $E_1, \dots, E_{3k-2}$ be non-empty edge subsets of a graph and suppose that $ν(E_i\cup E_j)\geq k$ for every $i\ne 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.

preprint2020arXiv

Two extensions of the Erdős-Szekeres problem

According to Suk's breakthrough result on the Erdos-Szekeres problem, any point set in general position in the plane, which has no $n$ elements that form the vertex set of a convex $n$-gon, has at most $2^{n+O\left({n^{2/3}\log n}\right)}$ points. We strengthen this theorem in two ways. First, we show that the result generalizes to convexity structures induced by pseudoline arrangements. Second, we improve the error term. A family of $n$ convex bodies in the plane is said to be in convex position if the convex hull of the union of no $n-1$ of its members contains the remaining one. If any three members are in convex position, we say that the family is in general position. Combining our results with a theorem of Dobbins, Holmsen, and Hubard, we significantly improve the best known upper bounds on the following two functions, introduced by Bisztriczky and Fejes Toth and by Pach and Toth, respectively. Let $c(n)$ (and $c'(n)$) denote the smallest positive integer $N$ with the property that any family of $N$ pairwise disjoint convex bodies in general position (resp., $N$ convex bodies in general position, any pair of which share at most two boundary points) has an $n$-membered subfamily in convex position. We show that $c(n)\le c'(n)\leq 2^{n+O\left(\sqrt{n\log n}\right)}$.

preprint2016arXiv

Cutting convex curves

We show that for any two convex curves $C_1$ and $C_2$ in $\mathbb R^d$ parametrized by $[0,1]$ with opposite orientations, there exists a hyperplane $H$ with the following property: For any $t\in [0,1]$ the points $C_1(t)$ and $C_2(t)$ are never in the same open halfspace bounded by $H$. This will be deduced from a more general result on equipartitions of ordered point sets by hyperplanes.

preprint2015arXiv

Orthogonal colorings of the sphere

An orthogonal coloring of the two-dimensional unit sphere $\mathbb{S}^2$, is a partition of $\mathbb{S}^2$ into parts such that no part contains a pair of orthogonal points, that is, a pair of points at spherical distance $π/2$ apart. It is a well-known result that an orthogonal coloring of $\mathbb{S}^2$ requires at least four parts, and orthogonal colorings with exactly four parts can easily be constructed from a regular octahedron centered at the origin. An intriguing question is whether or not every orthogonal 4-coloring of $\mathbb{S}^2$ is such an octahedral coloring. In this paper we address this question and show that if every color class has a non-empty interior, then the coloring is octahedral. Some related results are also given.

preprint2015arXiv

Topology of geometric joins

We consider the geometric join of a family of subsets of the Euclidean space. This is a construction frequently used in the (colorful) Carathéodory and Tverberg theorems, and their relatives. We conjecture that when the family has at least $d+1$ sets, where $d$ is the dimension of the space, then the geometric join is contractible. We are able to prove this when $d$ equals $2$ and $3$, while for larger $d$ we show that the geometric join is contractible provided the number of sets is quadratic in $d$. We also consider a matroid generalization of geometric joins and provide similar bounds in this case.

preprint2014arXiv

Regular systems of paths and families of convex sets in convex position

In this paper we show that every sufficiently large family of convex bodies in the plane has a large subfamily in convex position provided that the number of common tangents of each pair of bodies is bounded and every subfamily of size five is in convex position. (If each pair of bodies have at most two common tangents it is enough to assume that every triple is in convex position, and likewise, if each pair of bodies have at most four common tangents it is enough to assume that every quadruple is in convex position.) This confirms a conjecture of Pach and Toth, and generalizes a theorem of Bisztriczky and Fejes Toth. Our results on families of convex bodies are consequences of more general Ramsey-type results about the crossing patterns of systems of graphs of continuous functions $f:[0,1] \to \mathbb{R}$. On our way towards proving the Pach-Toth conjecture we obtain a combinatorial characterization of such systems of graphs in which all subsystems of equal size induce equivalent crossing patterns. These highly organized structures are what we call regular systems of paths and they are natural generalizations of the notions of cups and caps from the famous theorem of Erdos and Szekeres. The characterization of regular systems is combinatorial and introduces some auxiliary structures which may be of independent interest.

preprint2013arXiv

The Colored Hadwiger Transversal Theorem in $\mathbb R^d$

Hadwiger's transversal theorem gives necessary and sufficient conditions for a family of convex sets in the plane to have a line transversal. A higher dimensional version was obtained by Goodman, Pollack and Wenger, and recently a colorful version appeared due to Arocha, Bracho and Montejano. We show that it is possible to combine both results to obtain a colored version of Hadwiger's theorem in higher dimensions. The proofs differ from the previous ones and use a variant of the Borsuk-Ulam theorem. To be precise, we prove the following. Let $F$ be a family of convex sets in $\mathbb R^d$ in bijection with a family $P$ of points in $\mathbb R^{d-1}$. Assume that there is a coloring of $F$ with sufficiently many colors such that any colorful Radon partition of points in $P$ corresponds to a colorful Radon partition of sets in $F$. Then some monochromatic subfamily of $F$ has a hyperplane transversal.