Date/Time : 05 Dec 2024 14:00
Venue : S17 #04-04 (SR3)
Speaker : Hong Liu, Institute for Basic Science, South Korea

A well-known theorem of Nikiforov asserts that any graph with a positive $K_r$-density contains a logarithmic blowup of $K_r$. We explore variants of Nikiforov’s result and investigate when positive clique density condition implies the existence of a significantly larger blowup of a clique. Our results study such problems for families of ordered graphs with forbidden induced monotone path, obtaining optimal bounds. As corollaries, we strengthen a result of Pach and Tomon, and resolve a conjecture of Tomon in a strong form. To find a large blowup, we reduce the embedding problem to a certain Ramsey problem. For optimal lower bound constructions, we make use of concentration of measure and the isodiametric inequality on high dimensional spheres.

Add to calendar :

Date/Time : 02 Nov 2022 14:00
Venue : via Zoom
Speaker : Zilin Jiang, Arizona State University

Join Zoom Meeting
https://nus-sg.zoom.us/j/81639604748?pwd=UXZXTnhwZHRmQTFrZEs0VEtWYjRVUT09

Meeting ID: 816 3960 4748
Passcode: 23571113

A set of unit vectors in a Euclidean space is called a spherical two-distance set if the pairwise inner products of these vectors assume only two values α and β. It is known that the maximum size of a spherical two-distance grows quadratically as the dimension of the Euclidean space grows. However when the values α and β are held fixed, a very intricate behavior of the maximum size emerges. Building on our recent resolution in the equiangular case, that is β = -α, we make a plausible conjecture which connects this behavior with spectral theory of signed graphs in the regime β < 0 ≤ α, and we confirm this conjecture when α + 2β < 0 or (1 – α)/(β-α) < 2.0198. Joint work with Alexandr Polyanskii, Jonathan Tidor, Yuan Yao, Shengtong Zhang and Yufei Zhao.

Add to calendar :