Umeå University's logo

umu.sePublications
Change search
Link to record
Permanent link

Direct link
Jäger, Gerold
Publications (10 of 61) Show all publications
Jäger, G., Öhman, L.-D., Markström, K. & Shcherbak, D. (2024). Enumeration of sets of mutually orthogonal latin rectangles. The Electronic Journal of Combinatorics, 31(1), Article ID #P1.53.
Open this publication in new window or tab >>Enumeration of sets of mutually orthogonal latin rectangles
2024 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 31, no 1, article id #P1.53Article in journal (Refereed) Published
Abstract [en]

We study sets of mutually orthogonal Latin rectangles (MOLR), and a natural variation of the concept of self-orthogonal Latin squares which is applicable on larger sets of mutually orthogonal Latin squares and MOLR, namely that each Latin rectangle in a set of MOLR is isotopic to each other rectangle in the set. We call such a set of MOLR co-isotopic. In the course of doing this, we perform a complete enumeration of sets of t mutually orthogonal k × n Latin rectangles for k ≤ n ≤ 7, for all t < n up to isotopism, and up to paratopism. Additionally, for larger n we enumerate co-isotopic sets of MOLR, as well as sets of MOLR where the autotopism group acts transitively on the rectangles, and we call such sets of MOLR transitive. We build the sets of MOLR row by row, and in this process we also keep track of which of the MOLR are co-isotopic and/or transitive in each step of the construction process. We use the prefix stepwise to refer to sets of MOLR with this property at each step of their construction. Sets of MOLR are connected to other discrete objects, notably finite geometries and certain regular hypergraphs. Here we observe that all projective planes of order at most 9 except the Hughes plane can be constructed from a stepwise transitive MOLR.

Place, publisher, year, edition, pages
Australian National University Press, 2024
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-222588 (URN)10.37236/9049 (DOI)001183448100001 ()2-s2.0-85187699389 (Scopus ID)
Funder
eSSENCE - An eScience CollaborationSwedish Research Council, 2014-4897
Available from: 2024-04-08 Created: 2024-04-08 Last updated: 2024-04-08Bibliographically approved
Jäger, G. & Drewes, F. (2024). Optimal strategies for the static black-peg AB game with two and three pegs. Discrete Mathematics, Algorithms and Applications (DMAA), 16(4), Article ID 2350049.
Open this publication in new window or tab >>Optimal strategies for the static black-peg AB game with two and three pegs
2024 (English)In: Discrete Mathematics, Algorithms and Applications (DMAA), ISSN 1793-8309, E-ISSN 1793-8317, Vol. 16, no 4, article id 2350049Article in journal (Refereed) Published
Abstract [en]

The AB Game is a game similar to the popular game Mastermind. We study a version of this game called Static Black-Peg AB Game. It is played by two players, the codemaker and the codebreaker. The codemaker creates a so-called secret by placing a color from a set of c colors on each of p ≤ c pegs, subject to the condition that every color is used at most once. The codebreaker tries to determine the secret by asking questions, where all questions are given at once and each question is a possible secret. As an answer the codemaker reveals the number of correctly placed colors for each of the questions. After that, the codebreaker only has one more try to determine the secret and thus to win the game. 

For given p and c, our goal is to find the smallest number k of questions the codebreaker needs to win, regardless of the secret, and the corresponding list of questions, called a (k + 1)-strategy. We present a (⌈4c/3⌉ − 1)-strategy for p = 2 for all c ≥ 2, and a ⌊(3c − 1)/2⌋-strategy for p = 3 for all c ≥ 4 and show the optimality of both strategies, i.e., we prove that no (k + 1)-strategy for a smaller k exists. 

Place, publisher, year, edition, pages
World Scientific, 2024
Keywords
Game theory, mastermind, AB game, optimal strategy
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-210346 (URN)10.1142/s1793830923500490 (DOI)001034748600002 ()2-s2.0-85165934499 (Scopus ID)
Funder
The Kempe Foundations, JCK-2022.1
Available from: 2023-06-20 Created: 2023-06-20 Last updated: 2024-06-26Bibliographically approved
Ghanbari, N., Jäger, G. & Lehtilä, T. (2024). Super domination: graph classes, products and enumeration. Discrete Applied Mathematics, 349, 8-24
Open this publication in new window or tab >>Super domination: graph classes, products and enumeration
2024 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 349, p. 8-24Article in journal (Refereed) Published
Abstract [en]

The dominating set problem (DSP) is one of the most famous problems in combinatorial optimization. It is defined as follows. For a given graph G=(V,E), a dominating set of G is a subset S⊆V such that every vertex in V∖S is adjacent to at least one vertex in S. Furthermore, the DSP is the problem of finding a minimum-size dominating set and the corresponding minimum size, the domination number of G. In this, work we investigate a variant of the DSP, the super dominating set problem (SDSP), which has attracted much attention during the last years. A dominating set S is called a super dominating set of G, if for every vertex u∈S¯=V∖S, there exists a v∈S such that N(v)∩S¯=N(v)∖S={u}. Analogously, the SDSP is to find a minimum-size super dominating set, and the corresponding minimum size, the super domination number of G. The decision variants of both the DSP and the SDSP have been shown to be NP-hard. In this paper, we present tight bounds for the super domination number of the neighbourhood corona product, r-clique sum, and the Hajós sum of two graphs. Additionally, we present infinite families of graphs attaining our bounds. Finally, we give the exact number of minimum size super dominating sets for some graph classes. In particular, the number of super dominating sets for cycles has quite surprising properties as it varies between values of the set [Formula presented] based on nmod4.

Place, publisher, year, edition, pages
Elsevier, 2024
Keywords
Domination number, Hajós sum, Neighbourhood corona product, r-clique sum, Super dominating set
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-221545 (URN)10.1016/j.dam.2024.01.039 (DOI)2-s2.0-85185397337 (Scopus ID)
Funder
The Research Council of NorwaySwedish Research Council, 2022–04535Academy of Finland, 338797
Available from: 2024-03-13 Created: 2024-03-13 Last updated: 2024-03-13Bibliographically approved
Jäger, G., Markström, K., Shcherbak, D. & Öhman, L.-D. (2023). Small youden rectangles, near youden rectangles, and their connections to other row-column designs. Discrete Mathematics & Theoretical Computer Science, 25(1), Article ID 9.
Open this publication in new window or tab >>Small youden rectangles, near youden rectangles, and their connections to other row-column designs
2023 (English)In: Discrete Mathematics & Theoretical Computer Science, ISSN 1462-7264, E-ISSN 1365-8050, Vol. 25, no 1, article id 9Article in journal (Refereed) Published
Abstract [en]

In this paper we first study k × n Youden rectangles of small orders. We have enumerated all Youden rectangles for a range of small parameter values, excluding the almost square cases where k = n − 1, in a large scale computer search. In particular, we verify the previous counts for (n, k) = (7, 3), (7, 4), and extend this to the cases (11, 5), (11, 6), (13, 4) and (21, 5). For small parameter values where no Youden rectangles exist, we also enumerate rectangles where the number of symbols common to two columns is always one of two possible values, differing by 1, which we call near Youden rectangles. For all the designs we generate, we calculate the order of the autotopism group and investigate to which degree a certain transformation can yield other row-column designs, namely double arrays, triple arrays and sesqui arrays. Finally, we also investigate certain Latin rectangles with three possible pairwise intersection sizes for the columns and demonstrate that these can give rise to triple and sesqui arrays which cannot be obtained from Youden rectangles, using the transformation mentioned above.

Place, publisher, year, edition, pages
Centre pour la Communication Scientifique Directe (CCSD), 2023
Keywords
block designs, row-column designs, Youden squares
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-206792 (URN)10.46298/DMTCS.6754 (DOI)2-s2.0-85152096973 (Scopus ID)
Funder
Swedish Research Council, 2014-4897Swedish National Infrastructure for Computing (SNIC)eSSENCE - An eScience Collaboration
Available from: 2023-04-24 Created: 2023-04-24 Last updated: 2023-08-18Bibliographically approved
Jäger, G. & Turkensteen, M. (2022). Assessing the effect of multiple cost changes using reverse set tolerances. Discrete Applied Mathematics
Open this publication in new window or tab >>Assessing the effect of multiple cost changes using reverse set tolerances
2022 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771Article in journal (Refereed) In press
Abstract [en]

We determine the sensitivity of a current optimal solution to a combinatorial optimization problem to cost changes in a set of elements. In a recent study, the concept of regular set tolerances has been introduced for a combinatorial optimization problem and for three types of cost functions, namely sum, product, and bottleneck. A regular set tolerance is the supremum amount of cost changes that can be distributed in the most favorable way to multiple elements such as not to change the current optimal solution. In this paper, we introduce an alternative concept, namely the reverse set tolerance, which is a measure of the infimum amount of cost changes to multiple elements such that the current optimal solution becomes non-optimal.

We characterize the specific cases in which reverse set upper and lower tolerances have positive values and in which they are infinite. We also show a criterion for the uniqueness of an optimal solution. Furthermore, we present bounds and exact formulas for reverse set upper and lower tolerances using the relation to their corresponding single tolerance counterparts. We discuss the similarities and differences in the results between regular and reverse set tolerances. Finally, we motivate this new concept by analyzing them for special combinatorial optimization problems with important practical applications.

Place, publisher, year, edition, pages
Elsevier, 2022
Keywords
Combinatorial optimization, Reverse set tolerance, Sensitivity analysis, Tolerance
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-201471 (URN)10.1016/j.dam.2022.10.018 (DOI)2-s2.0-85142695036 (Scopus ID)
Available from: 2022-12-06 Created: 2022-12-06 Last updated: 2024-04-26
Turkensteen, M. & Jäger, G. (2022). Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems. Theoretical Computer Science, 937, 1-21
Open this publication in new window or tab >>Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems
2022 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 937, p. 1-21Article in journal (Refereed) Published
Abstract [en]

This paper considers combinatorial optimization problems with an objective of type bottleneck, so the objective is to minimize the maximum cost among all elements in a feasible solution. For these problems, the sensitivity of an optimal solution to changes in parameters has received much less attention in existing studies than the computation of an optimal solution. This paper introduces methods for computing upper and lower tolerances which measure the amount of cost change needed in an element inside and outside an optimal solution, respectively, before that solution becomes non-optimal. Our main contribution is the development of efficient computation methods for bottleneck versions of the Linear Assignment Problem and the Minimum Spanning Tree Problem.

Place, publisher, year, edition, pages
Elsevier, 2022
Keywords
Bottleneck objective, Bottleneck Spanning Tree Problem, Combinatorial optimization, Linear Bottleneck Assignment Problem, Sensitivity analysis
National Category
Discrete Mathematics Probability Theory and Statistics
Identifiers
urn:nbn:se:umu:diva-200411 (URN)10.1016/j.tcs.2022.09.026 (DOI)000894223300001 ()2-s2.0-85139352141 (Scopus ID)
Available from: 2022-10-20 Created: 2022-10-20 Last updated: 2023-09-05Bibliographically approved
Glazik, C., Jäger, G., Schiemann, J. & Srivastav, A. (2021). Bounds for the Static Permutation Mastermind game. Discrete Mathematics, 344(3), Article ID 112253.
Open this publication in new window or tab >>Bounds for the Static Permutation Mastermind game
2021 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 344, no 3, article id 112253Article in journal (Refereed) Published
Abstract [en]

In this paper' we introduce a variant of Mastermind, which we call Static Permutation Mastermind and which is defined as follows. One player creates a secret code, called secret, consisting of n colors on n pegs, where each color is used exactly once. The second player tries to determine the secret with as few questions as possible, where each question is a possible secret and all questions are asked at once. After having asked all questions, he receives for each question the number of correctly placed colors and has one more try to determine the secret. The main result of this paper is an upper bound of O(n1.525) questions. It is proved by a distinction of pairs of possible secrets with low and high Hamming distance. For pairs with a low Hamming distance we construct questions using certain arithmetic progressions. For pairs with a high Hamming distance we estimate the size of a vertex cover in a suitable hypergraph. With a slight modification of the arguments of Doerr et al. (2016) we also give a lower bound of Ω(nlogn).

Place, publisher, year, edition, pages
Elsevier, 2021
Keywords
Static Permutation Mastermind, Game theory, Graph theory, Vertex cover
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-180197 (URN)10.1016/j.disc.2020.112253 (DOI)000608703700004 ()2-s2.0-85098170441 (Scopus ID)
Available from: 2021-02-22 Created: 2021-02-22 Last updated: 2021-02-22Bibliographically approved
Jäger, G. & Drewes, F. (2020). The Metric Dimension of Z(n) x Z(n) x Z(n) is [3n/2]. Theoretical Computer Science, 806, 344-362
Open this publication in new window or tab >>The Metric Dimension of Z(n) x Z(n) x Z(n) is [3n/2]
2020 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 806, p. 78p. 344-362Article in journal (Refereed) Published
Abstract [en]

In this work we determine the metric dimension of Zn × Zn × Zn as ⌊3n/2⌋ for all n ≥ 2. We prove this result by investigating a variant of Mastermind.

Mastermind is a famous two-player game that has attracted much attention in the literature in recent years. In particular we consider the static (also called non-adaptive) black-peg variant of Mastermind. The game is played by a codemaker and a codebreaker. Given c colors and p pegs, the principal rule is that the codemaker has to choose a secret by assigning colors to the pegs, i.e., the secret is a p-tuple of colors, and the codebreaker asks a number of questions all at once. Like the secret, a question is a p-tuple of colors chosen from the c available colors. The codemaker then answers all of those questions by telling the codebreaker how many pegs in each question are correctly colored. The goal is to find the minimal number of questions that allows the codebreaker to determine the secret from the received answers. We present such a strategy for this game for p = 3 pegs and an arbitrary number c ≥ 2 of colors using ⌊3c/2⌋ + 1 questions, which we prove to be both feasible and optimal.

The minimal number of questions required for p pegs and c colors is easily seen to be equal to the metric dimension of Zcp plus 1 which proves our main result.

Place, publisher, year, edition, pages
Elsevier, 2020. p. 78
Keywords
weighted tree automaton, N-best analysis, tropical semiring
National Category
Computer Sciences Discrete Mathematics
Research subject
Computer Science
Identifiers
urn:nbn:se:umu:diva-159286 (URN)10.1016/j.tcs.2019.05.042 (DOI)000510523000025 ()2-s2.0-85068555744 (Scopus ID)
Note

Available online 4 July 2019.

Available from: 2019-05-23 Created: 2019-05-23 Last updated: 2023-03-24Bibliographically approved
Jäger, G., Markström, K., Öhman, L.-D. & Shcherbak, D. (2019). Triples of Orthogonal Latin and Youden Rectangles of small order. Journal of combinatorial designs (Print), 27(4), 229-250
Open this publication in new window or tab >>Triples of Orthogonal Latin and Youden Rectangles of small order
2019 (English)In: Journal of combinatorial designs (Print), ISSN 1063-8539, E-ISSN 1520-6610, Vol. 27, no 4, p. 229-250Article in journal (Refereed) Published
Abstract [en]

We have performed a complete enumeration of non-isotopic triples of mutually orthogonal k × n Latin rectangles for k ≤ n ≤ 7. Here we will present a census of such triples, classified by various properties, including the order of the autotopism group of the triple. As part of this we have also achieved the first enumeration of pairwise orthogonal triples of Youden rectangles. We have also studied orthogonal triples of k×8 rectangles which are formed by extending mutually orthogonal triples with non-trivial autotopisms one row at a time, and requiring that the autotopism group is non-trivial in each step. This class includes a triple coming from the projective plane of order 8. Here we find a remarkably symmetrical pair of triples of 4 × 8 rectangles, formed by juxtaposing two   selected copies of complete sets of MOLS of order 4.

National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-158857 (URN)10.1002/jcd.21642 (DOI)000459040800001 ()2-s2.0-85059030594 (PubMedID)
Available from: 2019-05-13 Created: 2019-05-13 Last updated: 2024-07-02Bibliographically approved
Jäger, G. & Drewes, F. (2018). An Optimal Strategy for Static Black-Peg Mastermind with Three Pegs. In: Xiaotie Deng (Ed.), SAGT: International Symposium on Algorithmic Game Theory: 11th International Symposium, SAGT 2018, Beijing, China, September 11-14, 2018, Proceedings. Paper presented at 11th International Symposium on Algorithmic Game Theory, Beijing, China, September 11-14, 2018 (pp. 261-266). Springer, 11059
Open this publication in new window or tab >>An Optimal Strategy for Static Black-Peg Mastermind with Three Pegs
2018 (English)In: SAGT: International Symposium on Algorithmic Game Theory: 11th International Symposium, SAGT 2018, Beijing, China, September 11-14, 2018, Proceedings / [ed] Xiaotie Deng, Springer, 2018, Vol. 11059, p. 261-266Conference paper, Published paper (Refereed)
Abstract [en]

Mastermind is a famous game played by a codebreaker against a codemaker. We investigate its static (also called non-adaptive) black-peg variant. Given c colors and p pegs, the codemaker has to choose a secret, a p-tuple of c colors, and the codebreaker asks a set of questions all at once. Like the secret, a question is a p-tuple of c colors. The codemaker then tells the codebreaker how many pegs in each question are correct in position and color. Then the codebreaker has one final question to find the secret. His aim is to use as few of questions as possible. Our main result is an optimal strategy for the codebreaker for p=3 pegs and an arbitrary number c of colors using ⌊3c/2⌋+1questions.

A reformulation of our result is that the metric dimension of ℤn×ℤn×ℤnis equal to ⌊3n/2⌋.

Place, publisher, year, edition, pages
Springer, 2018
Series
Lecture Notes in Computer Science
Keywords
Mastermind, winning strategy, optimality
National Category
Discrete Mathematics Other Computer and Information Science
Identifiers
urn:nbn:se:umu:diva-151844 (URN)10.1007/978-3-319-99660-8_25 (DOI)2-s2.0-85053255238 (Scopus ID)
Conference
11th International Symposium on Algorithmic Game Theory, Beijing, China, September 11-14, 2018
Available from: 2018-09-13 Created: 2018-09-13 Last updated: 2023-03-23Bibliographically approved
Organisations

Search in DiVA

Show all publications