Page 624 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 624
COMBINATORICS AND DISCRETE MATHEMATICS
regions and an explicit asymptotic expression for the number of tilings of “thin and long” n-by-
N rectangular regions. As a consequence, we show that the entropy of a random ribbon tiling
of a “thin and long” region is asymptotically log n.
Joint work with Yinsong Chen.
On the structure of maximum matchings in vertex-weighted graphs
Miklós Krész, miklos.kresz@innorenew.eu
InnoRenew CoE, Slovenia
Coauthor: Miklós Bartha
Matching theory is a classical field of Combinatorics, however, despite the well-developed
theory of efficient algorithms and structural results for the unweighted and edge-weighted
cases, the Maximum Vertex-Weighted Matching Problem (MVWMP) has received less atten-
tion. Even though it was observed by T. H. Spencer and E. W. Mayr (Node weighted matching,
in Automata, Languages and Programming ) as early as 1984 that most problems concern-
ing vertex-weighted graphs are closer to their unweighted counterparts than the edge-weighted
ones, only a few specific theoretical problems have been considered since then.
In this talk we will present the most fundamental structure theorems for MVWMP. The
counterpart of the classical Gallai-Edmonds Structure Theorem is worked out for vertex-weight-
ed graphs, first for non-negative assignments, and then for the general case where negative
weights are also allowed. These theorems characterize the structure and composition of max-
imum weight matchings, and also specify the deficiency of such matchings. Building on the
Gallai-Edmonds decomposition, two Berge-type formulas are presented to estimate the defi-
ciency of graphs incurring in one particular weight and also globally at all weights.
1-skeleton of the polytope of pyramidal tours with step-backs
Andrei Nikolaev, andrei.v.nikolaev@gmail.com
P. G. Demidov Yaroslavl State University, Russian Federation
The 1-skeleton of the polytope P is the graph whose vertex set is the vertex set of P and edge
set is the set of 1-dimensional faces of P . We consider the following 3 characteristics of a
1-skeleton: the vertex adjacency, the diameter, and the clique number. The adjacency relation
is the key for the study and analysis of 1-skeleton, as well as the basis for the edge-following
algorithms. While the diameter and the clique number serve as lower bounds on complexity in
some computation models and classes of algorithms (see [1,3], for example).
We consider a classic asymmetric traveling salesperson problem: for a given complete
weighted digraph Kn it is required to find a Hamiltonian cycle of minimum weight. For a
Hamiltonian cycle τ we denote by τ (i) the successor of a vertex i and by τ −1(i) the predecessor
of i. A vertex i, satisfying τ −1(i) < i and τ (i) < i, is called a peak. A step-back peak is the
vertex i, such that
τ −1(i) < i, τ (i) = i − 1, τ 2(i) > i, or τ −2(i) > i, τ −1(i) = i − 1, τ (i) < i.
A proper peak is a peak i which is not a step-back peak. A pyramidal tour with step-backs,
introduced by Enomoto, Oda and Ota [2], is a Hamiltonian cycle with exactly one proper peak
622
regions and an explicit asymptotic expression for the number of tilings of “thin and long” n-by-
N rectangular regions. As a consequence, we show that the entropy of a random ribbon tiling
of a “thin and long” region is asymptotically log n.
Joint work with Yinsong Chen.
On the structure of maximum matchings in vertex-weighted graphs
Miklós Krész, miklos.kresz@innorenew.eu
InnoRenew CoE, Slovenia
Coauthor: Miklós Bartha
Matching theory is a classical field of Combinatorics, however, despite the well-developed
theory of efficient algorithms and structural results for the unweighted and edge-weighted
cases, the Maximum Vertex-Weighted Matching Problem (MVWMP) has received less atten-
tion. Even though it was observed by T. H. Spencer and E. W. Mayr (Node weighted matching,
in Automata, Languages and Programming ) as early as 1984 that most problems concern-
ing vertex-weighted graphs are closer to their unweighted counterparts than the edge-weighted
ones, only a few specific theoretical problems have been considered since then.
In this talk we will present the most fundamental structure theorems for MVWMP. The
counterpart of the classical Gallai-Edmonds Structure Theorem is worked out for vertex-weight-
ed graphs, first for non-negative assignments, and then for the general case where negative
weights are also allowed. These theorems characterize the structure and composition of max-
imum weight matchings, and also specify the deficiency of such matchings. Building on the
Gallai-Edmonds decomposition, two Berge-type formulas are presented to estimate the defi-
ciency of graphs incurring in one particular weight and also globally at all weights.
1-skeleton of the polytope of pyramidal tours with step-backs
Andrei Nikolaev, andrei.v.nikolaev@gmail.com
P. G. Demidov Yaroslavl State University, Russian Federation
The 1-skeleton of the polytope P is the graph whose vertex set is the vertex set of P and edge
set is the set of 1-dimensional faces of P . We consider the following 3 characteristics of a
1-skeleton: the vertex adjacency, the diameter, and the clique number. The adjacency relation
is the key for the study and analysis of 1-skeleton, as well as the basis for the edge-following
algorithms. While the diameter and the clique number serve as lower bounds on complexity in
some computation models and classes of algorithms (see [1,3], for example).
We consider a classic asymmetric traveling salesperson problem: for a given complete
weighted digraph Kn it is required to find a Hamiltonian cycle of minimum weight. For a
Hamiltonian cycle τ we denote by τ (i) the successor of a vertex i and by τ −1(i) the predecessor
of i. A vertex i, satisfying τ −1(i) < i and τ (i) < i, is called a peak. A step-back peak is the
vertex i, such that
τ −1(i) < i, τ (i) = i − 1, τ 2(i) > i, or τ −2(i) > i, τ −1(i) = i − 1, τ (i) < i.
A proper peak is a peak i which is not a step-back peak. A pyramidal tour with step-backs,
introduced by Enomoto, Oda and Ota [2], is a Hamiltonian cycle with exactly one proper peak
622
