16:15 on Tuesday, December 1, 2015 in the coffee room (MA B1 524)
Clement Hongler (EPFL)
11.15 on Monday, November 23, 2015 in the coffee room (MA B1 524)
Gunter Rote (Freie Universität Berlin)
“Minimal dominating sets in trees: counting, enumeration, and extremal results”
Abstract:A tree with $n$ vertices has at most 9*5^{n/13} minimal dominating sets.
The corresponding growth constant lambda = sqrt[13]{95} ~ 1.4194908
is best possible. These results are obtained more or less automatically by computer,
starting from the dynamic-programming recursion for computing the number of minimal dominating sets of a given tree. This recursion defines a bilinear operation on sixtuples, and
the growth constant arises as a kind of “dominant eigenvalue” of
this operation. We also derive an output-sensitive algorithm for listing all minimal dominating sets
with linear set-up time and linear delay between reporting successive solutions.
It is open whether the delay can be reduced to a constant delay,
for an appropriate modification of the problem statement.
10.15 on Tuesday, November 17, 2015 in the coffee room (MA B1 524)
Radoslav Fulek (IST)
“Easy and hard planarity variants”
Abstract: How hard is it to decide if a pair of planar graphs sharing edges can be simultaneously embedded in the plane? This question asked a decade ago by Brass et al. [WADS 2003, Computational Geometry 2007] became arguably the most prominent open problem in the algorithmic theory of graph planarity variants, simply because it turned out that its tractability would imply tractability for a myriad of planarity variants, whose tractability status is unknown.
10.15 on Tuesday, November 10, 2015 in the coffee room (MA B1 524)
Géza Tóth (Rényi Institute, Budapest)
“Saturated 1-planar graphs”
Abstract: A graph is called 1-planar, if it can be drawn in the plane such that each edge is crossed at most once. It is known that the maximum number of edges of a 1-planar graph is $4n-8$. Brandenburg et al. observed a very interesting phenomenon. They noticed that maximal 1-planar graphs (no edge can be added so that it remains 1-planar) can have much fewer edges.
I review the estimates of Brandenburg et al. for the minimum number of edges of a maximal 1-planar graph and give an improvement of the lower bound.
Joint work with Jànos Baràt.
11.15 on Monday, November 9, 2015 in the coffee room (MA B1 524)
Andrey Gavriliuk (Systems Analysis Institute of Russian Academy of Sciences)
“Voronoi’s conjecture and canonical scalings for tilings”
Abstract: Voronoi’s conjecture is a hundred years’ old problem that remains open. Amazingly enough, new results on the topic appeared recently, after decades of silence. The main object for the problem is a parallelotope. It is a convex polytope in a Euclidean space which tiles the space with its translates. The conjecture suggests nice (and efficient) classification for parallelotopes: they are conjectured to be affine images of Dirichlet domains for lattice points.
Voronoi himself suggested a sophisticated method, which he applied to the so-called primive parallelotopes. This method was enhanced with a novel study of canonical scalings. This method provides a nice treatment for local geometry of tilings and have led to new results (in 2005 by Ordine and in 2015 by our group).
We will discuss aapproach for proving Voronoi’s conjecture, the role of canonical scalings, methods for generating local canonical scalings and our recent results dealing with these concepts.
10.15 on Tuesday, November 3, 2015 in the coffee room (MA B1 524)
“A Compact Geometric Structure for Global Illumination‘‘
Nabil Mustafa (Universite Paris-Est)
Abstract: One of the most challenging problems in computer graphics is efficient photo-realistic rendering. One solution is the family of many-lights methods that approximate global illumination by individually computing illumination from a large number of virtual point lights (VPLs) placed on surfaces. To reduce computations one can group the VPLs into a small number of clusters. We use the well-separated pair decomposition of points as a basis for a data structure for pre-computing and compactly storing a set of view independent candidate VPL clusterings showing that a suitable clustering of the VPLs can be efficiently extracted from this data structure. Empirical results indicate that our method outperforms previous state-of-the-art methods. Joint work with Norbert Bus and Venceslas Biri appearing in Eurographics 2015.
No background in computer graphics will be assumed!
10.15 on Tuesday, October 27, 2015 in the coffee room (MA B1 524)
“A discrete geometric version of Hall’s theorem”
Andreas Holmsen (KAIST, EPFL)
Abstract: I will present a recent discrete geometric version of Hall’s marriage theorem based on joint work with Luis Montejano and Leonardo Martinez. Given n finite sets in the d-dimensional space, we give combinatorial conditions under which it is possible to choose n points, one point from each set, in such a way that the selected points are in general position. When the dimension is 1 we recover Hall’s theorem. The combinatorial conditions relate a certain domination parameter in hypergraphs to the homological connectedness of independence complexes.
10.15 on Tuesday, October 20, 2015 in the coffee room (MA B1 524)
“Erdos-Ko-Rado theorem for (-1,0,1)-vectors
Andrey Kupavskii (EPFL)
Abstract: We determine the maximum number of (-1,0,1)-vectors subject to the following condition. All vectors have length n, exactly k of the coordinates are +1 and one is -1, n>2k-1. Moreover, there are no two vectors whose scalar product equals the possible minimum, -2. Thus, this problem may be seen as an extension of the classical Erd\H os-Ko-Rado theorem. We obtain a complete solution for this problem. Rather surprisingly, there is a phase transition in the behaviour of the maximum at n=k^2. The main tools are from extremal set theory and some of them might be of independent interest.
Joint work with Peter Frankl.
10.15 on Tuesday, October 13, 2015 in the coffee room (MA B1 524)
“On VC-dimension, Voronoi diagrams of moving points, density Hales-Jewett phenomena and a problem in sensor networks“
Shakhar Smorodinsky (Ben-Gurion University & EPFL)
Abstract: Think of the following simple fact: Given a set P of n points on the line and a parameter 1 < k < n, one can (TRIVIALLY) select a subset P’ of the given points of size O(k) such that between any two consecutive points of P’ there are at most O(n/k) points of P.
Now lets add a bit of complication: Assume that the points are moving linearly. Each point p is now a linear function and so the location of p at time t is given by p(t) = at+b. Can one still select O(k) of the given points with the above property preserved at all times?
In this talk we consider this problem and show how it relates to the density version of Hales Jewett theorem. We show how to tackle a much more general problem using the theory of VC-dimension. Time permitting we show a nice application to sensor networks.
10.15 on Tuesday, October 6, 2015 in the coffee room (MA B1 524)
“Beyond the Richter-Thomassen conjecture”
Natan Rubin (Ben-Gurion University, Israel)
Abstract: If two closed Jordan curves in the plane have precisely one point in common, then it is called a touching point. All other intersection points are called crossing points. We establish the following Crossing Lemma for closed curves: In any family of n pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, the number of crossing points exceeds the number of touching points by a factor of at least Omega(loglog n)^{1/8}). As a corollary, we prove the following long-standing conjecture of Richter and Thomassen: The total number of intersection points between any n pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, is at least (1-o(1))n^2.
Joint work with Janos Pach and Gabor Tardos.
10.15 on Tuesday, September 29, 2015 in the coffee room (MA B1 524)
“Every finite family of pseudodiscs must contain a small pseudodisc”
Rom Pinchasi (Technion)
Abstract: We show that there exists an absolute constant c<200 such that
in every finite family F of pseduodiscs one can find one disc D with
the following property. Among the members of F that intersect D,
there are at most c pairwise disjoint pseduodiscs. This result has some
nice applications in two and three dimensions.
17:00 on Tuesday, July 14, 2015 in the coffee room (MA B1 524)
”Ordered graphs and Ramsey numbers”
Abstract: An ordered graph is a pair (G,<) where G is a graph and < is a total ordering of its vertices. Recently, an analogue of Ramsey numbers for ordered graphs has been introduced. The ordered Ramsey number OR(G,<) is the minimum number N such that every ordered complete graph with N vertices and with edges colored by two colors contains a monochromatic copy of (G,<).
In this talk, we discuss the effects of different vertex orderings on the ordered Ramsey number of a given graph and compare the ordered and unordered Ramsey numbers. We also mention some new open problems concerning ordered Ramsey numbers.
11:15am on Wednesday, May 27, 2015 in the coffee room (MA B1 524)
Abstract: Let T=(V=V_1 U V_2 U V_3,E) denote a tree whose vertex set V
time algorithm to test if there exists a planar graph G=(V,E’) such that
11:15am on Wednesday May 20, 2015 in the coffee room (MA B1 524)
”Low-diameter decomposition technique”
Nabil Mustafa (Universite Paris-Est)
Abstract: The low-diameter decomposition lemma states broadly that a set of n points in a metric space can be partitioned into smaller-diameter subsets such that for every pair of points p, q, the probability of the edge pq crossing the cut is proportional to d(p,q)*log n. I will present an elegant proof of this, together with some applications.
Abstract: Given a set N of n points in d-dimensional Euclidean space, we consider
Steiner minimal trees, which are shortest trees that interconnects the set
N, where we allow the trees to have additional vertices. It is well known
that these additional vertices, called Steiner points, have degree 3 and
that the angle between any two edges incident to a Steiner point is
exactly 120 degrees. In the plane, Steiner minimal trees can be
constructed with ruler and compass, but in higher dimensions this is not
true any more, and exact calculations are in practice replaced by
numerical approximations. Rubinstein, Weng and Wormald (2006) studied the
error in the length of epsilon-approximate Steiner trees,which are
approximations in which all angles at Steiner points are within epsilon of
120 degrees. We improve and extend some of their results. This is joint
work with Charl Ras and Doreen Thomas (University of Melbourne).
”Rigidity of graphs and Erdos Geometry”
Abstract: In the talk, I will introduce a new approach for testing the *rigidity* of graphs embedded in the plane, and will demonstrate it by analyzing the rigidity of complete bipartite graphs. A major tool in the analysis is the so-called Elekes-Sharir framework that transforms repeated distances in a planar point set into incidences of lines in three dimensions.
I will then reprove a result of Pach and De Zeeuw (2014), regarding the number of distinct distances determined by points lying on an algebraic curve in the plane, by identifying special bipartite graphs that arise in this context and by exploiting the rigidity of such graphs. This is joint work with Micha Sharir.
The prerequisite will be minimal.
Abstract: We say that a sequence of d-regular graphs is “essentially expander”
if it can be turned into a disjoint union of expanders by removing
and adding o(n) edges. We give a spectral characterization of such
sequences. (Essential) expansion is not testable by randomly sampling
a constant number of vertices and looking at a ball of constant radius
centered at these vertices. Indeed, graphs with large girth may be
essential expanders or very far from essential expanders. Howevert,
there exists local (Benjamin-Schramm) statistics that a sequence
with this statistics is essentially expander, i.e., essential
expansion is locally forceable as showed by the next result: We
solve Bowen’s problem proving that the local (sofic) approximation
of a finitely generated group with Kazhdan Property (T) is essentially
expander. Our results extend to the strongly ergodic case and give a
non-separable(!) ergodic decomposition theorem (for ultraproducts).
We use our characterization to give an alternative construction of non-
hyperfinite 2-dimensional simplicial complexes (in the sense of
Freedman and Hastings). The talk will focus on the graph theoretical
parts, no background will be assumed in group theory and ergodic
theory.
Zsolt
Lángi (Budapest University of Techonlogy)
Abstract: In the 1950s, Rogers and Shephard determined the minimal and maximal
