# Combinatorics Seminar[ Edit ]

## Moderator: Shira Zerbib Gelaki

*Abstract:*

We consider the following Tur\'an-type problem: given a fixed tournament H, what is the least integer t=t(n,H) so that adding t edges to any n-vertex tournament, results in a digraph containing a copy of H. Similarly, what is the least integer t=t(T_n,H) so that adding t edges to the n-vertex transitive tournament, results in a digraph containing a copy of H. Besides proving several new results on these problems, our main contributions are the following:

1. Pach and Tardos conjectured that if M is an acyclic 0/1 matrix, then any n \times n matrix with n(\log n)^{O(1)} entries equal to 1 contains the pattern M. We prove that this conjecture is equivalent to the assertion that t(T_n,H)=n(\log n)^{O(1)} if and only if H belongs to a certain (natural) family of tournaments.

2. We propose an approach for determining if t(n,H)=n(\log n)^{O(1)}. This approach combines expansion in sparse undirected graphs, together with certain structural characterizations of H-free tournaments. We demonstrate the usefulness of this approach for various H.

Our result opens the door for using structural graph theoretic tools in order to settle the Pach-Tardos conjecture. Joint work with Asaf Shapira.

*Abstract:*

Tiling of the $n$-dimensional Euclidian space, $\mathbb{R}^n$, with a shape $S$ and perfect error-correcting codes are closely related concepts. A $t$-error-correcting code C in a metric space $(V,d)$, where $d:V\times V\rightarrow\mathbb{R}$ is a metric, is a code that can retrieve the transmitted codeword x from the received word y, whenever $d(x,y)\leq t$. A $t$-error-correcting code is called perfect if for every $y\in V$ there exists a codeword $x\in C$ such that $d(x,y)\leq t$. If V is a finite additive group then a perfect $t$-error-correcting code yields a tiling of $\mathbb{R}^n$ with the ball of radius $t$ in $(V,d)$.

Error-correcting codes in general and perfect error-correcting codes in particular are fundamental concepts in coding theory. Their relation to tiling of the $n$-dimensional Euclidian space give rise to many intriguing theoretical problems, of most interest is the existence question of certain tilings.

In this talk I will review some examples of tilings and perfect-error-correcting codes that are of special interest from the perspective of coding theory. I will show exactly the dimensions in which a tiling with a shape called the $(0.5,n)$-cross exists. I will also show a construction of a perfect asymmetric $t$-error correcting code, when the error magnitude is bounded by a parameter $\ell$.

Joint work with Tuvi Etzion, Department of Computer Science, Technion.

*Abstract:*

In the famous KKL (Kahn-Kalai-Linial) paper of 1988 the authors "imported" to combinatorics and theoretical computer science a hypercontractive inequality known as Beckner's ineqaulity (proven first, independently, by Gross and Bonami). This inequality has since become an extremely useful and influential tool, used in tens of papers, in a wide variety of settings. In many cases there are no proofs known that do not use the inequality.

In this talk I'll try to illuminate the information theoretic nature of both the inequality and its dual, touch upon a proof of the dual version from about a decade ago, (joint with V. Rodl), and a fresh (and unrelated) information theoretic proof of the primal version.

No prior knowledge will be assumed regarding discrete Fourier analysis, Entropy, and hypercontractivity.

*Abstract:*

Let F(x,y,z) be a real trivariate polynomial of constant degree,and let A,B,C be three sets of real numbers, each of size n.

How many roots can F have on A x B x C?

This setup arises in many interesting problems in combinatorial geometry, including distinct distances between points on curves, distinct distancesfrom three points, collinear triples of points on curves (the `orchard problem'), unit-area triangles, triple intersection points of families of circles, and more.

This question has been studied by Elekes and R\'onyaiand then by Elekes and Szab\'o about 15 years ago. One of their striking resultsis that, for the special case where F(x,y,z) = z-f(x,y), either F vanishes at quadratically many points of A x B x C, or else f must have one of the special formsf(x,y) = h(p(x)+q(y)) or f(x,y) = h(p(x)q(y)), for univariate polynomials p, q, h.

In this talk I will survey recent progress on this problem, in which theanalysis is greatly simplified, and the bounds become sharp: If F does not have a special form, the number of roots is at most O(n^{11/6}). Moreover, the results also hold over the complex field. This yields significantly improvedbounds for many geometric problems, as listed above.

The proofs use techniques from algebra and algebraic geometry, which are somewhat relatedto the recent growing body of work on algebraic techniques for incidences and distanceproblems, inspired by Guth and Katz's seminal papers.

Joint work with Orit Raz, Jozsef Solymosi, and Frank de Zeeuw (and others).

*Abstract:*

The k-th expansion constant h_k(X) of a simplicial complex X is a natural k-dimensional extension of the Cheeger constant of a graph. Roughly speaking, h_k(X) measures the distance of X from complexes Y that have non-trivial k-cycles.

We will describe this notion and some of its applications.

In particular, we'll discuss:

1) A probabilistic construction of 2-dimensional expanders with bounded edge degree. This involves a concentration inequality on the space of random Latin squares. (joint work with A. Lubotzky).

2) Expansion of building-like complexes (Joint work with A. Lubotzky and S. Mozes).

No prior knowledge will be assumed.