? Between Combinatorics and Topology
            Between Combinatorics and Topology,   Jerusalem 24-28.11.14


Program
all lectures will take place in Rothberg B-220 (31.776507, 35.19780)

Monday

  9:00-10:45    Nati Linial    A combinatorial approach to simplicial complexes
  11:00-13:00    Ron Aharoni   Fair representation
  13:00-14:30    Lunch
  14:30-16:00    Joel Hass    Knots, knot diagrams, and Reidemeister moves
  16:30-18:00    A very vivid discussion on problems, questions, and new trends
        of combinatorial topology and topological combinatorics

Tuesday

  9:00-10:30    Tadeusz Januszkiewicz    Topology of aspherical spaces and combinatorics
  10:45-12:15    Yuval Peled    On the phase transition in random simplicial complexes
  12:30-14:00    Lunch
  14:00-15:30    Gil Kalai    Topological Helly type theorems
  15:45-16:30    Abigail Thompson    Triangulation of the 2-sphere

Wednesday

  9:00-10:30    Roy Meshulam    Higher dimensional expansion
  10:45-11:45    Nir Lazarovich    Uniqueness of regular CAT(0) complexes
  12:00-12:30    Eran Nevo    How many n-vertex triangulations does the 3-sphere have?
  12:30-14:00    Lunch
  14:00-14:45    Tomasz Elsner    Applications of minimal surfaces to systolic spaces
  14:50-15:35    Yuri Rabinovich    On connectivity of the facet graphs
              of d-cycles, d-hypertrees and d-hypercuts
  15:40-16:15    Deepak Rajendraprasad    On boundaries of the d-hypertrees

                              Conference dinner in Chakra restaurant

Thursday

  9:00-10:30    Chaim Even Zohar    Invariants of random knots and links
  10:40-11:40    Sylwia Antoniuk    When does the random group stop being free
  11:50-12:50    Elliot Paquette   Local spectral expansion in random complexes
  13:00-14:00    Lunch




Abstracts


Ron Aharoni, Fair representation
A conjecture of Ryser-Brualdi-Stein from the 1970s is that in a Latin square of order n there exists a transversal (permutation submatrix with distinct symbols) of size n-1. This can be generalized to:
Conjecture: Let (A1, ... ,Am) be a partition of the edge set of Kn,n. There exists then a perfect matching F that represents the partition fairly in a similar sense to that by which a parliament represents fairly the population of voters, namely
|S ∩ Ai| ≥
|S||Ai| / |V| -1
for all i, with the "minus 1" needed only for one i.

We prove this for m=2,3.
We also prove that a partition of the vertices of a path on n vertices into m parts can be fairly represented by an independent set of size ⌊(n-m)/2⌋.
Both proofs are topological - the first uses Sperner's lemma, and the second the Borsuk Ulam theorem. I will also discuss the connection of the conjecture to other conjectures on the intersection of matroids.
Joint work with E. Berger, M. Chudnovsky, D. Kotlar, M. Loebl and R. Ziv.

Sylwia Antoniuk, When does the random group stop being free
We consider a model Γ(n,p) of a random triangular group, which is a group generated by a random presentation < S | R > with a set of n relators S, a set of relators R all of length three and such that each relator is present in R independently with probability p=p(n). We study the asymptotic behavior of this group when the number of generators n goes to infinity. In particular, we show that for a certain constant c > 0, p=c/n2 is the threshold for the property of being a free group.

Tomasz Elsner, Applications of minimal surfaces to systolic spaces

Joel Hass, Knots, knot diagrams, and Reidemeister moves

Tadeusz Januszkiewicz, Topology of aspherical spaces and combinatorics
In the talk we present some problems related to h polynomial of a flag complex. We explain how such a polynomial emerges in homology computations related to Coxeter groups and buildings, what are conjectural restrictions, and describe how to use it to study boundaries of some CAT -1 complexes.

Gil Kalai, Topological Helly type theorems
We will give an outline of results and problems on topological Helly-type problems, relations to graph theory and to high-dimensional expanders.

Nati Linial, A combinatorial approach to simplicial complexes
The relationship between combinatorics and topology was not always rosy. There is a saying famously attributed to the great Whitehead that "graph theory is the slums of topology". But present day graph theory is nothing like it was in Whitehead's times. Our current perspective of modern combinatorics suggests that there are many intriguing potential connections between the two fields. In particular, we have gained very profound insights with applications of the probabilistic method in graph theory and in combinatorics, and this indicates new ways of investigating random topological structures. In particular there are very simple and natural ways of defining random simplicial complexes and the properties of such complexes are fascinating. In my lecture I will explain some of our recent discoveries and several of the many open problems that these studies raise.
This talk is based on joint papers with the following coauthors: R. Meshulam, T. Łuczak, I. Newman, Y. Rabinovich, M. Rosenthal, L. Aronshtam and Y. Peled.

Nir Lazarovich, Uniqueness of regular CAT(0) complexes
Over the past years CAT(0) cubical and polygonal complexes have played a major role in geometric group theory and have provided many examples of interesting group actions on CAT(0) spaces. In the search for highly symmetric CAT(0) complexes - just as for their 1-dimensional analogues, trees - it is natural to consider the sub-class of "regular" CAT(0) complexes, i.e., complexes with the same link at each vertex. However, unlike regular trees, general regular CAT(0) complexes are not necessarily uniquely determined by their links. In this talk, we will discuss a necessary and sufficient condition for uniqueness of regular CAT(0) cubical and polygonal complexes. We will then explore some examples of unique regular cube complexes and the properties of their automorphism groups.

Deepak Rajendraprasad, On boundaries of the d-hypertrees
A d-hypertree over [n] is the maximal acyclic set of d-simplices over [n]. Let the underlying filed be F2. What are the boundaries of d-hypertrees? In particular, is there a Hamiltonian d-hypertree, i.e., a d-hypertree whose boundary is just the boundary of d-simplex? For d=1, the obvious answer is: S is a boundary of a spanning tree iff S is an even-size subset of [n]. For d=2, a not so obvious answer turns out to be: The set S of 1-simplices is a boundary of a 2-hypertree iff S is a 1-cycle, and |S| = (n-1)(n-2)/2 mod 2. For d>2, we do not know the full answer. One of the partial results is: For every (d-1)-cycle S there exists a (d-1)-cycle S' such that S' is a boundary of a d-hypertree T, and | S XOR S' | = O(|T|/n).
Joint work with Rogers Matthews, Ilan Newman, and Yuri Rabinovich.

Roy Meshulam, Higher dimensional expansion
Cohomological expansion is a natural higher dimensional version of the Cheeger constant. We will discuss this notion and some of its applications. In particular, we'll describe a probabilistic construction of 2-dimensional expanders with bounded degree, and some results on the expansion of building-like complexes.
Joint work with A. Lubotzky and S. Mozes.

Eran Nevo, How many n-vertex triangulations does the 3-sphere have?
We give an almost tight answer for the question from the title by improving the lower bound, via a construction which will be described in the talk.
Joint work with Francisco Santos and Stedman Wilson.

Yuri Rabinovich, On connectivity of the facet graphs of d-cycles, d-hypertrees and d-hypercuts
A facet graph G(S) of a set S of r-simplices over [n] has a vertex for every simplex in S, and has an edge for every two d-simplices in S sharing a common (r-1)-face. We study the connectivy properties of the facet graphs of basic combinatorial-topological d-dimensional objects such as simple d-cycles Z, d-hypertrees T and d-hypercuts C, of the complete d-dimensional simplicial complex K_n^d over [n]. We show, in particular, that
* G(Z) is (d+1)-vertex connected, as one would expect in view of the dual Balinksy theorem;
* G(T) is d-vertex connected;
* G(C) is (n-d-1)-vertex connected.
The methods involve basic tools from Algebraic Topology, and work well for these and other connectivity-related problems about simplicial- and cell-complexes.
Joint work with Ilan Newman.

Elliot Paquette, Local spectral expansion in random complexes
For showing the homology of random simplicial complexes vanishes in a variety of models, the notion of local spectral expansion has proven to be a useful tool. We will introduce this tool and show how it can be used to sharpen some homology threshold theorems for random simplicial complexes, as well as give a free product decomposition for the fundamental group of the Linial-Meshulam complex for a small range of face density. We will also show how local spectral expansion relates to other notions of expansion and give some open questions related to extensions of this method.

Yuval Peled, On the phase transition in random simplicial complexes
It is well-known that the G(n,p) model of random graphs undergoes a dramatic change around p=1/n. It is here that the random graph is, almost surely, no longer a forest, and here it first acquires a giant connected component. Several years ago, Linial and Meshulam have introduced the Xd(n,p) model, a probability space of n-vertex d-dimensional simplicial complexes, where X1(n,p) coincides with G(n,p). Within this model we prove a natural d-dimensional analog of these graph theoretic phenomena. Specifically, we determine the exact threshold for the nonvanishing of the real d-th homology of complexes from Xd(n,p), and show that it is strictly greater than the threshold of d-collapsibility. In addition, we compute the real Betti numbers, i.e. the dimension of the homology groups, of Xd(n,p) for p=c/n. Finally, we establish the emergence of giant shadow at this threshold. (For d=1 a giant shadow and a giant component are equivalent). Unlike the case for graphs, for d > 1 the emergence of the giant shadow is a first order phase transition.
Joint work with Nati Linial.

Chaim Even Zohar, Invariants of Random Knots and Links
We study random knots and links in R3 using the Petaluma model, which is based on the petal projections developed by Adams et al. (2012). In this model we obtain a formula for the distribution of the linking number of a random two-component link. We also obtain formulas for the expectations and the higher moments of the Casson invariant and the order-three knot invariant v3. These are the first precise formulas given for the distributions of invariants in any model for random knots or links. We also use numerical computation to compare these to other random knot and link models, such as those based on grid diagrams.
All terms above will be defined and explained.
Joint work with Joel Hass, Nati Linial, and Tahl Nowik.



Participants

Karim Adiprasito sunya00@gmail.com
Ron Aharoni ra@techunix.technion.ac.il
Sylwia Antoniuk sylwia.antoniuk@gmail.com
Yuri Arbin yuri@cs.haifa.ac.il
Lior Aronshtamliobsar@gmail.com
Tomasz ElsnerTomasz.Elsner@math.uni.wroc.pl
Emmanuel Dror Farjoun farjoun@ma.huji.ac.il
Joel Hass joelhass@gmail.com
Tadeusz Januszkiewicz   tjan@impan.pl
Gil Kalaigil.kalai@gmail.com
Tali Kaufmankaufmant@mit.edu
Nir Lazarovichnirlazarovich@gmail.com
Nati Linialnati@cs.huji.ac.il
Alex Lubotzkyalexlub@math.huji.ac.il
Tomasz Łuczak tomasz@amu.edu.pl
Rogers Mathewrogersmathew@gmail.com
Roy Meshulammeshulam@math.technion.ac.il
Ilan Newman ilan@cs.haifa.ac.il
Eran Nevo nevo.eran@gmail.com
Tahl Nowik tahl@math.biu.ac.il
Damian Osajda dalosaj@gmail.com
Elliot Paquetteelliot.paquette@gmail.com
Yuval Peledypeledy@gmail.com
Wojciech Politarczyk w.politarczyk@gmail.com
Yuri Rabinovich yuri@cs.haifa.ac.il
Deepak Rajendraprasad deepakmail@gmail.com
Zlil Sela zlil@math.huji.ac.il
Jacek ŚwiątkowskiJacek.Swiatkowski@math.uni.wroc.pl
Abigail Thompsonthompson@math.ucdavis.edu
Bartosz Zaleski balzak@amu.edu.pl
Shira Zerbibshira.zerbib@gmail.com
Chaim Even Zohar chaimevenzohar@yahoo.com