Combinatorics

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 May 13

Combinatorics: Shira Zerbib (U. Michigan, Iowa State University) "Envy-free division of a cake without the “hungry players" assumption"

11:00am to 1:00pm

Location: 

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 May 06

Combinatorics: Omri Ben Eliezer (TAU) "Finding patterns in permutations"

11:00am to 1:00pm

Location: 

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 May 27

Combinatorics: Uri Rabinovich (U. Haifa) "SOME EXTREMAL PROBLEMS ABOUT SIMPLICIAL COMPLEXES"

11:00am to 1:00pm

Location: 

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 Apr 15

Combinatorics: problem session

11:00am to 1:00pm

Location: 

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.
2019 Apr 01

Combinatorics: Raphy Yuster (U. Haifa) "On some Ramsey type problems in tournaments"

11:00am to 1:00pm

Location: 

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 Jun 17

NO seminar: mini conference in memory of Prof. Yossi Zaks at U. Haifa

11:00am to 1:00pm

Location: 

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 ) Speakers: Noga Alon (Princeton and Tel Aviv University) Gil Kalai (Hebrew University) Nati Linial (Hebrew University) Rom Pinchasi (Technion) Schedule: 10:00-10:15 Greetings 10:15-11:05 Noga Alon 11:05-11:25 Coffee break 11:25-12:15 Gil Kalai 12:15-14:00 Lunch break to attendees (catering) 14:00-14:50 Nati Linial
2019 Apr 29

Combinatoric: Karthik C. Srikanta (Weizmann Institute) "On Closest Pair Problem and Contact Dimension of a Graph"

11:00am to 1:00pm

Location: 

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

Combinatorics: Kim Minki (Technion) "The fractional Helly properties for families of non-empty sets"

11:00am to 1:00pm

Location: 

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$.

Pages