Processing math: 100%

BBC+G

Organizers: János Pach, Dömötör Pálvölgyi, Géza Tóth

Budapest Big Combinatorics + Geometry (BBC+G) Seminar is the main seminar in whose organization our group takes active part.

It was initiated in 2020 as the joint seminar of the Geometry Seminar of the Rényi Institute, the GeoScape Research Group and the Combinatorial Geometry (CoGe) Research Group.
Zoom link for the online lectures: https://zoom.us/j/96029300722 and the password is the first 6 terms from the Fibonacci sequence starting with 11.
Recordings of past online talks of the BBC+G Seminar can be watched at the BBC+G video archive.

2024 Spring Semester - every Friday usually at 14:15 in the "Dog Room" of the Rényi Institute

April 4, 2025, 2.15pm (CET)
Ferenc Fodor: TBA

Abstract: TBA


March 28, 2024, 2.15pm (CET)
Gergely Ambrus: TBA

Abstract: TBA


March 21, 2024, 2.15pm (CET)
TBA

Abstract: TBA


March 14, 2024, 2.15pm (CET)
Károly Böröczky: Width and volume in the hyperbolic plane

Abstract: Inspired by the Kakeya problem, Pal showed in 1921 that in the Euclidean plane, the area of a convex domain with given minimal width is minimized by regular triangles. Recently, Pal's theorem has been generalized to the two-sphere, as well. The talk focuses on possible hyperbolic versions of Pal's theorem. In the hyperbolic world, even the notion of width is hard to clarify, and we use a recent natural notion of width due to Lassak. On the one hand, we show that the infimum of the area of convex domains of given Lassak width is zero. On the other hand, we prove that if horo-convex domains are considered (for any two points of a set X, the connecting two horocycle arcs are parts of X), then area is minimized by the "regular horo-triangle", that is bounded by three horocycle arcs. Joint work with Ansgar Freyer and Adam Sagmeister.


March 7, 2024, 2.15pm (CET)
Zsolt Lángi: Normed variants of a theorem of Macbeath

Abstract: A classical theorem of Macbeath states that among convex bodies of unit volume, Euclidean balls are hardest to approximate with an inscribed convex polytope with a fixed number of vertices. In this talk we present normed variants of this problem, and solve some of them. Ongoing joint work with Shanshan Wang.


February 14, 2024, 2.15pm (CET)
Gábor Damásdi: Self-dual polyhedral cones in R4

Abstract: A cone is self-dual if it equals its dual. For example an orthant is self-dual. A less trivial example is the cone of positive semidefinite matrices. Recently João Gouveia and Bruno F. Lourenço studied self-dual polyhedral cones and showed that in R4 the 2-dimensional faces of a self-dual cone must correspond to a 3-connected planar graph which is self-dual in the plane and furthermore this self-duality is strongly involutive. They conjectured that the reverse also holds, that is, for each 3-connected strongly involutive self-dual graph there is a self-dual cone realizing it. We show that the conjecture is true. We also discuss how this result corresponds to characterizations of diameter graphs, touching graphs of circles, ball-polytopes, quadrangulations of the projective plane and generalized thrackles.

2024 Fall Semester - every Friday usually at 14:15 in the "Dog Room" of the Rényi Institute

January 10, 2025, 2.15pm (CET)
Csaba Tóth: Erdős-Szekeres Maker-Breaker Games

Abstract: This talk presents new results on Maker-Breaker games arising from the Erdős-Szekeres problem in planar geometry. This classical problem asks how large a set in general position has to be to ensure the existence of n points that are the vertices of a convex n-gon. Moreover, Erdős further extended this problem by asking what happens if we also require that this n-gon has an empty interior. In a 2-player Maker-Breaker setting, this problem inspires two main games. In both games, Maker tries to obtain an empty convex n-gon, while Breaker tries to prevent her from doing so. The games differ only in which points can comprise the winning n-gons: in the monochromatic version the points of both players can make up an n-gon, while in the bichromatic version only Maker's points contribute to such a polygon. We show that in the monochromatic game, Maker always wins. Even in a biased game where Breaker is allowed to place s points per round, for any constant s1, Maker has a winning strategy. In the bichromatic setting, Maker still wins whenever Breaker is allowed to place at most two points per round. Furthermore, we show that Breaker wins when n=8 and she is allowed to play 12 or more points per round. We also consider the two-round bichromatic game (a.k.a. the offline version). In this setting, we show that Maker wins if she has any advantage in the number of points placed, and we also show that Breaker wins if she can place twice as many points as Maker. (Joint work with Aleksa Džuklevski, Alexey Pokrovskiy, Tomáš Valla and Lander Verlinde.)


December 6, 2024, 2.15pm (CET)
Gábor Damásdi: Characterizing diameter graphs in R^3 using rigidity theory

Abstract: Vázsonyi conjectured that any set of n points in R^3 determines at most 2n-2 diameter pairs. The conjecture was proven independently by Grünbaum, Heppes and Straszewicz using ball polyhedra. Later Swanepoel and Pinchasi gave new proofs using different methods. They showed that any diameter graph can be drawn in the projective plane such that any region has a boundary of even length. Monetjano, Pauli, Raggi, and Roldan-Pensado conjectured that the converse also holds, that is, for any such graph G that there is a point set in R^3 whose diameter graph is isomorphic to G. Whe show that this is indeed true, completing the characterization of diameter graphs in R^3. This result also implies new constructions of Reuleaux polyhedra, ball-polyhedra, Meissner bodies and bodies of constant width. The proof uses ideas from rigidity theory.


November 29, 2024, 2.15pm (CET)
Dániel Simon: Saturated Partial Embeddings of Maximal Planar Graphs

Abstract: In this paper, we study some saturation properties of partial embeddings of maximal planar graphs. A planar graph on vertex set V of size n is maximal if it has 3n6 edges. Let G=(V,E) be a maximal planar graph. For the first problem, suppose H=(V,E) with EE where H is a plane drawing of the graph. We define H is a \emph{labeled plane-saturated subgraph of} G, if no additional edge of E\E can be added to the drawing of H without adding a crossing, and maintaining the same labeling of vertices of H as before. The \emph{labeled plane-saturation ratio of G}, lpsr(G), is the minimum value of e(H)e(G) over all labeled plane-saturated subgraphs H of G. We almost determine the maximum value of lpsr(G) among all maximal planar graphs G. Specifically, we show that lpsr(G)n+863n6 for any such G, and exhibit an example of a graph G with lpsr(G)n+23n6, providing tight upper and lower bounds up to a O(1n) difference. For the second problem, we drop the labeling condition on the vertices of H. A plane graph HG is a \emph{plane-saturated subgraph} of G, if no edge or vertex can be added to H without introducing a crossing, or making H no longer a subgraph of G. The \emph{plane-saturation ratio of G}, psr(G) is defined analogously to lpsr(G) just with plane-saturated subgraphs H of G. We show that there exists a maximal planar graph G with psr(G)32n33n6=12. Joint work with Alexander Clifton.


November 22, 2024
Szeged Geometry Day 2024

November 15, 2024, 2.15pm (CET)
Attila Jung: Quantitative Fractional Helly theorem

Abstract: Two celebrated extensions of Helly's theorem are the Fractional Helly theorem of Katchalski and Liu (1979) and the Quantitative Volume theorem of Bárány, Katchalski, and Pach (1982). Improving on several recent works, we prove an optimal combination of these two results. We show that given a family F of n convex sets in Rd such that at least α(nd+1) of the (d+1)-tuples of F have an intersection of volume at least 1, then one can select Ωd,α(n) members of F whose intersection has volume at least Ωd(1). Joint work with Nóra Frankl and István Tomon.


November 8, 2024, 2.15pm (CET)
Imre Bárány: Same average in every direction

Abstract: Given a polytope P in R3 and a non-zero vector z also in R3, the plane {xR3:zx=t} (where zx is the scalar product of z and x) intersects P in a convex polygon P(z,t) for all t in [t,t+]. Here t=min{zx:xP} and t+=max{zx:xP}. Let A(P,z) denote the average number of vertices of P(z,t) on the interval [t,t+]. It is not hard to see that A(Q,z)=4 for every z in R3 when Q is the unit cube. For what polytopes is A(P,z) a constant independent of z? Joint work with Gabor Domokos.


October 4, 2024, 2.15pm (CET)
Zsolt Lángi: Steiner symmetrization on the sphere

Abstract: 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.


September 27, 2024, 2.15pm (CET)
Ji Zeng: Unbalanced Zarankiewicz problem for bipartite subdivisions

Abstract: A real number σ is called a linear threshold of a bipartite graph H if every bipartite graph G=(UV,E) with unbalanced parts |V||U|σ and without a copy of H must have a linear number of edges |E||V|. We prove that σs=21/s is a linear threshold of the complete bipartite subdivision graph Ks,t. Moreover, we show that any σ<σs is not a linear threshold of Ks,t for sufficiently large t (depending on s and σ). Some applications of our result in incidence geometry are discussed.