Abstracts

Improvisations on the Hall marriage theorem: Completing Latin squares and Sudokus
Eli Shamir, Hebrew University

Abstract: The key concept of our discussion is that of a perfect matching (PM) in a bipartite graph. The expansion condition in Hall's marriage theorem can be extended to an unbiased 2-sided one. This enables an alternative (and simpler) proof of Evans' (proven) Conjecture:

A partial nxn Latin square with n-1 dictated entries admits a completion to a full Latin square.

PMs are used to successively fill the square by rows, columns or diagonals. Latin square tables correspond to quasi-groups; the ones corresponding to groups are only a tiny fraction of them, as n grows. However, for Sudoku tables of order mnxmn, the completion (say by diagonals) usually fails, even if there are no dictated entries, unless they are conjugates of a twisted product of two groups, of orders n and m.

An open problem for sudoku lovers: Is there a sudoku square (of any order) which is not a conjugate of a twisted product of groups?

No prior knowledge needed.

Back

Same Graph, Different Universe
Assaf Rinot, Bar-Ilan University

Abstract: May the same graph admit two different chromatic numbers in two different universes? How about infinitely many different values? And can this be achieved without changing the cardinals structure?

In this talk, we shall give various examples of graphs+universes that address the above questions.

Back

Mixing, coloring and expansion of Ramanujan complexes
Konstantin Golubev, Hebrew University

Abstract: Ramanujan graphs, constructed by Lubotzky, Phillips and Sarnak and known also as the LPS graphs, are certain quotients of the Bruhat-Tits building of PGL_2(Q_p). These graphs form a family of expander graphs, and serve as an explicit construction of graphs of high girth and large chromatic number. High dimensional counterparts of the LPS graphs are the Ramanujan Complexes, constructed by Lubotzky, Samuels and Vishne, as quotients of the Bruhat-Tits building of PGL_d over a non-archimedean field of finite characteristic. I'll talk about the mixing of these complexes, which implies that they have good expansion and large chromatic number.

If time permits, I'll talk about analogous results for general hypergraphs satisfying certain regularity condition.

Joint work with S.Evra, A.Lubotzky.

Back

Every property of outerplanar graphs is testable in O(poly(\log n)) queries
Ilan Newman, University of Haifa

Abstract: For a graph on $n$ vertices, and an integer $D$, let the $D$-local view of $G=(V,E)$ be the collection (multiset) of the unlabelled $n$ balls of distance $D$ around the vertices.

The main question that motivates this study is: what can be said about $G$ knowing only its $D$-local view for some constant $D$?

For constant bounded degree planar (or more generally hyperfinite) graphs, Newman-Sohler [2011], following a long sequence of works, show that for any $\epsilon > 0$ there is a $D$ such that the $D$-local view of the graph determines the graph up to the deletion / insertion of at most $\epsilon n$ edges. This, in turn, implies that every property of planar (hyperfinite) graphs can be tested, in the sense of property testing, by constantly many queries.

What happens in non-bounded degree planar graphs? The answer is currently still open. However, we show, following Yoshida's results on forests, that the above phenomenon still holds for outerplanar graphs. The implication to testing is deteriorated, though: Testing now requires $O(poly(\log n))$ queries.

I will describe the ideas behind the two results, the latter of which is a joint work with Jasine Babu and Areej Khoury.

Back

Local and global colorability of graphs
Omri Ben-Eliezer, Tel-Aviv University

Abstract: It is shown that for any fixed c \geq 3 and r, the maximum possible chromatic number of a graph on n vertices in which every subgraph of radius at most r is c-colorable is n^(1/r+1) up to a multiplicative factor logarithmic in n: in fact, it is O((n/log(n)) ^ (1/r+1)) and Omega(n^(1/r+1) / log(n)).

The proof is based on a careful analysis of the local and global colorability of random graphs and implies, in particular, that a random n-vertex graph with the right edge probability has typically a chromatic number as above and yet most balls of radius r in it are 2-degenerate.

Joint work with Noga Alon.

Back

Uncertainty principle in the hypercube and short vectors in linear codes
Alex Samorodnitsky, Hebrew University

Abstract: The uncertainty principle in the n-dimensional hypercube states that if a non-zero function is supported in A and its Fourier transform is supported in B, then |A||B| is at least 2^n.

We consider a relaxed version, requiring only a non-negligible fraction of the l_2 norm of the function to be attained in A and of its transform in B. Provided either A or B is a Hamming ball, we give a description of the possible joint behavior of |A| and |B|. This description is tight on the exponential scale (that is, assuming both A and B are exponentially small). The main technical tool we use is a stronger version of the hypercontractive inequality for functions with exponentially small support.

As a corollary we show that any binary linear code contains "many" (in the appropriate sense) codewords whose length is close to that guaranteed by the linear programming bound.

Joint work with Yury Polyanskiy.

Back

(k,l)-suitable digraphs
Rani Hod, Bar-Ilan University

Abstract: We discuss a generalization of k-suitable permutations, defined in 1950 by Dushnik in the context of the order dimension of the boolean lattice.

We relate suitable digraphs to communication settings and prove lower and upper bounds on the cardinality of families of (k,l)-suitable digraphs.

Joint work with Elad Haramaty, Aaron Potechin and Madhu Sudan.

Back

Random knots
Tahl Nowik, Bar-Ilan University

Abstract: We introduce a new model for random knots and links, based on the petal projection developed by C. Adams et al. We study the distribution of various invariants of knots and links in this model. We view a knot invariant as a random variable on the set of all petal diagrams with n petals, and ask for its limiting distribution as n --> infinity. We obtain a formula for the limiting distribution of the linking number of a random two-component link. We obtain formulas for all moments of the two most basic Vassiliev invariants of knots, which are related to the Conway polynomial and the Jones polynomial. These are the first precise formulas given for the distributions or moments of invariants in any model for random knots and links.

Joint work with Chaim Even-Zohar, Joel Hass, and Nati Linial.

Back

Rational polygons: Odd compression ratio and odd plane coverings
Yuri Rabinovich, University of Haifa

Abstract: We show that for any rational polygon P in the plane, and any odd-sized collection of translates of P, the area of the set of points covered by an odd number of these translates is bounded away from 0 by a universal constant depending on P alone.

The key ingredient of the proof is a construction of an odd cover of the plane by translates of P. That is, we establish a family of translates of P covering (almost) every point in the plane a uniformly bounded odd number of times.

Joint work with Rom Pinchasi.

Back

Improved bounds on the Hadwiger-Debrunner numbers
Chaya Keller, Ben-Gurion University

Abstract: The classical Helly's theorem states that if in a family of compact convex sets in R^d every d+1 members have a non-empty intersection then the whole family has a non-empty intersection. In an attempt to generalize Helly's theorem, in 1957 Hadwiger and Debrunner posed a conjecture that was proved more than 30 years later in a celebrated result of Alon and Kleitman: For any p,q (p >= q > d) there exists a constant C=C(p,q,d) such that the following holds: If in a family of compact convex sets, out of every p members some q intersect, then the whole family can be pierced with C points. Hadwiger and Debrunner themselves showed that if q is very close to p, then C=p-q+1 suffices. The proof of Alon and Kleitman yields a huge bound C=O(p^{d^2+d}), and providing sharp upper bounds on the minimal possible C remains a wide open problem.

In this talk we show an improvement of the best known bound on C for all pairs (p,q). In particular, for a wide range of values of q, we reduce C all the way to the almost optimal bound p-q+1<=C<=p-q+2. This is the first near tight estimate of C since the 1957 Hadwiger-Debrunner theorem.

Joint work with Shakhar Smorodinsky and Gabor Tardos.

Back

One-sided epsilon-approximants
Gabriel Nivasch, Ariel University

Abstract: We introduce the notion of "one-sided epsilon-approximants", which is in strength between epsilon-nets and usual (two-sided) epsilon-approximants. Given an n-point set P in R^d, a one-sided epsilon-approximant for P (with respect to convex sets) is a multiset A such that, for every convex set C, we have |P cap C|/|P| - |A cap C|/|A| <= epsilon.

We show that, in contrast with the usual epsilon-approximants, every P has a one-sided epsilon-approximant with respect to convex sets of size g(eps, d) for some g, but independent of n.

Unfortunately, due to the use of a geometric Ramsey theorem, our bound is very weak: g(eps, d) <= 2^2^...^2^(1/epsilon)^c, with d-1 2's.

For more info, see arXiv:1603.05717

Joint work with Boris Bukh.

Back

TBA
Robert Shwartz, Ariel University

Abstract: TBA

Back