Publications

Please submit all program related publications via this form.
Showing entries 110 of 11 total entries.

Please acknowledge the support of the SPP in your publications with one of the following phrases:

was supported by the SPP 2458 "Combinatorial Synergies", funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – project number(s)

or simply

funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – project number(s)

If multiple projects are involved in your publication, list all of the relevant project numbers, separated by commas.

01/10/2025
Central limit theorems for the nearest neighbour embracing graph in Euclidean and hyperbolic space [ preprint | publication ]
by Holger Sambale, Christoph Thäle, Tara Trauthwein

Consider a stationary Poisson process \(\eta\) in the d-dimensional Euclidean or hyperbolic space and construct a random graph with vertex set \(\eta\) as follows. First, each point \(x\in\eta\) is connected by an edge to its nearest neighbour, then to its second nearest neighbour and so on, until \(x\) is contained in the convex hull of the points already connected to . The resulting random graph is the so-called nearest neighbour embracing graph. The main result of this paper is a quantitative description of the Gaussian fluctuations of geometric functionals associated with the nearest neighbour embracing graph. More precisely, the total edge length, more general length-power functionals and the number of vertices with given outdegree are considered.

26/08/2025
Symmetric SAGE and SONC forms, exactness and quantitative gaps [ publication ]
by Philippe Moustrou, Cordian Riener, Thorsten Theobald, Hugues Verdure

The classes of sums of arithmetic-geometric exponentials (SAGE) and of sums of nonnegative circuit polynomials (SONC) provide nonnegativity certificates which are based on the inequality of the arithmetic and geometric means. We study the cones of symmetric SAGE and SONC forms and their relations to the underlying symmetric nonnegative cone. As main results, we provide several symmetric cases where the SAGE or SONC property coincides with nonnegativity and we present quantitative results on the differences in various situations. The results rely on characterizations of the zeroes and the minimizers for symmetric SAGE and SONC forms, which we develop. Finally, we also study symmetric monomial mean inequalities and apply SONC certificates to establish a generalized version of Muirhead's inequality.

20/08/2025
A PC Algorithm for Max-Linear Bayesian Networks [ preprint ]
by Carlos Améndola, Benjamin Hollering, Francesco Nowell

Max-linear Bayesian networks (MLBNs) are a relatively recent class of structural equation models which arise when the random variables involved have heavy-tailed distributions. Unlike most directed graphical models, MLBNs are typically not faithful to d-separation and thus classical causal discovery algorithms such as the PC algorithm or greedy equivalence search can not be used to accurately recover the true graph structure. In this paper, we begin the study of constraint-based discovery algorithms for MLBNs given an oracle for testing conditional independence in the true, unknown graph. We show that if the oracle is given by the ∗-separation criteria in the true graph, then the PC algorithm remains consistent despite the presence of additional CI statements implied by ∗-separation. We also introduce a new causal discovery algorithm named "PCstar" which assumes faithfulness to C∗-separation and is able to orient additional edges which cannot be oriented with only d- or ∗-separation.

05/08/2025
Graph Curve Matroids [ preprint ]
by Geiger, Alheydis; Kühn, Kevin; Vlad, Raluca

We introduce a new class of matroids, called graph curve matroids. A graph curve matroid is associated to a graph and defined on the vertices of the graph as a ground set. We prove that these matroids provide a combinatorial description of hyperplane sections of degenerate canonical curves in algebraic geometry. Our focus lies on graphs that are 2-connected and trivalent, which define identically self-dual graph curve matroids, but we also develop generalizations. Finally, we provide an algorithm to compute the graph curve matroid associated to a given graph, as well as an implementation and data of examples that can be used in Macaulay2.---

05/08/2025
Barnette Graphs with Faces up to Size 8 are Hamiltonian [ preprint ]
by Tobias Schnieders

Barnette's conjecture states that every cubic, bipartite, planar and 3-connected graph is Hamiltonian. Goodey verified Barnette's conjecture for all graphs with faces of size up to 6. We substantially strengthen Goodey's result by proving Hamiltonicity for cubic, bipartite, planar and (2-)connected graphs with faces of size up to 8. Parts of the proof are computational, including a distinction of 339.068.624 cases.

27/06/2025
Linear operators preserving volume polynomials [ preprint ]
by Lukas Grund, June Huh, Mateusz Michałek, Hendrik Süß, Botong Wang

Volume polynomials measure the growth of Minkowski sums of convex bodies and of tensor powers of positive line bundles on projective varieties. We show that Aluffi's covolume polynomials are precisely the polynomial differential operators that preserve volume polynomials, reflecting a duality between homology and cohomology. We then present several applications to matroid theory.

07/05/2025
Complete monotonicity of log-functions [ preprint ]
by Rourou Ma, Julian Weigert

In this article we investigate the property of complete monotonicity within a special family Fs of functions in s variables involving logarithms. The main result of this work provides a linear isomorphism between Fs and the space of real multivariate polynomials. This isomorphism identifies the cone of completely monotone functions with the cone of non-negative polynomials. We conclude that the cone of completely monotone functions in Fs is semi-algebraic. This gives a finite time algorithm to decide whether a function in Fs is completely monotone.

23/04/2025
An intersection product for the polytope algebra [ preprint ]
by Thomas Wannerer

We introduce a new multiplication for the polytope algebra, defined via the intersection of polytopes. After establishing the foundational properties of this intersection product, we investigate finite-dimensional subalgebras that arise naturally from this construction. These subalgebras can be regarded as volumetric analogues of the graded Möbius algebra, which appears in the context of the Dowling-Wilson conjecture. We conjecture that they also satisfy the injective hard Lefschetz property and the Hodge-Riemann relations, and we prove these in degree one.

20/03/2025
Quantification of the fourth moment theorem for cyclotomic generating functions [ preprint | publication ]
by Benedikt Rednoß, Christoph Thäle

This paper deals with sequences of random variables \(X_n\) only taking values in \(\{0,\ldots,n\}\). The probability generating functions of such random variables are polynomials of degree \(n\). Under the assumption that the roots of these polynomials are either all real or all lie on the unit circle in the complex plane, a quantitative normal approximation bound for \(X_n\) is established in a unified way. In the real rooted case the result is classical and only involves the variances of \(X_n\), while in the cyclotomic case the fourth cumulants or moments of \(X_n\) appear in addition. The proofs are elementary and based on the Stein--Tikhomirov method.

04/03/2025
The Likelihood Correspondence [ preprint ]
by Thomas Kahle, Hal Schenck, Bernd Sturmfels, Maximilian Wiesmann

An arrangement of hypersurfaces in projective space is SNC if and only if its Euler discriminant is nonzero. We study the critical loci of all Laurent monomials in the equations of the smooth hypersurfaces. These loci form an irreducible variety in the product of two projective spaces, known in algebraic statistics as the likelihood correspondence and in particle physics as the scattering correspondence. We establish an explicit determinantal representation for the bihomogeneous prime ideal of this variety.

Funded by
Coordinated at