AndreasHolmsen

Archive of posts with tag 'AndreasHolmsen'

  • Andreas Holmsen, Large cliques in hypergraphs with forbidden substructures

    IBS/KAIST Joint Discrete Math Seminar

    Large cliques in hypergraphs with forbidden substructures
    Andreas Holmsen
    Department of Mathematical Sciences, KAIST
    2019/03/12 Tue 4:30PM-5:30PM (Room B232, IBS)
    A result due to Gyárfás, Hubenko, and Solymosi, answering a question of Erdős, asserts that if a graph G does not contain K2,2 as an induced subgraph yet has at least c n(n-1)/2 edges, then G has a complete subgraph on at least c^2 n /10 vertices. In this paper we suggest a “higher-dimensional” analogue of the notion of an induced K2,2, which allows us to extend their result to k-uniform hypergraphs. Our result also has interesting consequences in topological combinatorics and abstract convexity, where it can be used to answer questions by Bukh, Kalai, and several others.
    Tags:

  • Andreas Holmsen, Nerves, minors, and piercing numbers
    Nerves, minors, and piercing numbers
    Andreas Holmsen
    Department of Mathematical Sciences, KAIST
    2017/5/08 Mon 4PM-5PM
    We will give a topological generalization of the planar (p,q) theorem due to Alon and Kleitman. In particular we will show that the assertion of the (p,q) theorem holds for families of open connected sets in the plane under the hypothesis that the intersection of any subfamily is empty or connected. The proof is based on a surprising connection between nerve complexes and complete minors in graphs. This is join work with Minki Kim and Seunghun Lee.
    Tags:

  • On the Erdős-Szekeres convex polygon problem
    On the Erdős-Szekeres convex polygon problem
    Andreas Holmsen
    Department of Mathematical Sciences, KAIST
    2016/05/27 4PM (Room 2411 of Bldg E6-1)
    Very recently, Andrew Suk made a major breakthrough on the Erdos-Szekeres convex polygon problem, in which he solves asymptotically this 80 year old problem of determining the minimum number of points in the plane in general position that always guarantees n points in convex position. I will review his proof in full detail.
    Tags:

  • Andreas Holmsen, Topological methods in matching theory
    Topological methods in matching theory
    Andreas Holmsen
    Department of Mathematical Sciences, KAIST
    2015/4/7 Tue 4PM-5PM
    Around 15 years ago, Aharoni and Haxell gave a wonderful generalization of Hall’s marriage theorem. Their proof introduced topological methods in matching theory which were further developed by Berger, Meshulam, and others. Recently, motivated by some geometric questions, we extended these methods further, and in this talk I’ll explain the ideas and some of our results.
    Tags:

  • Andreas Holmsen, On the Erdős-Szekeres Problem
    On the Erdős-Szekeres Problem
    Andreas Holmsen
    Department of Mathematical Sciences, KAIST
    2012/9/21 Fri 4PM-5PM
    In 1935 Erdős and Szekeres showed that every “sufficiently large” set of points in general position in the plane contains a “large” subset which is in convex position. Since then many mathematicians have tried to determine good bounds for “sufficiently large” in  terms of “large”, as well as given numerous generalizations and refinements. In this talk I will survey this famous problem and extend it to a natural object which we call generalized wiring diagram. This unifies several proposed generalizations, and as a result we will settle several conjectures in this area. This is joint work with Michael Dobbins and Alfredo Hubard.
    Tags:

  • Andreas Holmsen, Convex representations of Oriented Matroids
    Convex representations of Oriented Matroids
    Andreas Holmsen
    Department of Mathematical Sciences, KAIST
    2011/09/16 Fri 4PM-5PM
    Many combinatorial problems and arguments concerning finite point sets in the Euclidean plane (or higher dimensions) often do not use the linear structure. A more general concept is that of an Oriented Matroid (OM). It is well-known that every OM can realized by pseudolines, and in fact most oriented matroids can not be realized by straight lines.
    Recently, Alfreod Hubard (Courant Institute) and myself have found a new way to represent an OM by convex sets which retains much more of the “straightness” of the Euclidean plane. Interestingly, in our model the isotopy conjecture holds in a very strong sense, and it unifies several aspects of pseudoline arrangements.
    Tags:

  • Andreas Holmsen, Points surrounding the origin
    Points surrounding the origin
    Andreas Holmsen
    Div. of Computer Science, KAIST, Daejeon, Korea.
    2008/10/09 Thu, 3PM-4PM

    Many problems in discrete and computational geometry can be reduced to combinatorial questions concerning systems of segments or triangles in the plane. In spite of what (little) we can say about these planar questions, much less is known in higher dimensions. In this talk we will survey some of these questions and classical results, and present the following theorem: Let d>2 and n>d+1 and P a set of n points in d-dimensional Euclidean space. Then P contains a subset Q of d points such that for any point p in P, the simplex spanned by Q and p does not contain the origin in its interior. This answers a question by R.Strausz, and along the way we strengthen the Colored Helly and Caratheodory theorems, due to L. Lovász and I. Bárány, respectively.

    Joint work with János Pach and Helge Tverberg.

    Tags:

Monthly Archives