Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

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

**Duration**: 30 minutes

**Location**: OAT S15/S16/S17

**Speaker**: Zhihan Jin

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!)

Previous talks by year: 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login