top of page

Geometry Seminar Abstracts: Fall 18

Introductory Meeting

Various Speakers

This introductory meeting would not consist of the standard seminar presentation. Instead, some of the participants will introduce themselves and mention the main topics that interest them. You are welcome to either introduce yourself, or just to come listen and have some pastries. If you introduce yourself, you are encouraged to briefly state a major open problem you wish you could solve.

variouspeakers.jpg

Recent Developments on Falconer's Distance Set Problem

Yumeng Ou (Baruch College)

 

 

 

 

 

 

 

 

Given a compact set E in ℝ^d, it determines a distance set Δ(E) that is defined
as the set of all distinct distances generated by points in E. If one wants to make sure
that Δ(E) has positive Lebesgue measure, how large does E itself need to be?
Falconer (1985) conjectured that E should have Hausdorff dimension at least d/2, and the conjecture remains open today for all dimension d≥ 2. I will introduce some classical and modern tools for the study of this problem, especially from the Fourier analytic perspective, and discuss some very recent developments.

yumeng.png

 

 

 

 

 

 

Regular matroids are binary matroids with no minors isomorphic to the Fano matroid or its dual. The Fano matroid is the binary projective plane PG(2, 2). Seymour proved that 3-connected regular matroids are either  graphs, cographs, or a special 10-element matroid R10 called a splitter, or else can be decomposed along a non-minimal exact 3-separation induced by another special matroid R12 called a 3-decomposer. Quasiregular matroids are binary matroids with no minor isomorphic to E4, where E4 is a 10-element rank 5 self-dual binary matroid. The class of quasiregular matroids properly contains the class of regular matroids. In a paper that just appeared in the Electronic Journal of Combinatorics (Vol. 25, Issue 3 (2018)), we decomposed the class of quasiregular matroids in a manner similar to regular matroids by showing that quasiregular matroids are either graphs, cographs, or deletion-minors of PG(3,2), R17 or M12 or else can be decomposed along a non-minimal exact 3-separation induced by R12, P9, or its dual.  The matroid M12 is a splitter and PG(3,2) and R17  are the maximal 3-connected rank 4 and 5 members, respectively.   The class of quasiregular matroids is one of very few excluded minor classes whose members have been described. After Seymour's decomposition of  regular matroids, the Fano dual became the starting point for the analysis of  binary non-graphic and non-cographic matroids. As a consequence of the decomposition of quasiregular matroids the starting point for the analysis of binary non-graphic and non-cographic matroids is E4.

Sandra Kingan (Brooklyn College)

Quasiregular Matroids

Kingan.jpg

Contact Representation of Planar Graphs in 2D and 3D

Stephen Kobourov 
 (University of Arizona)

 

 

 

In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. We show how to use Schnyder realizers and canonical orders for planar graphs to obtain different types of contact representations. Specifically, we describe an algorithm that constructs proportional contact representation for arbitrary planar graphs using 10-sided rectilinear polygons. We also describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity, as 8-sided polygons are sometimes necessary. In 3D vertices are represented by polytopes and edges by contacts between the corresponding polytopes contacts. We show that
planar 3-trees have contact representations with cubes and proportional contact representations with boxes.

kobourov.jpg

 

 

 

In this talk, I will present a general upper bound for the number of incidences with k-dimensional varieties in R^d such that their incidence graph does not contain K_{s,t}. The leading term of this new bound generalizes previous bounds for the special cases of k=1, k=d-1, and k= d/2. Moreover, we find lower bounds showing that this leading term is tight (up to sub-polynomial factors) in various cases. To prove our incidence bounds, we define k/d as the dimension ratio of an incidence problem. This ratio provides an intuitive approach for deriving incidence bounds and isolating the main difficulties in each proof. If time permits, I will mention other incidence bounds with traversal varieties and hyperplanes in complex spaces. This is joint work with Adam Sheffer.

Thao Do (MIT)

A General Incidence Bound in High Dimensions

thao.JPG

Ordinary lines in space

Frank de Zeeuw (Baruch College)

 

 

 

The Sylvester-Gallai theorem states that if a finite set of points in the real plane is not contained in a line, then it spans at least one ordinary line, i.e. a line containing exactly two of the points. In fact, by a result of Green and Tao, any finite point set in the real plane spans a linear number of ordinary lines, and that is best possible because there are point sets on cubic curves that determine only a linear number of ordinary lines.

 

One can consider the same question in three-dimensional space. By projection, the results in the plane hold word-for-word in space, but the known constructions with a linear number of ordinary lines are contained in a plane. I will show that if one assumes that the point set does not have too many points on a plane, then it spans a quadratic number of ordinary lines. More precisely, for any a<1 there is a c>0 such that if we have n points in real space with at most an points on a plane, then there are at least cn^2 ordinary lines. The proof uses projection and Beck’s theorem.

frank.jpg

 

 

 

It is known that there are exactly 8 convex 3-dimensional polyhedra whose faces are equilateral triangles. What about realizations by convex 3-dimensional polyhedra of plane triangulations with faces that are isosceles or equilateral triangles? This talk will look at combinatorial problems related to isosceles/equilateral colorings of triangulations and their geometric realizations by convex polyhedra.

Joseph Malkevitch (York College)

Convex 3-polytopes Whose Faces are Equilateral or Isosceles Triangles

Joe-Malkevitch.jpg

 

 

 

In this talk we discuss a new line of research dealing with the problem to understand which affine constructions and isoperimetric inequalities from flat space R^n allow for generalizations to other spaces of, say, constant curvature (then no longer compatible with affine transformations, but the isometry group of the respective space). The origins of these investigations go back to a paper by F. Gao, D. Hug, and R. Schneider from 2003 who established a counterpart of the famous Blaschke-Santaló inequality in spherical space. In our presentation we will focus on the very recent progress in the generalization of other affine invariants (such as Blaschke's affine surface area or centroid bodies) and their related inequalities. In order to keep the exposition sufficiently succinct, we will restrict our considerations mostly to n-dimensional spherical space, even though some of the results discussed were also treated in hyperbolic space or even more general settings.

Franz Schuster (TU Wien)

"Affine" Isoperimetric Inequalities in Real Space Forms

Schuster.jpg
KarolyBezdek.jpg

 

 

 

Gromov's conjecture (1987) states that if the centers of a family of N congruent balls in E^d is contracted, then the volume of the intersection does not decrease. A uniform contraction is a contraction where all the pairwise distances in the first set of centers are larger than all the pairwise distances in the second set of centers, that is, when the pairwise distances of the two sets are separated by some positive real number. The speaker and M. Naszódi [Discrete Comput. Geom. 60/4 (2018), 967-980] proved Gromov's conjecture for all uniform contractions in E^d, d>1 under the condition that N ≥ (1+\sqrt{2})^d. In this talk, I will improve this result in dimensions 2 and 3 as well as in high dimension.

Károly Bezdek (University of Calgary)

Gromov's Conjecture for Uniform Contractions Revisited

Variants of the Strong Hanani–Tutte Theorem on Surfaces

Radoslav Fulek (IST Austria)

A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The strong Hanani–Tutte theorem states that a graph admitting an independently even drawing in the plane must be planar. We present two extensions of the theorem to higher genus surfaces.

The genus g(G) of a graph G is the minimum g such that G has an embedding on the orientable surface Mg of genus g. The Z2-genus of a graph G, denoted by g0(G), is the minimum g such that G has an independently even drawing on the orientable surface of genus g. Clearly, every graph Gsatisfies g0(G)≤g(G), and the strong Hanani–Tutte theorem states that g0(G)=0 if and only if g(G)=0.

Although there exist graphs G, for which the value of g(G) and g0(G) differ, several recent results suggest that these graph parameters are closely related. We provide further evidence of their similarity. Assuming the validity of an unpublished result by Robertson and Seymour, we show that g(G) can be upper bounded by a function depending only on g0(G). This gives an approximate version of the Hanani–Tutte theorem on orientable surfaces conjectured by Schaefer and Stefankovic in 2013.

The second extension was conjectured by Repovs and A. Skopenkov in 1998 for trees, and by M. Skopenkov in 2003 for general graphs. We show that a possibly degenerate drawing of a tree on a closed surface is approximable by an embedding if and only if it is approximable by an independently even drawing. An analogous claim fails already for certain bad drawings of cycles in the plane. Nevertheless, we extend the result to general graphs by characterizing all such bad drawings.

Joint work with J. Kyncl.

fulek.png

Colorful Phenomena in Discrete Geometry and Combinatorics via Topological Methods

Shira Zerbib (University of Michigan)

 

 

 

We will discuss two new topological theorems and their applications to different problems in discrete geometry and combinatorics involving colorful settings. 

 

The first result is a polytopal-colorful generalization of the topological KKMS theorem due to Shapley. We apply our theorem to prove a new colorful extension of the well-known d-interval theorem of Tardos and Kaiser, as well as to provide a new proof to the colorful Caratheodory theorem of Barany. Our theorem can be also applied to questions regarding fair-division of goods among a set of players. This is a joint work with Florian Frick.

 

The second result is a new topological lemma that is reminiscent of Sperner's lemma: instead of restricting the labels that can appear on each face of the simplex, our lemma considers labelings that enjoy a certain symmetry on the boundary of the simplex. We apply this to prove that the well-known envy-free division theorem of a cake is true even if the players are not assumed to prefer non-empty pieces (that is, without the "hungry players" condition), if the number of players is prime or equal to 4. This is joint with Frederic Meunier.

zerbib.jpg

Dan Halperin (Tel-Aviv University)

 

 

 

The Minkowski sum of two sets P and Q in Euclidean space is the result of adding every point (position vector) in P to every point in Q. Considering the Minkowski sum of two polyhedra with holes (voids), we show that one can always fill up the holes in one of the summand polyhedra and still get the same Minkowski sum as of the original summands. We present a simple proof of this observation, improving on (our) earlier rather involved proof of a more restricted claim. As we explain, this observation helps in speeding up the computation of Minkwoski sums in practice. We also review additional recent results in computing and using Minkowksi sums.

Joint work with Alon Baram, Efi Fogel, Michael Hemmer, and Sebastian Morr.

halperin.jpg

Minkowski Sums of Polyhedra with Holes

Lattice Paths with States, and Counting Geometric Objects via Production Matrices

Günter Rote (FU Berlin)

 

We consider paths in the plane governed by the following rules: (a) There is a finite set of states. (b) For each state q, there is a finite set S(q) of allowable "steps" ((i,j),q'). This means that from any point (x,y) in state q, we can move to (x+i,y+j) in state q'. We want to count the number of paths that go from (0,0) in some starting state q0 to the point (n,0) without going below the x-axis. Under some natural technical conditions, I conjecture that the number of such paths is asymptotic to C^n/sqrt(n^3), and I will show how to compute C.

I will discuss how lattice paths with states can be used to model asymptotic counting problems for some non-crossing geometric structures (such as trees, matchings, triangulations) on certain structured point sets. These problems were recently formulated in terms of so-called production matrices.

This is ongoing joint work with Andrei Asinowski and Alexander Pilz.

Rote.jpg

 

 

 

Erdos conjectured that a set of n points in the Euclidean plane has at least c n/sqrt(log(n))) distinct distances for some universal constant c>0. Guth and Katz nearly resolved this question, but many related problems remain wide open. I will discuss recent results on a variant of this problem for points in a plane over a finite field. This is joint work with Giorgis Petridis.

Ben Lund (Princeton)

Erdos Distinct Distance Problem in Finite Fields

Lund.jpg
bottom of page