2023-06316 - Post-Doctoral Research Visit F/M Finite point sets and Intersection Patterns

Contract type : Fixed-term contract

Level of qualifications required : PhD or equivalent

Fonction : Post-Doctoral Research Visit

Context

This position is within the INRIA-KAIST partnership.

The postdoc would be hosted in the associate team FIP between the Gamble project, at INRIA Nancy Grand EST, and the department of mathematical sciences in KAIST. We expect the candidate to spend about 2/3 of her/his time in Nancy and about 1/3 in KAIST.

Context

Every year Inria International Relations Department has a few postdoctoral positions in order to support Inria international collaborations.

This year, postdoctoral positions within the frame of Inria London, Inria Brasil and Inria Chile programs and to strengthen partnerships with Simula (Norway), University of Waterloo (Canada) and KAIST and ETRI (South Korea) are eligible.

The postdoc contract will have a duration of 12 to 24 months. The default start date is November 1st, 2023 and not later than January, 1st 2024. The postdoctoral fellow will be recruited by one of the Inria Centers in France but it is recommended that the time is shared between France and the partner’s country (please note that the postdoctoral fellow has to start his/her contract being in France and that the visits have to respect Inria rules for missions).

Assignment

Candidates for postdoctoral positions are recruited after the end of their Ph.D. or after a first post-doctoral period: for the candidates who obtained their PhD in the Northern hemisphere, the date of the Ph.D. defense shall be later than 1 September 2021; in the Southern hemisphere, later than 1 April 2021.

In order to encourage mobility, the postdoctoral position must take place in a scientific environment that is truly different from the one of the Ph.D. (and, if applicable, from the position held since the Ph.D.); particular attention is thus paid to French or international candidates who obtained their doctorate abroad.

 

Main activities

The postdoc would join the associate team FIP, which works in discrete and computational geometry, more precisely on intersection patterns of geometric set systems and on combinatorial abstractions of finite point sets.

Intersection patterns of geometric set systems. The theory of combinatorial convexity revealed many striking properties of families of convex sets that found surprising applications going far beyond their geometric origins. An established line of research explores generalizations of these properties beyond convexity, and some far-reaching conjectures were made by Kalai and Meshulam regarding a homological analogue of the Vapnik-Chervonenkis dimension from learning theory.

Combinatorial abstractions of finite point sets. Geometric algorithms are often designed over the reals, taking advantage of properties of continuity, closure under arithmetic operations, and geometric figures of Rd , but effectively operate on a combinatorial abstraction of the geometric input, as their courses are determined not by the numerical values given in input, but by the output of the predicate functions. A better understanding of these combinatorial abstractions would allow better design and finer analysis of geometric algorithms, as well as better testing of algorithms or geometric conjectures dealing with finite point sets. This is a classical line of research; an example of a long standing open problem is the tightening of the bounds on the number of halving lines in n-point sets, that is the number of ways in which a line can partition it in two equal-size subset.

The candidate will develop research in the above directions. Here we give some examples of problems that can be investigated but this list is not exhaustive.

  • Intersection patterns of topological set systems with slowly-growing topological complexity. Several classical results from combinatorial convexity were extended to topological set systems with “bounded topological complexity”, see e.g. [GHP21] and the references therein. The conjectures of Kalai and Meshulam that outline a homological Vapnik-Chervonenkis theory predict that many of these results hold for topological set systems whose topological complexity grows polynomially. It would already be a significant step to establish this for topological set systems whose topological complexity grows slowly (say polylogarithmically in the number of sets).

  • Geometric transversals in the intermediate range. Another research direction in combinatorial convexity is to view intersection by points as the special case k = 0 of a k-transversal, that is, a k-dimensional affine flat that intersects every member of a family of convex sets. While much is known for the case k = 0 and k = d − 1, much less can be said for the intermediate range 0 < k < d − 1. In recent years there has been a resurgence of activity in the area with new results [MZ21, Bar21, McG22, McG23] and conjectures [BK21]. We intend to investigate colorful and fractional versions of the recent extension of the Goodman–Pollack–Wenger theorem due to McGinnis. This could potentially yield new insights to the conjecture of Martinez–Roldan–Rubin [MSRPR18].

  • Extremal configurations for halving-lines. The halving set problem from discrete geometry is a classical problem concerning planar point configurations in general position, which has a natural extension to abstract order types. Through the lens of the Edelman-Greene bijection one can reformulate this as an equivalent question regarding standard Young tableaux of staircase shape (see e.g. [Ten12]). We propose to study this connection in more depth and also from the viewpoint of random sorting networks (introduced in [AHRV07]) which have received much attention recently (see e.g. [ADHV19, DV19, Dau21]).

[ADHV19] Omer Angel, Duncan Dauvergne, Alexander E. Holroyd, and Bá lint Virág. The local limit of random sorting networks. Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, 55(1), feb 2019.

[AHRV07] Omer Angel, Alexander E. Holroyd, Dan Romik, and Bálint Virág. Random sorting networks. Advances in Mathematics, 215(2):839–868, 2007.

[Bar21] Imre Barany. Pairwise intersecting convex sets and cylinders in R3 , 2021.

[BK21] Imre Bárány and Gil Kalai. Helly-type problems, 2021.

[Dau21] Duncan Dauvergne. The archimedean limit of random sorting networks. Journal of the American Mathematical Society, nov 2021.

[DV19] Duncan Dauvergne and Bálint Virág. Circular support in random sorting networks. Transactions of the American Mathematical Society, 373(3):1529–1553, nov 2019.

[GHP21] Xavier Goaoc, Andreas F. Holmsen, and Zuzana Patáková. A Stepping-Up Lemma for Topological Set Systems. In 37th International Symposium on Computational Geometry (SoCG 2021), volume 189 of Leibniz International Proceedings in Informatics (LIPIcs), pages 40:1–40:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.

[McG22] Daniel McGinnis. Piercing families of convex sets in the plane that avoid a certain subfamily with lines, 2022.

[McG23] Daniel McGinnis. A necessary and sufficient condition for (2d − 2)-transversals in R2d , 2023.

[MSRPR18] Leonardo Martı́nez-Sandoval, Edgardo Roldán-Pensado, and Natan Rubin. Further consequences of the colorful helly hypothesis, 2018.

[MZ21] Daniel McGinnis and Shira Zerbib. Line transversals in families of connected sets the plane, 2021.

[Ten12] Bridget Eileen Tenner. Repetition in reduced decompositions, 2012.

Skills

We are seeking candidates in the fields of mathematics (discrete geometry or probabilistic/extremal combinatorics) or computer science (computational geometry/topology) with an interest in discrete geometric structures.

Remuneration

2746€ gross/month