Session 1 |
08:55-09:00 |
Opening:
Emo Welzl |
09:00-09:18 |
Winning fast in biased Maker-Breaker games
Miloš Stojaković, University of Novi Sad
(Gremo May 15, 2002 - Sept 30, 2005)
Abstract:
We take a look at two standard Maker-Breaker games played on the
complete graph - the Perfect Matching game and the Hamiltonicity
game. Our goal is to find out how fast can Maker win the (1:b)
biased game, for values of b for which we know that the game is a
Maker's win.
Joint work with Asaf Ferber, Dan Hefetz and Mirjana
Mikalački.
|
09:18-09:36 |
Compatible connectivity-augmentation of planar disconnected graphs
Luis F. Barba, UL Bruxelles and Carleton University
Abstract:
Motivated by applications to graph morphing, we consider the
following compatible connectivity-augmentation problem: We are
given a labeled n-vertex planar graph G, that has
r>1 connected components, and k>1 isomorphic planar
straight-line drawings G1,...,Gk, of G. We
wish to augment G by adding vertices and edges to make
it connected in such a way that these vertices and edges can be
added to the k drawings G1,...,Gk as points and
straight-line segments, respectively, to obtain k planar
straight-line drawings isomorphic to the augmentation of
G. We show that adding Θ(nr1-1/k) edges and vertices
to G is always sufficient and sometimes necessary to
achieve this goal. The upper bound holds for all
r ∈ {2,...,n} and k>=2. The lower bound holds for all
r ∈ {2,...,n/3} and k>=2.
|
09:36-09:54 |
Solving generalized Laplacian linear systems
Sebastian Stich, UC de Louvain
(Gremo Sep 15, 2010 - Sep 30, 2014)
Abstract:
A Laplacian linear system is an equation of the form Lx = b,
where L describes the Laplacian matrix of a graph G. In 2013,
Kelner et al. presented a simple, combinatorial algorithm to
solve such systems approximately in nearly linear time. Their
algorithm is not only very simple, it was in 2013 also the fastest
algorithm in the unit-cost RAM model.
Motivated by an engineering application, we recently considered
linear systems where L does not describe a graph, but a
higher-dimensional simplicial complex. To some extent, the ideas of
Kelner et al. can still be applied in this setting.
In this talk, I will present the algorithm of Kelner et al. and
its
generalization to higher dimensions, together with some preliminary results.
Joint work with François Glineur, Guoyong Gu, and Yurii
Nesterov.
|
09:54-10:12 |
On tangencies between algebraic curves
József Solymosi, University of British Columbia
(Gremo Jan 1, 2000 - Mar 31, 2001)
Abstract:
This talk is about a recent bound for the number of tangencies amongst
a family of n algebraic curves in the plane. Given a collection
of n bounded degree algebraic curves in R2 or C2, there
are O(n3/2) points where two or more curves are tangent. In
particular, if no three curves are mutually tangent at a common
point, then there are O(n3/2) curve-curve tangencies.
Joint work with Josh Zahl.
|
10:12-10:42 |
Coffee Break |
Session 2 |
10:42-11:00 |
Vertical visibility among parallel polygons in three dimensions
Radoslav Fulek, IST Austria
Abstract:
Let C be a collection of homothetic copies of a convex k-gon P in
the plane with given stacking order. The collection C forms a
visibility clique if, for every pair of copies P1 and P2 in C, the
intersection of P1 and P2 is not covered by the union of the
copies in C appearing between P1 and P2 in the stacking order.
We obtain an upper bound of 22{k \choose 2}+2 on the size of
a visibility clique of homothetic copies of a convex k-gon. In the
case of translates of a regular convex k-gon we improve the bound
to O(k4).
Joint work (in progress) with Radoš Radoičić.
|
11:00-11:18 |
Choosing representatives for moving points
Shakhar Smorodinsky, Ben Gurion University and EPFL
(Gremo Feb 15, 2004 - Oct 31, 2004)
Abstract:
Let P be a set of n moving points in the plane. Namely, the
coordinate of each point is a polynomial (in time) of some
bounded constant degree. We show that for any k, we can choose
a subset N ⊂ P of size O(k log k) such that the Voronoi
cells of the points of N at any time t are balanced in the
following sense: the Voronoi cell of any point of N in the
Voronoi diagram of N at time t contains at most O(n/k)
points of P. This bound is nearly tight even when all the points
are moving with constant speed on the x-axis.
|
11:18-11:36 |
Cartesian products in Erdős geometry
Frank de Zeeuw, EPF Lausanne
Abstract:
A number of interesting problems from combinatorial geometry can
be described in terms of the intersection of an algebraic variety
with a Cartesian product. For instance, by the Schwartz-Zippel
lemma, an algebraic surface F(x,y,z)=0 in R3 intersects a
finite product AxAxA in at most deg(F) |A|2 points, and
this bound is tight. However, if F does not have a certain
special form, one can significantly improve this bound. This is
the Elekes-Szabó theorem, which can provide highly nontrivial
bounds in Erdős-type questions, for example about distances or
collinearity. I will discuss this theorem, a few of its
applications, and some recent variants.
|
11:36-11:54 |
Covering inscribed polytopes by their smaller copies
Márton Naszódi, EPF Lausanne
Abstract:
We can define the illumination number of a convex body in
Euclidean d-space as the minimum number of its positive homothets,
with homothety ratio less than one, that cover the body. The
general problem of establishing the largest illumination
number for a given dimension seems very hard. I am proposing
to consider polytopes all of whose vertices lie on a sphere. The
three-dimensional case is already open, and - I think -
interesting.
|
11:54-12:12 |
Constructing plane graphs in simple topological graphs
Andres Ruiz-Vargas, EPF Lausanne
Abstract:
We show a simple way to construct plane subgraphs of minimum
degree two in simple topological graphs.
|
12:12-12:15 |
Organizational Remarks:
Michael Hoffmann |