2019
Jun
03

# Combinatorics - back to back:

11:00am to 1:00pm

## Location:

CS Rothberg bldg, room B-500, Safra campus

First talk:
Speaker: Madeleine Weinstein (Berkeley)
Title: Voronoi Cells of Varieties
Abstract:

2019
Jun
03

11:00am to 1:00pm

CS Rothberg bldg, room B-500, Safra campus

First talk:
Speaker: Madeleine Weinstein (Berkeley)
Title: Voronoi Cells of Varieties
Abstract:

2019
May
06

11:00am to 1:00pm

CS building, room B-500, Safra campus

Speaker: Omri Ben Eliezer, TAU
Title: Finding patterns in permutations
Abstract:
For two permutations sigma and pi, we say that sigma contains a copy of
pi, if there is a subset (not necessarily consecutive) of elements in sigma,
whose relative order is the same as in pi. For example, if pi = (1,2,3),
then a copy of pi in sigma amounts to an increasing subsequence in sigma
of length 3.
As shown by Guillemot and Marx, a copy of a constant length pi can be
found in sigma in linear time. However, how quickly can one find such a

2019
Jun
10

11:00am to 1:00pm

CS bldg, room B-500, Safra campus

Speaker: Eyal Karni (BIU)
Title: Combinatorial high dimensional expanders
Abstract:
An eps-expander is a graph G=(V,E) in which every set of vertices X where |X|<=|V|/2 satisfies |E(X,X^c)|>=eps*|X| . There are many edges that "go out" from any relevant set.

2019
May
27

11:00am to 1:00pm

CS Rothberg bldg, room B-500, Safra campus

Speaker: Uri Rabinovich (U. Haifa)
Title: SOME EXTREMAL PROBLEMS ABOUT SIMPLICIAL COMPLEXES
Abstract:
We shall discuss the following three issues:
* The existence of Hamiltonian d-cycles, i.e., simple d-cycles containing a spanning d-hypertree of a complete d-complex K_n^d;
* The existence of a distribution D over spanning d-hypertrees T of K_n^d, so that for ANY
(d-1)-cycle C there, the expected size of the d-filling of C with respect to a random T from D is Omega(n^d);
* The existence of f(k,d) such that any d-simplex of rank r with > f(k,d)*r d-faces contains

2019
Jun
24

11:00am to 1:00pm

CS bldg, room B-500, Safra campus

Speaker: Doron Puder, TAU
Title: Aldous' spectral gap conjecture for normal sets
Abstract:
Aldous' spectral gap conjecture, proved in 2009 by Caputo, Liggett and Richthammer, states the following a priori very surprising fact: the spectral gap of a random walk on a finite graph is equal to the spectral gap of the interchange process on the same graph.

2019
May
13

11:00am to 1:00pm

CS bldg, room B-500, Safra campus

Speaker: Shira Zerbib (U. Michigan, Iowa State University)
Title: Envy-free division of a cake without the “hungry players" assumption
Abstract:
The fair division theorem due to Stromquist (1980) ensures that under some conditions it is possible to divide a rectangular cake into n pieces and assign one piece to each of n players such that no player strictly prefers a piece that has not been assigned to him.

2019
Apr
01

11:00am to 1:00pm

CS B-500, Safra campus

Speaker: Raphy Yuster, U. Haifa
Title: On some Ramsey type problems in tournaments
Abstract:
I will talk about several Ramsey type problems in tournaments guaranteeing the existence of subgraphs with certain chromatic properties.
Here are two such problems which attracted some attention recently:
1. Let g(n) be the smallest integer such that every tournament with more than g(n) vertices has an *acyclic subgraph* with chromatic number larger than n.
It is straightforward that Omega(n) <= g(n) <= n^2. An improvement of both bounds is presented.

2019
Mar
18

11:00am to 1:00pm

CS B-500, Safra campus

Speaker: Arindam Banerjee, RMVERI
Title: Castelnuovo-Mumford Regularity, Combinatorics and Edge Ideals.
Abstract:

2019
Jun
17

11:00am to 1:00pm

U. Haifa

From Raphy Yuster: On Monday 17 June, 2019 we will hold a one day mini conference in memory of Professor Yossi Zaks
(see attached poster or updated information in
http://sciences.haifa.ac.il/math/wp/?page_id=1382 )
Mini conference: Yossi Zaks Memorial Meeting – Monday, June 17, 2019
list of speakers
Noga Alon, Princeton University and Tel Aviv University
Gil Kalai, Hebrew University
Nati Linial, Hebrew University
Rom Pinchasi, The Technion
Organizers
Raphael Yuster, University of Haifa

2019
Apr
29

11:00am to 1:00pm

CS B-500, Safra campus

Speaker: Karthik C. Srikanta (Weizmann Institute)
Title: On Closest Pair Problem and Contact Dimension of a Graph
Abstract: Given a set of points in a metric space, the Closest Pair problem asks to find a pair of distinct points in the set with the smallest distance. In this talk, we address the fine-grained complexity of this problem which has been of recent interest. At the heart of all our proofs is the construction of a family of dense bipartite graphs with special embedding properties and are inspired by the construction of locally dense codes.

2019
Apr
08

11:00am to 1:00pm

CS B-500, Safra campus

Speaker: Kim Minki, Technion
Title: The fractional Helly properties for families of non-empty sets
Abstract:
Let $F$ be a (possibly infinite) family of non-empty sets.
The Helly number of $F$ is defined as the greatest integer $m = h(F)$ for which there exists a finite subfamily $F'$ of cardinality $m$ such that every proper subfamily of $F'$ is intersecing and $F'$ itself is not intersecting.
For example, Helly's theorem asserts that the family of all convex sets in $d$-dimensional Euclidean space has Helly number $d+1$.

2019
Mar
25

11:00am to 1:00pm

CS B-500, Safra campus

Speaker: Roy Meshulam (Technion)
Title: Topology and combinatorics of the complex of flags
Abstract:

2019
May
20

2019
Apr
15

11:00am to 1:00pm

CS B-500, Safra campus

Speaker: Eyal Karni, BIU
Title: Combinatorial high dimensional expanders
Abstract:
An eps-expander is a graph G=(V,E) in which every set of vertices X where |X|<=|V|/2 satisfies |E(X,X^c)|>=eps*|X| . There are many edges that "go out" from any relevant set.

2018
Dec
24

11:00am to 1:00pm

Rothberg CS room B500, Safra campus, Givat Ram

Speaker: Benny Sudakov, ETH, Zurich
Title: Subgraph statistics
Abstract:
Consider integers $k,\ell$ such that $0\le \ell \le \binom{k}2$. Given
a large graph $G$, what is the fraction of $k$-vertex
subsets of $G$ which span exactly $\ell$ edges? When $G$ is empty or
complete, and $\ell$ is zero or $\binom k 2$,
this fraction can be exactly 1. On the other hand if $\ell$ is not one
these extreme values, then by Ramsey's theorem, this
fraction is strictly smaller than 1.
The systematic study of the above question was recently initiated by