Nov 13, 16:10–17:10, In 201

Finitely Forcible Graphons

Roman Glebov (BGU)

Abstract:
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 (socalled 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 joint results with D. Kral, T. Klimosova, and J. Volec, we could
disprove both conjectures.

Nov 20, 16:00–17:00, In 201

Sparse sharp thresholds and hypercontractivity

Noam Lifshitz (Bar Ilan)

The sharp threshold phenomenon is a central topic of research in the analysis of Boolean functions. Here, one aims to give sufficient conditions for a monotone Boolean function f to satisfy\mu_p(f)=o(\mu_q(f)), where q = p + o(p), and \mu_p(f) is the probability that f=1 on an input with independent coordinates, each taking the value 1 with probability p.
The dense regime, where \mu_p(f)=\Theta(1), is somewhat understood due to seminal works by Bourgain, Friedgut, Hatami, and Kalai. On the other hand, the sparse regime where \mu_p(f)=o(1) was out of reach of the available methods. However, the potential power of the sparse regime was suggested by Kahn and Kalai already in 2006.
In this talk we show that if a monotone Boolean function f with \mu_p(f)=o(1) satisfies some mild pseudorandomness conditions then it exhibits a sharp threshold in the interval [p,q], with q = p+o(p). More specifically, our mild pseudorandomness hypothesis is that the pbiased measure of f does not bump up to Θ(1) whenever we restrict f to a subcube of constant codimension, and our conclusion is that we can find q=p+o(p), such that \mu_p(f)=o(\mu_q(f)).

Nov 27, 15:45–16:45, In 201

Almost all string graphs are intersection graphs of plane convex sets

Lena Yuditsky (BGU)

A string graph is the intersection graph of a family of continuous arcs in the plane. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of almost all string graphs on $n$ vertices can be partitioned into five cliques such that some pair of them is not connected by any edge ($n\rightarrow\infty$). As a corollary, we obtain that almost all string graphs on $n$ vertices are intersection graphs of plane convex sets.
This is a joint work with Janos Pach and Bruce Reed.

Dec 4, 15:30–17:00, In 201

Steiner Point Removal with distortion O(log k), using the Relaxed Voronoi algorithm

Arnold Filtser (BGU)

In the Steiner Point Removal (SPR) problem, we are given a weighted graph $G=(V,E)$ and a set of terminals $K\subset V$ of size $k$.
The objective is to find a minor $M$ of $G$ with only the terminals as its vertex set, such that distances between the terminals will be preserved up to a small multiplicative distortion.
Kamma, Krauthgamer and Nguyen [SICOMP2015] devised a ballgrowing algorithm with exponential distributions to show that the distortion is at most $O(\log^5 k)$.
Cheung [SODA2018] improved the analysis of the same algorithm, bounding the distortion by $O(\log^2 k)$.
We devise a novel and simpler algorithm (called the Relaxed Voronoi algorithm) which incurs distortion $O(\log k)$. This algorithm can be implemented in almost linear time ($O(E\log V)$).

Dec 11, 15:45–16:45, In 201

Dense forests and low visibility

Yaar Solomon (BGU)

In this talk we will discuss a type of visibility problem (in Euclidean spaces), with an infinite, discrete, set of obstacles. A dense forest refers to a discrete point set Y that satisfies dist(L,Y)=0 for every ray L in $R^d$, and moreover, the distance between Y and every line segment decays uniformly, as the length of the segments tend to infinity. The constructions of dense forests that are known today were given using tools from Diophantine approximations (Bishop+Peres), homogeneous dynamics (SolomonWeiss), Fourier analysis (Adiceam), the Lovász local lemma (Alon), and more tools form number theory and dynamics (AdiceamSolomonWeiss). We will discuss some of these constructions of dense forests, as well as the speed of which the visibility decays in them.
Some of the results that I will discuss come from a joint work with Faustin Adiceam and with Barak Weiss.

Dec 18

Frankl’s conjecture for dense families.

Ilan Karpas

A union closed family F is a family of sets, so that for any two sets A,B in F,
A$\cup$B is also on F. Frankl conjectured in 1979 that for any unionclosed family F of subsets of [n], there is some element i $\in$ [n] that appears in at least half the members of F.
We prove that the conjecture is true if 
F 
>= 2^{n1}, using tools from boolean analysis. 

Dec 25

Piercing Edges with Subsets in Geometric Hypergraphs

Bruno Jartoux (BGU)


Jan 1

Improved lower and upper bounds on the HadwigerDebrunner numbers

Chaya Keller (Technion)

A family of sets F is said to satisfy the (p,q)property if among any p sets in F, some q have a nonempty intersection. Hadwiger and Debrunner (1957) conjectured that for any p > q > d there exists a constant c = c_d(p,q), such that any family of compact convex sets in R^d that satisfies the (p,q)property, can be pierced by at most c points. Helly’s Theorem is equivalent to the fact that c_d(p,p)=1 (p > d).
In a celebrated result from 1992, Alon and Kleitman proved the conjecture. However, obtaining sharp bounds on the minimal such c_d(p,q), called `the HadwigerDebrunner numbers’, is still a major open problem in combinatorial geometry.
In this talk we present improved upper and lower bounds on the HadwigerDebrunner numbers, the latter using the hypergraph container method.
Based on joint works with Shakhar Smorodinsky and Gabor Tardos.

Jan 8



