Open problem session of HUJI-COMBSEM: Problem #1, Nati Linial – Turan type theorems for simplicial complexes.

On November, 2020  we had a very nice open problem session in our weekly combinatorics seminar at HUJI.  So I thought to have a series of posts to describe you the problems presented there.  This is the first post in the series. Later I will add a link to the zoom recording of the session, and to a writeup of all the problems.

While talking on open problems let me mention that in connection with the OPAC 2020 conference (now delayed to May 2021),  a community blog to discuss open problems in algebraic combinatorics was created. Everybody is invited to check out the problems posted there, to subscribe, and to contribute their own problems. And, of course, to solve the problems! The list of problems so far is impressive.

Nati’s problem

Problem 1: Given a 2-manifold $M$ what is the the number of 2-faces for a 2-dimensional simplicial complex S on n vertices that guarantee that S contains a triangulation of M?

The case that $M$ is a triangulation of a two dimensional sphere goes back to a theorem of Brown, Erdos and Sos. They proved that the answer is $Cn^{5/2}$. Nati proved that the lower bound applies for every 2-manifold $M$.

Problem 2: Given a k-complex S, how many facets can a  k-complex on n vertices have if it contains no topological copy of S? (Topological copy = homeomorphic image)

Nati mentioned some further background and recent progress regarding these problems and I will mention them in a separate post.

“High dimensional combinatorics”

Problems 1 and 2 are parts of “Linial’s programme” of studying systematically “high dimensional combinatorics”.  Here are links to a few papers, slides of talks and videotaped talks. Among the highlights of this theory are the study, starting with a paper by Linial and Roy Meshulam of the Erdos-Renyi model for simplicial complexes (which is closely related to high dimensional expanders), the study of high dimensional permutations, and high dimensional tournaments.

Challenges of high-dimensional combinatorics (slides), Laszlo Lovasz 70th birthday conference, Budapest July 2018. video (covering 2/3 of the slides)

What is high-dimensional combinatorics?, Random-Approx, August ’08.

On high-dimensional acyclic tournaments, Nati Linial and Avraham Morgenstern, Discrete and Computational Geometry: Volume 50, Issue 4 (2013), Page 1085-1100.

Homological connectivity of random 2-dimensional complexes, N. Linial, and R. Meshulam, Combinatorica, 26(2006) 475–487.

Random Simplicial complexes – Around the phase transition, Nati Linial and Yuval Peled, A Journey Through Discrete Mathematics, A tribute to Jiri Matousek, 543–570 (2017).

( See Nati’s homepage for more)

This entry was posted in Combinatorics, Geometry, Open problems and tagged . Bookmark the permalink.