December 18, 2017 (Monday) at 14:00, Adrian Dumitrescu (UWM)
“On the Number of Convex Polygons in a Grid”
Abstract.
It is shown that the maximum number of convex polygons in an n×n grid is Θ*(16n).
December 11, 2017 (Monday) at 14:00, Nabil Mustafa (ESIEE Paris)
“Packing in Combinatorial Set Systems”
Abstract.
The concept of packing for geometric objects typically relies on an underlying notion of distance between these objects. A natural way to extend the notion of packing to purely combinatorial set systems is by defining the distance between two sets as the size of their symmetric difference. In a beautiful and conceptually elegant work, Haussler proved tight bounds on packing in set systems of bounded VC dimension. In this talk, I will present a generalization of this theorem and some applications of this generalization.
November 27, 2017 (Monday) at 14:00, Gergely Kiss (University of Luxembourg)
“The discrete Pompeiu problem on the plane”
Abstract.
The discrete Pompeiu problem is stemmed from an integral-geometric question on the plane. The problem is whether we can reconstruct a function if we know the average values of the function on every congruent copy of a given pattern. After introducing the theory of spectral analysis on discrete Abelian groups, I show some results for the discrete version of the problem. One of the arguments is connected to a coloring problem of the plane. One of them is a geometric construction and some others based on some geometric and combinatoric properties of the plane. I also mention some unsolved questions of the topic. My talk is based on a joint work with M. Laczkovich and Cs. Vincze
November 22, 2017 (Wednesday) at 14:00, István Tomon (EPFL)
“Forbidden posets in the Boolean lattice”
Abstract.
The classical theorem of Sperner states that if F is a family of subsets of {1,…,n} such that no element of F is contained in another element of F, then |F|≤ \binom{n}{⎣n/2⎦}. In other words, if a subfamily of the Boolean lattice 2[n] does not contain a chain of size 2, then its size is at most \binom{n}{⎣n/2⎦}.
We are concerned with the following natural extension of this result. Given a partially ordered set P, what is the maximum size of a family F ⊆ 2[n] avoiding P. Depending on how we define “avoid”, we can talk about weak and induced subposet problems. I try to outline the line of research surrounding these problems, and I will talk about one of my recent results on the forbidden induced subposet problem.
November 6, 2017 (Monday) at 14:00, Dániel Korándi (EPFL)
“On the Turán number of ordered forests”
Abstract.
An ordered graph H is a graph with a linear ordering on its vertex set. The corresponding Turán problem, first studied by Pach and Tardos, asks for the maximum number ex<(n,H) of edges in an ordered graph on n vertices that does not contain H as an ordered subgraph. It is known that ex<(n,H) > n1+ε for some positive ε=ε(H) unless H is a forest that has a bipartition V1∪V2 such that V1 totally precedes V2 in the ordering. Making progress towards a conjecture of Pach and Tardos, we prove that ex<(n,H)=n1+o(1) holds for all such forests that are “degenerate” in a certain sense. This class includes every forest for which an n1+o(1) upper bound was previously known, as well as new examples. For example, the class contains all forests with |V1|≤3. Our proof is based on a density-increment argument.
Joint work with Gábor Tardos, István Tomon and Craig Weidert
October 30, 2017 (Monday) at 15:00, Géza Tóth (Rényi Institute, Budapest)
“The Crossing Lemma for multigraphs”
Abstract.
The crossing number cr(G) of a graph G is the minimum number of crossings over all possible drawings of G on the plane. According to the Crossing Lemma, for any simple graph G with n vertices and e ≥ 4n edges, cr(G) ≥ e3/64n2.
Clearly, this result does not hold for multigraphs (graphs with parallel edges or loops). We find natural conditions that imply the analogue of the Crossing Lemma for multigraphs.
Joint work with János Pach.
October 30, 2017 (Monday) at 14:00, Konrad Swanepoel (LSE, London)
“Few-distance sets in finite-dimensional normed spaces”
Abstract.
In the real d-dimensional space with the maximum norm, there are (k+1)d points between which only k distinct non-zero distances occur, namely the points with coordinates from the set {0, 1, …, k}. Does there exist a d-dimensional normed space with a larger k-distance set? (Conjecture: No.) In this talk I give an overview of what is known about this problem.
October 23, 2017 (Monday) at 14:00, Andrey Kupavskii (EPFL)
“Intersecting families”
Abstract.
In the talk we will discuss some classical and new results on intersecting families of k-element subsets of an n-element set. We will present a new proof of the Erdos-Ko-Rado and Hilton-Milner theorems using regular bipartite graphs. Then we will show how this method may be used to prove some general structural results on intersecting families.
October 16, 2017 (Monday) at 14:00, Gábor Tardos (Rényi Institute, Budapest)
“Disjointness graphs of segments”
Abstract.
The disjointness graph G=G(S) of a set of segments S in Euclidean d-space is a graph whose vertex set is S and two vertices are connected by an edge if and only if the corresponding segments are disjoint. We prove that the chromatic number of G is at most ω4+ω3, where ω denotes the clique number of G. It follows, that S has at least approximately |S|1/5 pairwise disjoint or pairwise intersecting segments. We prove stronger bounds for lines in space, instead of segments.
Our results extends a similar classical result of Larman et al. for the disjointness graph of segments (or convex sets) in the plane. The famous result of Pawlik et al. states that bounding the chromatic number in terms of the clique number (or even for triangle free graphs) is not possible for the intersection graph of segments in the plane and a recent result of Norin shows the same for the intersection graphs of lines in space.
We also show that the chromatic number of disjointness graphs of relatively simple continuous arcs is the plane is not bounded as a function of their clique number.
The results represent joint work with Janos Pach and Geza Toth.
October 9, 2017 (Monday) at 14:00, Alexandr Polyanskii (MIPT, Moscow)
“Forbidden subgraphs for graphs of bounded spectral radius and equiangular lines”
Abstract.
The spectral radius of a graph is the largest eigenvalue of its adjacency matrix. Let F(λ) be the family of connected graphs of spectral radius ≤λ. F(λ) can be defined by a finite set of forbidden subgraphs for every λ <λ* := √(2 +√5) = 2.058…, whereas F(λ) cannot for every λ ≥ λ*. Recently, Zilin Jiang and the author found that forbidden subgraphs characterization for F(λ) is closely related to the problem of estimating the maximum cardinality of equiangular lines in the n-dimensional Euclidean space Rn — a family of lines through the origin such that the angle between any pair of them is the same. This connection implies several new results about the maximum cardinality of equiangular lines.
October 2, 2017 (Monday) at 14:00, Grigory Ivanov (EPFL)
“The cross-polytope and the cube, their sections and projections”
Abstract.
We will speak about different bounds on the volume of a projection of the n-dimensional cross-polytope and a central section of the n-dimensional cube. There are several results about central sections of the cube. However, the dual problems are still open.
For instance, the celebrated Vaaler theorem asserts that the volume of a k-dimensional central section of the n-cube is greater or equal to the volume of the k-cube. But it is not known whether the volume of a k-dimensional projection of the n-dimensional cross-polytope is less or equal to the volume of the k-dimensional cross-polytope.
We will introduce a linear algebra approach to these problems which allows us to find some optimal bounds for the cross-polytope and the cube at the same time. Also we will discuss current view on the problems and formulate some open questions.
2017. August 11. (Friday) 15:00: Nikita Zhivotovskii (MIPT)
“ Epsilon-nets and Statistical Learning.”
Abstract.
2017. May 4. (Thursday) 16:00: Justin Ward (EPFL)
“Improved Approximation for K-Means in Arbitrary Dimension.”
Abstract.
In the general K-Means problem in which we are given n input points in a Euclidean space and seek to find k “center” points in the space so that the sum of the squared distances of each input point to its nearest center is minimized. While there have been several recent results for the special case in which the Euclidean space has some bounded dimension d, the best known approximation in arbitrary Euclidean spaces has remained (9+\epsilon) since 2002. In this talk I will present a new algorithm that achieves a 6.36-approximation for this problem, as well as an improved 2.64 approximation for the Euclidean k-median problem. The algorithm is based on a new Lagrangian multiplier preserving primal dual approach. This talk is based on joint work with Sara Ahmadian, Ashkan Norouzi-Fard, and Ola Svensson.
2017. Mar. 29. (Wednesday) 14:00: Nabil Mustafa (ESIEE Paris)
“Local Search for Geometry, III: Euclidean problems.”
Abstract.
In this talk I will survey some results and proofs on local-search algorithms for approximating problems (e.g., k-means, variants of k-means) in the special case where the points are in Euclidean space. Here packing arguments, which are unavailable in the previous talk on the general metric case, lead to polynomial time approximation schemes for these problems.
2017. Mar. 22. (Wednesday) 14:00: Nabil Mustafa (ESIEE Paris)
“Local Search for Geometry, II: metric problems.”
Abstract.
In this talk I will survey some results and proofs on local-search algorithms for approximating distance-based problems (e.g., k-median). The analysis for many such problems follows a similar outline, and a quite different one from the local-search analysis for combinatorial optimization problems covered in the first lecture.
2017. Mar. 14. (Tuesday) 11:00: Nabil Mustafa (ESIEE Paris)
“Local Search for Geometry, I: combinatorial problems.”
Abstract.
In this talk I will present some new results on analysis of local-search algorithms for approximating geometric hitting-set and other combinatorial problems in the plane. Joint work with Norbert Bus, Shashwat Garg and Saurabh Ray.
2017. Mar. 8. (Wednesday) 14:00: István Tomon (EPFL)
“Tiling the Boolean lattice with copies of a poset”
Abstract.
Let 2^[n] denote the Boolean lattice of dimension n, that is, the poset (partially ordered set) whose elements are the subsets of {1,…,n}, ordered by inclusion. A well known property of the Boolean lattice is that any given poset P can be embedded into 2^[n] for n sufficiently large. Moreover, 2^[n] contains many copies of P if n is large enough. So a natural question arises: can 2^[n] be partitioned into copies of P?
For such a partition to exist, P must satisfy the following two trivial conditions: the size of P is a power of 2, and P has a unique minimal and maximal element. Settling a conjecture of Lonc from 1991, we show that these conditions are sufficient as well.
Also, we discuss the case when the size of P is not necessarily a power of 2: in this case, we can still “almost” partition 2^[n] into copies of P.
This is joint work with Vytautas Gruslys and Imre Leader.
