Combinatorics

2018 Jun 11

Combinatorics: Chris Cox (CMU) "Nearly orthogonal vectors"

11:00am to 12:30pm

Location: 

IIAS, Eilat hall, Feldman bldg, Givat Ram
Speaker: Chris Cox, CMU Title -- Nearly orthogonal vectors Abstract -- How can $d+k$ vectors in $\mathbb{R}^d$ be arranged so that they are as close to orthogonal as possible? In particular, define $\theta(d,k):=\min_X\max_{x
2018 Jun 18

Combinatorics -- Erdos lecture cancelled; instead (NOTE THE TIME!) :

10:30am to 12:30pm

Location: 

IIAS, Eilat hall, Feldman bldg (top floor), Givat Ram
Speaker: Ilan Newman and Yuri Rabinovich, U.Haifa Title: Sparsifiers - Part I (Part II from 2pm to 4pm, same day and place) Abstract: Time permitting, we plan to discuss the following topics (in this order): 1. * Additive Sparsification and VC dimension * Multiplicative Sparsification * Examples: cut weights, cut-dimension of L_1 metrics, general metrics, and their high-dimensional analogues 2. * Multiplicative Sparsification and Triangular Rank; * Karger-Benczur sparsification of cuts weights 3. * Batson-Spielman-Srivastava sparsification
2018 Jun 25

Combinatorics: Roman Glebov (HU) "Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs"

11:00am to 12:30pm

Location: 

IIAS, Eilat hall, Feldman bldg, Givat Ram
Speaker: Roman Glebov (HU) Title: Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs Abstract: Consider the random process in which the edges of a graph $G$ are added one by one in a random order. A classical result states that if $G$ is the complete graph $K_{2n}$ or the complete bipartite graph $K_{n,n}$, then typically a perfect matching appears at the moment at which the last isolated vertex disappears. We extend this result to arbitrary $k$-regular bipartite graphs $G$ on $2n$ vertices for all $k=\Omega(n)$.
2018 May 21

Combinatorics: Daniel Kalmanovich and Or Raz (HU) "2 talks back-to-back"

11:00am to 12:30pm

Location: 

IIAS, Eilat hall, Feldman Building, Givat Ram
First speaker: Daniel kalmanovich, HU Title: On the face numbers of cubical polytopes Abstract: Understanding the possible face numbers of polytopes, and of subfamilies of interest, is a fundamental question. The celebrated g-theorem, conjectured by McMullen in 1971 and proved by Stanley (necessity) and by Billera and Lee (sufficiency) in 1980-81, characterizes the f-vectors of simplicial polytopes.
2018 May 07

Combinatorics: Zur Luria (ETH), "New bounds for the n-queen's problem"

11:00am to 12:30pm

Location: 

IIAS, Eilat hall, Feldman bldg, Givat Ram
Speaker: Zur Luria, ETH Title: New bounds for the n-queen's problem Abstract: The famous n-queens problem asks: In how many ways can n nonattacking queens be placed on an n by n chessboard? This question also makes sense on the toroidal chessboard, in which opposite sides of the board are identified. In this setting, the n-queens problem counts the number of perfect matchings in a certain regular hypergraph. We give an extremely general bound for such counting problems, which include Sudoku squares and designs.
2018 May 14

Combinatorics: Joel Friedman (UBC) "Open Problems Related to the Zeta Functions"

11:00am to 12:30pm

Location: 

IIAS, Eilat hall, Feldman bldg, Givat Ram
Speaker: Joel Friedman, UBC Title: Open Problems Related to the Zeta Functions Abstract: We express some open problems in graph theory in terms of Ihara graph zeta functions, or, equivalently, non-backtracking matrices of graphs. We focus on "expanders" and random regular graphs, but touch on some seemingly unrelated problems encoded in zeta functions. We suggest that zeta functions of sheaves on graphs may have relevance to complexity theory and to questions of Stark and Terras regarding whether coverings of a fixed graph can ramify like number field extensions.
2017 Apr 30

Combinatorics: Amir Yehudayoff (Technion) TBA

Repeats every week every Sunday until Sun Jun 25 2017 except Sun Apr 30 2017.
11:00am to 1:00pm

11:00am to 1:00pm
11:00am to 1:00pm
11:00am to 1:00pm
11:00am to 1:00pm
11:00am to 1:00pm
11:00am to 1:00pm
11:00am to 1:00pm
11:00am to 1:00pm

Location: 

Rothberg B221 (CS building)
Speaker: Misha Tyomkyn (TAU) Title: Lagrangians of hypergraphs and the Frankl-Furedi conjecture Abstract: Frankl and Furedi conjectured in 1989 that the maximum Lagrangian of all r-uniform hypergraphs of given size m is realised by the initial segment of the colexicographic order. For r=3 this was partially solved by Talbot, but for r\geq 4 the conjecture was widely open. We verify the conjecture for all r\geq 4, whenever $\binom{t-1}{r} \leq m \leq \binom{t}{r}- \gamma_r t^{r-2}$ for a constant $\gamma_r>0$. This range includes the principal case
2015 Nov 02

Combinatorics seminar

Repeats every week every Monday until Sun Nov 08 2015 .
11:00am to 1:00pm

Abstract: Expander graphs have many wonderful properties, and have been an immensely useful and fruitful area of research in both applicative and theoretical fields. There has been a lot of interest recently in the study of higher dimensional generalizations of expanders to d-uniform hypergraphs. Many competing definitions have been proposed, and different definitions may be appropriate depending on the property of expanders that we wish to preserve.
2017 Dec 07

Combinatorics: Shira Zerbib Gelaki (MSRI, U. Michigan) "Colorful coverings of polytopes -- the hidden topological truth behind different colorful phenomena"

12:00pm to 1:00pm

Location: 

Room 101 in Sprinzak
Speaker: Shira Zerbib Gelaki (MSRI, University of Michigan) Title: Colorful coverings of polytopes -- the hidden topological truth behind different colorful phenomena Abstract: The topological KKMS Theorem is a powerful extension of the Brouwer's Fixed-Point Theorem, which was proved by Shapley in 1973 in the context of game theory. We prove a colorful and polytopal generalization of the KKMS Theorem, and show that our theorem implies some seemingly unrelated results in discrete geometry and combinatorics involving colorful settings.

Pages