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.

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.

Posted in Uncategorized
Leave a comment

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.

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.

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

Posted in Uncategorized
Leave a comment

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.

Posted in Uncategorized
Leave a comment

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

Posted in Uncategorized
Leave a comment

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.

Posted in Uncategorized
Leave a comment

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.

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.

Posted in Uncategorized
Leave a comment

Posted in Uncategorized
Leave a comment

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.

Posted in Uncategorized
Leave a comment

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.

Posted in Uncategorized
Leave a comment

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.

Posted in Uncategorized
Leave a comment