Activities This Week

The Shannon capacity of a graph $G$ is defined as $\Theta(G):=\sup_n \alpha(G^{\otimes n})^{1/n}$ where $G^{\otimes n}$ is the $n$th tensor power of $G$. Determining $\Theta(G)$ is notoriously difficult, but there are two general upper bounds: Lovasz’s theta function and Haemers’ bound. In this talk, we present a fractional version of Haemers’ bound, originally due to Blasiak, which roughly works by embedding the vertices of $G$ as large subspaces under adjacency constraints. This bound is a common strengthening of both Haemers’ bound and the fractional chromatic number of a graph. We show that this fractional version out-performs any bound on the Shannon Capacity that could be attained through Haemers’ bound and show also that this bound in multiplicative, similar to Lovasz’s theta function. (Joint work with Boris Bukh)

I will discuss the equidistribution of certain parameters of primitive integral points in Euclidean space, as their norms tend to infinity. These parameters include directions of integral points on the unit sphere, the integral grids in their orthogonal hyperplanes, and the shortest solutions to their associated gcd equations. These equidistribution statements follow from counting lattice points in the real Special Linear group.

הכללות של שאלות טבעיות בתורת הגרפים הסופיים לגרפים אינסופיים לעתים קלות יותר להבנה, לעתים קשות יותר, וקורה גם שהן לא ניתנות להכרעה על בסיס האקסיומות המקובלות למתמטיקה. בהרצאה נסקור שאלות כאלה ונראה שתופעת אי התלות יכולה גם לעזור ולא רק להפריע.