 ## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, August 23, 2022, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Zhihan Jin

## Semi-algebraic And Semi-linear Ramsey Numbers

The hypergraph Ramsey number R_r(s,n) denotes the smallest N such that any r-uniform hypergraph on N vertices has some clique of size s or some independent set of size n. The classic result by Erdős, Rado and Erdős, Rado and Hajnal says that tw_{r-1}(cn^2) < R_r(n,n) < tw_r(c'n) where c and c' are two constants.It remains open to close this gap since their papers in 1952 and 1965, respectively.
What about the Ramsey number of hypergraphs defined in a geometric setting? The so-called semi-algebraic hypergraphs are those whose vertices are points in R^d, and each hyperedge is determined by the signs of some fixed polynomials if you feed in the related points. We can also define the Ramsey number for the r-uniform semi-algebraic hypergraphs as R_r'(s,n). In the asymmetric case (s is a constant), we prove that R_3'(4,n) > 2^{log^{1.33}n}, refuting a conjecture (by Conlon, Fox, Pach, Sudakov and Suk) say R_3(s,n)=poly n. For the symmetric case (s=n), we prove that R_r'(n,n) < 2^{poly n} when all defining polynmials are linear functions, a different growth compared to the general bound R_r'(n,n) = tw_{r-1}(poly n).

Upcoming talks     |     All previous talks     |     Talks by speaker     | Upcoming talks in iCal format (beta version!)

Information for students and suggested topics for student talks