Réunion d'hiver SMC 2024

Vancouver/Richmond, 29 novembre - 2 decembre 2024

Interplay between Discrete Geometry, Convexity, and Combinatorics
Org: Károly Bezdek (Department of Mathematics and Statistics, University of Calgary, Canada), Márton Naszódi (Alfréd Rényi Institute of Mathematics, Budapest, Hungary) et Déborah Oliveros (Instituto de Matemáticas Universidad Nacional Autónoma de México)
[PDF]

LEAH WRENN BERMAN, University of Alaska Fairbanks Infinite classes of movable $(n_{4})$ configurations using Poncelet polygons [PDF]

An $(n_{k})$ geometric configuration is a collection of $n$ points and $n$ straight lines, typically in the Euclidean plane, so that every point lies at the intersection of $k$ lines and every line passes through $k$ points. The modern study of configurations began in 1990, when Branko Grünbaum and John Rigby published the first geometric realization of any $(n_{4})$ configuration. In particular, they realized a $(21_{4})$ configuration (previously studied as a combinatorial configuration by Felix Klein) using properties of regular heptagons. It had long been assumed that this configuration is not movable: it is impossible to fix four noncollinear points of the configuration and move a fifth point in such a way that all the other incidences of the configuration are retained. However, this assumption turns out to be false—the $(21_{4})$ Grünbaum-Rigby configuration is movable! Its movability relies on a deep relationship between the construction technique that produces the heptagonal realization, conics, and the structure of Poncelet polygons. Poncelet polygons provide a framework for showing that all trivial celestial configurations, of which the Grünbaum-Rigby configuration is the smallest example, are movable. This is joint work with Gábor Gévay, Jürgen Richter-Gebert, and Serge Tabachnikov.

ANOUK BROSE, University of California, Davis Computing Lattice Diameters of Lattice Polygons [PDF]

Motivated to count the lattice points in the intersection of a lattice polytope with an affine hyperplane, we study the 2-dimensional case, where a hyperplane corresponds to a line. A lattice diameter (for a lattice polytope $P$), is a line whose interesection with P has maximally many lattice points among all lines. We present an algorithm that computes all lattice diameters of a lattice polygon in polynomial time. Further, computing lattice diameters of lattice polytopes P with $dim P > 2$ is NP-hard. This is joint work with J. A De Loera, G. Lopez, and A. Torres.

GYIVAN LOPEZ CAMPOS, National Autonomous University of Mexico (UNAM) 0/1-Borsuk problem on matroids [PDF]

The Borsuk partition problem or better known as the Borsuk Conjecture asks whether for all $S\subset \mathbb{R}^n$ with diameter $d$, there is a partition of $S$ in at most $n+1$ subsets such that the diameter of each subset is less than $d$.

In 1993, the conjecture was proved false by J. Kahn and G. Kalai, with an astonishing finite conterexample, furthermore, the given set was made only by canonical vectors with the same weight. The Borsuk problem restricted to this type of sets is known today as the 0/1-Borsuk problem.

In this talk, we are going to analyze this counterexample and the 0/1-Borsuk problem when the set is the set of vertices of a matroid basis polytope.

SILVIA FERNANDEZ, California State University, Northridge Bounding Sylvester’s four-point constant and the rectilinear crossing number of the complete graph [PDF]

In 1865, Sylvester proposed a series of problems falling into a category he called form-probability. In particular, he asked for the chance of the quadrilateral formed by four points, taken arbitrarily within any assigned boundary, being convex. The infimum of these probabilities over all boundaries (open sets in the plane with finite Lebesgue measure) is known as Sylvester’s four-point constant. The rectilinear crossing number of the complete graph on n vertices is the minimum number of edge-crossings over all drawings of this graph in the plane, where the vertices are in general position and the edges are straight line segments. In 1994, Scheinerman and Wilf proved a close relationship between Sylvester’s four-point constant and the rectilinear crossing number of the complete graph. In this talk, we present the best known bounds for this crossing number, which in turn provide bounds on Sylvester’s four-point constant. We focus on the structure of crossing optimal configurations and in particular on exact results for symmetric drawings.

FEDERICO FIROOZI, University of Calgary Counting lattice paths with respect to a linear boundary of rational slope [PDF]

There is a remarkable and well-known enumeration result regarding lattice paths with unit up and right steps: the number of paths from $(0,0)$ to $(g,g)$ that contain $2k$ steps above the line $y=x$ does not depend on the integer $k$. This result --- called the Chung-Feller theorem --- has inspired numerous authors to search for similar patterns throughout the years. In this accessible talk, we discuss some of our recent findings regarding paths that end at $(ga,gb)$ and respect the boundary line given by $y=\frac ba x$ for coprime integers $a,b$; these findings include a result similar to the Chung-Feller theorem and an enumeration formula that generalizes counts conducted by previous authors Grossman and Bizley. In addition to discussing these results, we explain (at a high level) the combinatorial methods we used to obtain them and reveal a connection between our formula and the study of symmetric functions.

This is joint work with Jonathan Jedwab and Amarpreet Rattan.

FERENC FODOR, University of Szeged, Hungary Stability of mean width inequalities [PDF]

It was proved by Barthe, Schechtman and Schmuckenschl\"ager that among origin-symmetric convex bodies, whose John ellipsoid is the unit ball, the cube has maximal mean width, and that the regular cross-polytope minimizes the mean with among origin-symmetric convex bodies whose Löwner ellipsoid is the unit ball. We prove stronger, stability forms of these inequalities that are close to optimal. This is joint work with K.J. B\"or\"oczky (Budapest, Hungary) and D. Hug (Karlsruhe, Germany).

ALEXEY GARBER, The University of Texas Rio Grande Valley On spheres with $k$ points inside [PDF]

A classical result of Delone claims that for a finite and generic point set $A$ in $\mathbb R^d$, every generic point in the convex hull of $A$ belongs to exactly one simplex with empty circumsphere. The collection of all these simplices is called the Delaunay triangulation of $A$. In the talk I will discuss a generalization of Delaunay’s result to the case of simplices with $k$ points inside their circumspheres. I will also talk about possible extensions to the case of weighted points sets and point sets in $\mathbb S^d$, and sketch a new geometric proof for the fact that volumes of hypersimplices are Eulerian numbers. The talk is based on a joint work with Herbert Edelsbrunner and Morteza Saghafian.

ALEXEY GLAZYRIN, The University of Texas Rio Grande Valley Illuminating constant width bodies [PDF]

Recently, Arman, Bondarenko, and Prymak constructed a constant width body in $\mathbb{R}^n$ whose illumination number is exponential in $n$. In this talk, I will show how to improve their bound by generalizing the construction. In particular, I will explain how to find a constant width body in $\mathbb{R}^n$ whose illumination number is at least $(1.047+o(1))^n$.

ANTONIO TORRES HERNANDEZ, UC Davis Counting Vertices on Hyperplane Slices of Polytopes [PDF]

The study of slicing convex sets, especially polytopes, has been an active area of research in geometry and combinatorics, inspiring numerous investigations. In this talk, we will focus on the number of vertices in slices of polytopes. We will define the sequences of slices for a polytope and analyze the gaps within these sequences, providing new insights into their structure and properties.

ILLYA IVANOV, University of Calgary Counting $C$-polyhedra facets [PDF]

A translative (resp. homothetic) $C$-polyhedron $P \subset \mathbb{E}^d$ is an intersection of translates (resp. homothets) $C_1, C_2, \ldots C_n$ of a convex body $C \subset \mathbb{E}^d$; the intersection is reduced and has an interior. If $F' \subset P \cap \text{bd} C_i $ is connected, singularity-free and isn't a part of a larger connected singularity-free subset of $P \cap \text{bd} C_i$, then $F = \text{cl} F'$ is a facet of $P$ contributed by $C_i$. I will talk about our joint work with Cameron Strachan, estimating number of facets for $C$-polygons in $\mathbb{E}^{2}$. I will also show that when $C \subset \mathbb{E}^d$ is a Euclidean ball, every translate $C_i$ contributes exactly one facet to a translative $C$-polyhedron.

ZSOLT LÁNGI, Budapest University of Technology and Economics Steiner symmetrization on the sphere [PDF]

Steiner symmetrization is an important tool to solve geometric extremum problems in Euclidean space. The aim of this talk is to introduce a generalization of Steiner symmetrization in Euclidean space for spherical space, which is the dual of the Steiner symmetrization in hyperbolic space introduced by Peyerimhoff in 2002. We show that this symmetrization preserves volume in every dimension, and investigate when it preserves convexity. In addition, we examine the monotonicity properties of the perimeter and diameter of a set under this process, and find conditions under which the image of a spherically convex disk under a suitable sequence of Steiner symmetrizations converges to a spherical cap. We talk about applications of our method to prove a spherical analogue of a theorem of Sas, and to confirm a conjecture of Besau and Werner about spherical floating bodies for centrally symmetric spherically convex disks. We also describe a spherical variant of a theorem of Winternitz. Joint work with Bushra Basit, Steven Hoehner and Jeff Ledford.

EGON SCHULTE, Northeastern University Skeletal polyhedra, complexes, and their classification by symmetry [PDF]

The study of highly symmetric polyhedral structures in Euclidean 3-space has a long and fascinating history tracing back to the early days of geometry. Much recent work has focused on skeletal polyhedra and complexes, and their classification by symmetry. A skeletal polyhedron is a finite or infinite discrete structure made up of finite or infinite polygons as faces, with two faces on each edge and a circular vertex-figure at each vertex. The faces can be planar or skew, finite polygons, or can be linear, zigzag, or helical, infinite polygons. These skeletal figures exhibit fascinating geometric, combinatorial, and algebraic properties and include many new finite and infinite polyhedral structures. We discuss approaches to the classification for some of the most prominent classes of skeletal figures including the regular, chiral, or uniform polyhedra, as well as regular skeletal complexes with more than two edges meeting at an edge.

TAMON STEPHEN, Simon Fraser University Hypergraph Transversal Pairs Near the Fredman-Khachiyan Bound [PDF]

The Fredman-Khachiyan algorithm generates the transversal of a hypergraph in incremental quasi-polynomial time. It is a recursive algorithm which focuses on the most frequent vertex in terms of the number of edges in either the hypergraph or its transversal. Hypergraphs where this maximum fre- quency is low are therefore of interest. This gives a group of related optimization questions for hypergraph-transversal pairs. Here we present some preliminary extremal results.

Besides using classic combinatorial constructions, we adapt Wagner’s deep reinforcement learning scheme from graphs to hypergraphs to help find some unexpected examples.

This is joint work with Parsa Salimi.

PETER VAN HINTUM, Institute for Advanced Study Discrete Brunn-Minkowski theory [PDF]

The Brunn-Minkowski inequality is a fundamental result in convex geometry asserting that for sets $A,B\subset\mathbb{R}^n$ of the same volume and a parameter $t\in(0,1)$, we have $|tA+(1-t)B|\geq |A|$ with equality iff $A$ and $B$ are essentially the same convex set up to translation. We will explore how the study of discrete sumsets, including e.g. Freiman's theorem, can provide insights into the stability of this continuous Brunn-Minkowski inequality.

GORDON WILLIAMS, University of Alaska Fairbanks On Prisms of Polytopes [PDF]

The Tomotope provided the first well understood example of an abstract 4-polytope whose connection (monodromy) group was not a string C-group, and which also did not have a unique minimal regular cover. Conversely, we know that if the connection group of a polytope is a string C-group (if the polytope is \emph{C-connected}), then the polytope will have a unique minimal regular cover. Since the discovery of the Tomotope, an active area of investigation has been determining which abstract d-polytopes are C-connected and the ways various constructions for abstract polytopes result in polytopes that do or do not possess unique minimal regular covers. In this talk we'll discuss recent work showing that the prism over every abstract polyhedron is C-connected, or equivalently, that it has a unique minimal regular cover. We will also describe a conjecture positing a general condition on the C-connectedness of prisms over polytopes that is independent of rank.

haut de la page