Recent progress on high dimensional Turan-Type problems by Andrey Kupavskii, Alexandr Polyanskii, István Tomon, and Dmitriy Zakharov and by Jason Long, Bhargav Narayanan, and Corrine Yap.

The extremal number for surfaces

Andrey Kupavskii, Alexandr Polyanskii, István Tomon, Dmitriy Zakharov: The extremal number of surfaces

Abstract: In 1973, Brown, Erdős and Sós proved that if \cal H is a 3-uniform hypergraph on n vertices which contains no triangulation of the sphere, then \cal H  has at most O(n^{5/2}) edges, and this bound is the best possible up to a constant factor. Resolving a conjecture of Linial, also reiterated by Keevash, Long, Narayanan, and Scott, we show that the same result holds for triangulations of the torus. Furthermore, we extend our result to every closed orientable surface \cal S.

Remarks:

1) When \cal S is fixed Nati proved that there is a simplicial complex with n vertices and c n^{5/2} 2-faces that does not contain a triangulation of \cal S.

2) It is not known if there is an example with n vertices and c n^{5/2} 2-faces which does not contain a triangulation of any orientable closed surface \cal S.

We can ask the same question also for pseudomanifolds. What is the number of edges that guarantees a subcomplex with the property that every 1-face is included in precisely two 2-faces.

3) Nati conjectured that for every 2-dimensional simplicial complex S there is a constant C_S such that a 2-dimensional simplicial complex with $n$ vertices and $C_Sn^{5/2}$ 2-faces always contains a homeomorph of S. The paper  by Andrey, Alexandr, István, and Dmitriy asserts that proving the exponent 5/2 for the real projective space will imply the same exponent for all nonorientable closed surfaces.

4) The paper also mentions an unpublished result by Friedgut and Linial that n^{8/9} 2-faces suffice for a torus.

5) Here is another problem I am curious about: How many 2-faces guarantee a subcomplex K with H_2(K) \ne 0 and H_1(K)=0?  (You can choose the field of coefficients.)  Without the second requirement the answer is roughly n^2

Universal exponent for homeomorphs.

Nati’s Problem 2: Given a k-dimensional-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)

Jason Long, Bhargav Narayanan, and Corrine Yap:  Simplicial homeomorphs and trace-bounded hypergraphs 

Abstract: Our first main result is a uniform bound, in every dimension k \in \mathbb N, on the topological Turán numbers of k-dimensional simplicial complexes: for each k \in \mathbb N, there is a \lambda_k \ge k^{-2k^2} such that for any k-dimensional simplicial complex S, every k-complex on n \ge n_0(S) vertices with at least n^{k+1-\lambda_k}  facets contains a homeomorphic copy of S.

This was previously known only in dimensions one and two, both by highly dimension-specific arguments: the existence of \lambda_1 is a result of Mader from 1967, and the existence of \lambda_2 was suggested by Linial in 2006 and recently proved by Keevash-Long-Narayanan-Scott.

Jason Long, Bhargav Narayanan, and Corrine Yap deduce this theorem  from a very interesting purely combinatorial result about trace-bounded hypergraphs.

Here is the link to the aforementioned paper Peter Keevash, Jason Long, Bhargav Narayanan, and Alex Scott: A universal exponent for homeomorphs. The main theorem asserts that \lambda_2 can be taken to be 14/5.

Let me also mention a 2018 result by  Agelos Georgakopoulos, John Haslegrave, Richard Montgomery, and Bhargav Narayanan  in their 2018 paper Spanning surfaces in 3-graphs where they prove a topological extension of Dirac’s theorem about Hamiltonian cycles in graphs proposed by Gowers in 2005.

Finally, finding the correct value for \lambda_k would be very interesting.

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s