GENERAL DESCRIPTION
The thematic session “Combinatorics and Interactions” aims to highlight the growing role of combinatorial methods across diverse areas of mathematics and the sciences. Combinatorics increasingly acts as a bridge between disciplines ranging from algebra, geometry, topology, and probability to theoretical computer science and statistical physics. This session brings together researchers working at these interfaces to present recent developments, explore cross-disciplinary connections, and foster new collaborations built around the combinatorial viewpoint.
SCHEDULE
Thursday, October 8th (Pi i Sunyer)
Friday, October 9th (Nicolau d’Olwer)
17:20h A Combinatorial Characterization of certain Terwilliger Modules and Pseudo-Distance-Regularity, by Blas Fernández (University of Primorska)
ABSTRACTS
Compatible Hamilton cycles in graphs with large minimum degree
by Bertille Granet (University of Warwick)
Abstract
The renowned theorem of Dirac states that if G is a graph with minimum degree at least n/2 then G has a Hamilton cycle. A natural generalisation asks what properties of an edge-colouring of G guarantee the existence of a properly edge-coloured Hamilton cycle in G. This concept can be further generalised as follows: an incompatibility system for G is a set F of `forbidden’ pairs of adjacent edges, that is, $F\subseteq \{\{uv,vw\}\in \binom{E(G)}2\}. A cycle in G is then compatible if no two of its edges form a pair in F.
The system F is called \mu n-bounded if for all v\in V(G) and uv\in E(G), there are at most \mu n pairs \{uv,vw\}\in F.
How small must \mu be to guarantee the existence of a compatible Hamilton cycle in $G$?
Krivelevich, Lee and Sudakov showed that \mu=10^{-16} suffices (for n large), while an example of Bollob\’as and Erd\H{o}s shows that \mu\leq 1/4 is necessary. We significantly reduce this gap for large graphs of minimum degree at least (1/2+\varepsilon)n, by showing that \mu=1/8 suffices but \mu\leq 1/6 is necessary for such graphs. In fact, we give more precise bounds which are functions of \delta(G)/n.
This is joint work with Natalie Behague, Francesco Di Braccio and Allan Lo.
Vertex-colored Turán problems and the low-resolution method
by Ander Lamaison (Public University of Navarre)
Abstract
We introduce a family of Turán problems on graphs, in which the goal is to find a subgraph with a specific vertex coloring, generalizing a class of problems by Bollobás. We show that there exists an algorithm that solves these problems in finite time, exploiting a connection to directed graphs. At the core of this connection is the low-resolution method, which previously found application in the study of the uniform Turán density of hypergraphs. Joint work with Hong Liu.
On almost Gallai colourings in complete graphs
by Letícia Mattos (University of Heidelberg)
Abstract
We introduce a natural extension of Gallai edge-colourings of the complete graph $K_n$, in which rainbow triangles, and more generally rainbow $t$-cliques, are allowed if they are edge-disjoint. In this setting, we are interested in maximising their number. Our main motivation comes from a lemma of Berkowitz concerning bounds on the modulus of the characteristic function of clique counts in random graphs. In the case of triangles (that is, when $t = 3$), our problem can be viewed as a rainbow analogue of the celebrated Ruzsa–Szemerédi problem, which asks for the maximum number of blue triangles in a red-blue edge-colouring of $K_n$, under the condition that all blue triangles are edge-disjoint. Our proof combines various applications of the probabilistic method and a generalisation of the edge-isoperimetric inequality for the hypercube. Based on a joint work with A. Grebennikov and T. Szabó.
Polygonal knots and oriented matroids
by Jorge Ramírez-Alfonsín (University of Montpellier)
Abstract
A polygonal knot is a loop in three-dimensional space formed by a finite union of straight line segments. After giving a gentle brief introduction on oriented matroids, we discuss how to use such combinatorial structure to investigate polygonal knots. In particular, we present a recent result about reconstructing polygonal knots via chirotopes.
Multiparameter counting of numerical semigroups
by Maria Bras-Amorós (Polytechnic University of Catalonia)
Abstract
A numerical semigroup is a cofinite subset of N0 closed under addition. There are three important parameters related to a numerical semigroup: the number of gaps (called genus), the largest gap (called Frobenius number) and the smallest nonzero nongap (called multiplicity).
While there are infinitely many numerical semigroups of each given multiplicity, there is only a finite number of semigroups of each given genus or of each given Frobenius number. There have been many efforts to count numerical semigroups by the genus and by the Frobenius number. It is known that the number of semigroups of each genus grows asymptotically with the genus like the Fibonacci numbers and that the number of semigroups of each Frobenius number grows asymptotically in such a way that each number doubles the previous but one. We will provide a formula for the number of numerical semigroups of each Frobenius number, genus, and multiplicity, under the assumption that the
multiplicity m and the Frobenius number F satisfy m \geq (F +1)/3. It is known that most numerical semigroups satisfy these hypotheses. The formula we present
gives, under the required restriction, a multiparameter exact recursion of the increasing behaviours just mentioned.
We will introduce the unleaved tree of numerical semigroups of a given genus and the Frobenius-leaf-discriminating tree of a given Frobenius number. The first tree is characterized by the fact that its leaves are exactly the semigroups of a given genus, while the second tree is characterized by the fact that its leaves are exactly the semigroups of a given Frobenis number. Hence, the problem of counting becomes a problem of exploring a tree up to its leaves. We will finally present two adaptations of the seeds algorithm to explore both the unleaved tree and the Frobenius-leaf-discriminating tree. For this purpose we adapted the recursive descending algorithm for trimming the tree exactly at
those nodes with no descendants with a given genus, in the first case, or with no descendants with a given Frobenius number, in the second case.
A Combinatorial Characterization of certain Terwilliger Modules and Pseudo-Distance-Regularity
by Blas Fernández (University of Primorska)
Abstract
The Terwilliger algebra of a graph brings together its global adjacency structure and the distance partition induced by a fixed vertex. Among its representations, the unique irreducible module with endpoint 0, called the trivial module, plays a fundamental role. A natural question is when this module is thin.
The answer is closely connected with the theory of pseudo-distance-regularity developed by Fiol, Garriga, and Yebra. In particular, Fiol and Garriga proved that the trivial module is thin if and only if the graph is pseudo-distance-regular around the distinguished vertex. Since pseudo-distance-regularity is defined using a positive eigenvector associated with the spectral radius, this equivalence naturally raises a further question: can these properties be recognized without recourse to spectral data?
In this talk, we present a purely combinatorial characterization. Our approach classifies walks according to how each successive step changes the distance from the fixed vertex: a step may move away from the vertex, remain in the same distance layer, or move towards it. We prove that the trivial module is thin if and only if the numbers of certain walks with prescribed shapes satisfy appropriate proportionality relations within each distance layer. Consequently, both the thinness of the trivial module and, equivalently, pseudo-distance-regularity around a vertex can be characterized entirely by counting walks of specified shapes.
This is joint work with Štefko Miklavič.