HUJI math seminars website

Dear All,
Please visit the new calendar website for the math seminars in HUJI at
http://math.huji.ac.il/~dynamics/Huji-seminars.html for updates about the Jerusalem Combinatorics seminar.

 

 

Special Combinatorics seminar on November 19, Horst Martini: Discrete Geometry in Minkowski Spaces

In recent decades, many papers appeared in which typical problems of
Discrete Geometry are investigated, but referring to the more general
setting of finite dimensional real Banach spaces (i.e., to Minkowski
Geometry). In several cases such problems are investigated in the even
more general context of spaces with so-called asymmetric norms (gauges).
In many cases the extension of basic geometric notions, needed for posing these problems in non-Euclidean Banach spaces, is already interesting enough.

Examples of such notions and problems are: circumballs and -centers of
convex sets (e.g., studying Chebyshev sets), corresponding inballs and
-centers, packings and coverings (for instance, Lebesgue’s universal
covering problem), problems from Location Science (like minsum
hyperplanes and minsum hyperspheres), properties of curves and surfaces
in the spirit of Discrete Differential Geometry (e.g., for polyhedral norms),
reduced and complete sets (also for polyhedral norms), applications of notions from Combinatorial Geometry (such as Helly dimension), and generalized theorems from incidence geometry (e.g., theorems of Clifford and Miquel). In this talk, an overview to several such problems and related
needed notions is given.

Time: 12:00–13:00

Location:  B314 Rothberg

November 16, Zuzana Patakova: Multilevel polynomial partitions

The polynomial partitioning method of Guth and Katz partitions a given finite point set P in R^d using the zero set Z(f) of a suitable d-variate polynomial f. Applications of this result are often complicated by the problem, what should be done with the points of P lying within Z(f)? A natural approach is to partition these points with another polynomial and continue further in a similar manner. As a main result, we provide a polynomial partitioning method with up to d polynomials in dimension d, which allows for a complete decomposition of the given point set. The inductive proof is based on the following lemma: Suppose we are given r > 1, a k-dimensional complex variety V in C^d whose all irreducible components have dimension k as well, and a finite set P of n real points contained in V. Under these assumptions we show that there exists a real polynomial f of degree at most O(r^{1/k}) that does not vanish on any of the irreducible components of V and moreover, every connected component of R^d \ Z(f) contains at most n/r points of P.

Joint work with Jirka Matoušek.

November 9, Clara Shikhelman: Many T copies in H-free graphs.

For two graphs T and H and for an integer n, let ex(n,T,H) denote

the maximum possible number of copies of T in an H-free graph on n

vertices. The study of this function when T=K_2 (a single edge) is

the main subject of extremal graph theory. We investigate the general

function, focusing on the cases of triangles, complete graphs and trees.

In this talk the main results will be presented as will sketches of

proofs of some of the following:

(i) ex(n,K_3,C_5) < (1+o(1)) (\sqrt 3)/2 n^{3/2}.

(ii) For any fixed integer m, s > 2m-3 and t >(s-1)!,

ex(n,K_m,K_{s,t})=\Theta(n^{m-m(m-1)/2s}) and

(iii) For any two trees H and T there are two constants c_1 and c_2

for which one has c_1 n^m<ex(n,T,H)< c_2 n^m where m=m(T,H) is an

integer depending on H and T.

The first statement improves (slightly) a result of Bollobas and

Gyori.

Joint work with Noga Alon

November 2, Zur Luria: Random designs and high dimensional expanders

Expander graphs have many wonderful properties, and have been an immensely useful and fruitful area of research in both applicative and theoretical fields. There has been a lot of interest recently in the study of higher dimensional generalizations of expanders to d-uniform hypergraphs. Many competing definitions have been proposed, and different definitions may be appropriate depending on the property of expanders that we wish to preserve.

Designs are a combinatorial object with a long history. They may be viewed as a generalization of regular graphs. Until recently, for all but a small collection of parameters, designs were not known to exist. Amazingly, recent papers by Peter Keevash established the existence of designs for every set of parameters obeying certain necessary conditions, and even proved an asymtotic estimate on their number.

In a joint work with Alexander Lubotzky and Ron Rosenthal, we prove the existence of bounded degree coboundary expanders. Our work makes use of Keevash’s construction: We show that the union of a constant number of designs constructed according to Keevash’s random construction is with high probability a good coboundary expander.

October 26, Roman Glebov: Finitely forcible graphons and permutons

In extremal graph theory, we often consider large graphs that are in
the limit uniquely determined by finitely many densities of their
subgraphs. The corresponding limits (so-called graphons) are called
finitely forcible. Motivated by classical results in extremal
combinatorics as well as by recent developments in the study of
finitely forcible graphons, Lovasz and Szegedy made some conjectures
about the structure of such graphons. In particular, they conjectured
that the topological space of typical points of every finitely
forcible graphon is compact and finitely dimensional.
In this talk we give a brief overview about the corresponding results,
and in particular show that these two conjectures are false.
We will go into more details on one particular example, where a
permuton (limit of permutations) is finitely forcible, but the
corresponding graphon is not.

Joint work with A. Grzesik, T. Klimošová, D. Král’, and J. Volec.

Oct 19, Ron Aharoni: Rainbow independent sets

Given sets of vertices in a graph, an independent transversal is the range of a  partial choice function from the sets, that is independent in the graph. It is also called a “rainbow independent set”. The talk is a survey of principles on this subject, some proved and some as yet only conjectured.

June 22, Alexey Gladkich: The cycle structure of random Mallows permutations

The Mallows model is a probability measure on permutations in S_n in which the probability of a permutation is proportional to q^{inv(pi)}, where inv(pi) denotes the number of inversions in pi and 0<q<1 is a parameter of the model. The model is an example of a class of distributions called spatial random permutations in which the distribution is biased to be close to the identity in a certain underlying geometry. We study the cycle structure of a permutation sampled from the Mallows model. Our main results are that the expected length of the cycle containing a given point is of order min(1/(1-q)^2, n) and in the super-critical regime (i.e., n = o(1/(1-q)^2)) lengths of cycles satisfy Poisson-Dirichlet law.

Joint work with Ron Peled.

June 8, Ehud Friedgut: An information-theoretic proof of Beckner’s inequality

Beckner’s hypercontractive inequality (first proven by Gross and Bonami), was introduced to the theoretical-CS and combinatorics community in the famous KKL paper (1988), and has since  become an extremely useful and important tool in these fields.

The excuse for this talk is a new proof of the inequality, that uses entropy, but the focus will be on the method:

I’ll try my best to sell the information theoretic approach to any audience members who show interest in buying.

June 1, Barak Weiss: Dense forests and Danzer sets

A set in Euclidean space that intersects every convex set of volume 1 is called a Danzer set, and if there is a lower bound on the distance between any two points, it is said to be uniformly discrete. It is not known whether there are sets which are simultaneously Danzer and uniformly discrete. In joint work with Yaar Solomon, we prove that natural candidates, such as uniformly discrete sets that arise from substitutions and from cut-and-project constructions, are not Danzer sets. For cut and project sets our proof relies on the dynamics of homogeneous flows. We also consider dense forests, which are sets satisfying a weakening of the Danzer condition, and we use homogeneous dynamics (in particular Ratner’s theorems on unipotent flows) to construct uniformly discrete dense forests.