Umeå University's logo

umu.sePublications
Change search
Link to record
Permanent link

Direct link
Markström, Klas
Alternative names
Publications (10 of 85) 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
Falgas-Ravry, V., Markström, K. & Räty, E. (2024). Minimum-degree conditions for rainbow triangles. Journal of Graph Theory
Open this publication in new window or tab >>Minimum-degree conditions for rainbow triangles
2024 (English)In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118Article in journal (Refereed) Epub ahead of print
Abstract [en]

Let G:=(G1,G2,G3) be a triple of graphs on a common vertex set V of size n. A rainbow triangle in G is a triple of edges (e1,e2,e3) with ei ∈ Gi for each i and {e1,e2,e3} forming a triangle in V. In this paper we consider the following question: what triples of minimum degree conditions (∂(G1),∂(G2),∂(G3)) guarantee the existence of a rainbow triangle? This may be seen as a minimum degree version of a problem of Aharoni, DeVos, de la Maza, Montejanos and Šámal on density conditions for rainbow triangles, which was recently resolved by the authors. We establish that the extremal behaviour in the minimum degree setting differs strikingly from that seen in the density setting, with discrete jumps as opposed to continuous transitions. Our work leaves a number of natural questions open, which we discuss.

Place, publisher, year, edition, pages
John Wiley & Sons, 2024
Keywords
extremal graph theory, Gallai colourings, Mantel's theorem, min degree, rainbow triangles
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:umu:diva-225265 (URN)10.1002/jgt.23109 (DOI)001223587000001 ()2-s2.0-85192869413 (Scopus ID)
Funder
Swedish Research Council, VR 2021-03687Olle Engkvists stiftelse, 213-0204
Available from: 2024-05-30 Created: 2024-05-30 Last updated: 2024-05-30
Falgas-Ravry, V., Markström, K. & Räty, E. (2024). Rainbow variations on a theme by mantel: extremal problems for Gallai colouring templates. Combinatorica
Open this publication in new window or tab >>Rainbow variations on a theme by mantel: extremal problems for Gallai colouring templates
2024 (English)In: Combinatorica, ISSN 0209-9683, E-ISSN 1439-6912Article in journal (Refereed) Epub ahead of print
Abstract [en]

Let G:=(G1,G2,G3) be a triple of graphs on the same vertex set V of size n. A rainbow triangle in G is a triple of edges (e1,e2,e3) with ei ∈ Gi for each i and {e1,e2,e3} forming a triangle in V. The triples G not containing rainbow triangles, also known as Gallai colouring templates, are a widely studied class of objects in extremal combinatorics. In the present work, we fully determine the set of edge densities (α123) such that if |E(Gi)| >αin2 for each i and n is sufficiently large, then G must contain a rainbow triangle. This resolves a problem raised by Aharoni, DeVos, de la Maza, Montejanos and Šámal, generalises several previous results on extremal Gallai colouring templates, and proves a recent conjecture of Frankl, Győri, He, Lv, Salia, Tompkins, Varga and Zhu.

Place, publisher, year, edition, pages
Springer Nature, 2024
Keywords
05C35, 05D99, Extremal graph theory, Gallai colourings, Mantel’s theorem, Rainbow triangles
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:umu:diva-224095 (URN)10.1007/s00493-024-00102-6 (DOI)001209613600001 ()2-s2.0-85191690527 (Scopus ID)
Funder
Swedish Research Council, 2021-03687Olle Engkvists stiftelse, 213-0204
Available from: 2024-05-16 Created: 2024-05-16 Last updated: 2024-05-16
Leedham-Green, C., Markström, K. & Riis, S. (2024). The largest Condorcet domain on 8 alternatives. Social Choice and Welfare, 62(1), 109-116
Open this publication in new window or tab >>The largest Condorcet domain on 8 alternatives
2024 (English)In: Social Choice and Welfare, ISSN 0176-1714, E-ISSN 1432-217X, Vol. 62, no 1, p. 109-116Article in journal (Refereed) Published
Abstract [en]

In this note, we report on a Condorcet domain of record-breaking size for n = 8 alternatives. We show that there exists a Condorcet domain of size 224 and that this is the largest possible size for 8 alternatives. Our search also shows that this domain is unique up to isomorphism. In this note we investigate properties of the new domain and relate them to various open problems and conjectures.

Place, publisher, year, edition, pages
Springer Science+Business Media B.V., 2024
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-214392 (URN)10.1007/s00355-023-01481-3 (DOI)001118965000001 ()2-s2.0-85170046317 (Scopus ID)
Available from: 2023-09-19 Created: 2023-09-19 Last updated: 2024-05-10Bibliographically approved
Danielsson, J. L. & Markström, K. (2023). Polarised random κ-SAT. Combinatorics, probability & computing, 32(6), 885-899
Open this publication in new window or tab >>Polarised random κ-SAT
2023 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 32, no 6, p. 885-899Article in journal (Refereed) Published
Abstract [en]

In this paper we study a variation of the random κ-SAT problem, called polarised random κ-SAT, which contains both the classical random κ-SAT model and the random version of monotone κ-SAT another well-known NP-complete version of SAT. In this model there is a polarisation parameter p, and in half of the clauses each variable occurs negated with probability p and pure otherwise, while in the other half the probabilities are interchanged. For p = 1/2 we get the classical random κ-SAT model, and at the other extreme we have the fully polarised model where p = 0, or 1. Here there are only two types of clauses: clauses where all κ variables occur pure, and clauses where all κ variables occur negated. That is, for p = 0, and p=1, we get an instance of random monotone κ-SAT. We show that the threshold of satisfiability does not decrease as p moves away from 1/2 and thus that the satisfiability threshold for polarised random κ-SAT with p ≠ 1/2 is an upper bound on the threshold for random κ-SAT. Hence the satisfiability threshold for random monotone κ-SAT is at least as large as for random κ-SAT, and we conjecture that asymptotically, for a fixed κ, the two thresholds coincide.

Place, publisher, year, edition, pages
Cambridge University Press, 2023
Keywords
k-SAT, phase transition, random constraint satisfaction problem, satisfiability
National Category
Computer Sciences Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-212544 (URN)10.1017/S0963548323000226 (DOI)2-s2.0-85165668678 (Scopus ID)
Available from: 2023-08-09 Created: 2023-08-09 Last updated: 2024-01-02Bibliographically approved
Lundow, P.-H. & Markström, K. (2023). Revising the universality class of the four-dimensional Ising model. Nuclear Physics B, 993, Article ID 116256.
Open this publication in new window or tab >>Revising the universality class of the four-dimensional Ising model
2023 (English)In: Nuclear Physics B, ISSN 0550-3213, E-ISSN 1873-1562, Vol. 993, article id 116256Article in journal (Refereed) Published
Abstract [en]

The aim of this paper is to determine the behavior of the specific heat of the 4-dimensional Ising model in a region around the critical temperature, and via that determine if the Ising model and the ϕ4-model belong to the same universality class in dimension 4. In order to do this we have carried out what is currently the largest scale simulations of the 4-dimensional Ising model, extending the lattices size up to L=256 and the number of samples per size by several orders of magnitude compared to earlier works, keeping track of data for both the canonical and microcanonical ensembles. Our conclusion is that the Ising model has a bounded specific heat, while the ϕ4-model is known to have a logarithmic divergence at the critical point. Hence the two models belong to distinct universality classes in dimension 4.

National Category
Other Physics Topics
Identifiers
urn:nbn:se:umu:diva-212073 (URN)10.1016/j.nuclphysb.2023.116256 (DOI)2-s2.0-85163809991 (Scopus ID)
Available from: 2023-07-18 Created: 2023-07-18 Last updated: 2023-07-18Bibliographically 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
Casselgren, C. J., Johansson, P. & Markström, K. (2022). Avoiding and Extending Partial Edge Colorings of Hypercubes. Graphs and Combinatorics, 38(3), Article ID 79.
Open this publication in new window or tab >>Avoiding and Extending Partial Edge Colorings of Hypercubes
2022 (English)In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 38, no 3, article id 79Article in journal (Refereed) Published
Abstract [en]

We consider the problem of extending and avoiding partial edge colorings of hypercubes; that is, given a partial edge coloring φ of the d-dimensional hypercube Qd, we are interested in whether there is a proper d-edge coloring of Qd that agrees with the coloring φ on every edge that is colored under φ; or, similarly, if there is a proper d-edge coloring that disagrees with φ on every edge that is colored under φ. In particular, we prove that for any d≥ 1 , if φ is a partial d-edge coloring of Qd, then φ is avoidable if every color appears on at most d/8 edges and the coloring satisfies a relatively mild structural condition, or φ is proper and every color appears on at most d- 2 edges. We also show that φ is avoidable if d is divisible by 3 and every color class of φ is an induced matching. Moreover, for all 1 ≤ k≤ d, we characterize for which configurations consisting of a partial coloring φ of d- k edges and a partial coloring ψ of k edges, there is an extension of φ that avoids ψ.

Place, publisher, year, edition, pages
Springer, 2022
Keywords
Avoiding edge coloring, Edge coloring, Hypercube, Precoloring extension
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-193790 (URN)10.1007/s00373-022-02485-z (DOI)000777995400001 ()2-s2.0-85127515233 (Scopus ID)
Funder
Swedish Research Council, 2017-05077
Available from: 2022-05-06 Created: 2022-05-06 Last updated: 2023-03-23Bibliographically approved
Lundow, P.-H. & Markström, K. (2022). Efficient computation of permanents, with applications to Boson sampling and random matrices. Journal of Computational Physics, 455, Article ID 110990.
Open this publication in new window or tab >>Efficient computation of permanents, with applications to Boson sampling and random matrices
2022 (English)In: Journal of Computational Physics, ISSN 0021-9991, E-ISSN 1090-2716, Vol. 455, article id 110990Article in journal (Refereed) Published
Abstract [en]

In order to find the outcome probabilities of quantum mechanical systems like the optical networks underlying Boson sampling, it is necessary to be able to compute the permanents of unitary matrices, a computationally hard task. Here we first discuss how to compute the permanent efficiently on a parallel computer, followed by algorithms which provide an exponential speed-up for sparse matrices and linear run times for matrices of limited bandwidth. The parallel algorithm has been implemented in a freely available software package, also available in an efficient serial version. As part of the timing runs for this package we set a new world record for the matrix order on which a permanent has been computed. Next we perform a simulation study of several conjectures regarding the distribution of the permanent for random matrices. Here we focus on permanent anti-concentration conjecture, which has been used to find the classical computational complexity of Boson sampling. We find a good agreement with the basic versions of these conjectures, and based on our data we propose refined versions of some of them. For small systems we also find noticeable deviations from a proposed strengthening of a bound for the number of photons in a Boson sampling system.

Place, publisher, year, edition, pages
Academia Press, 2022
Keywords
Boson sampling, Linear optics, Permanent
National Category
Computer Sciences Probability Theory and Statistics
Identifiers
urn:nbn:se:umu:diva-192500 (URN)10.1016/j.jcp.2022.110990 (DOI)000762463300004 ()2-s2.0-85124124557 (Scopus ID)
Funder
Swedish Research Council, 2014-4897Swedish National Infrastructure for Computing (SNIC)
Available from: 2022-02-24 Created: 2022-02-24 Last updated: 2023-09-05Bibliographically approved
Larsson, J. & Markström, K. (2021). Biased random k-SAT. Random structures & algorithms (Print), 59(2), 238-266
Open this publication in new window or tab >>Biased random k-SAT
2021 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 59, no 2, p. 238-266Article in journal (Refereed) Published
Abstract [en]

The basic random k‐SAT problem is: given a set of n Boolean variables, and m clauses of size k picked uniformly at random from the set of all such clauses on our variables, is the conjunction of these clauses satisfiable? Here we consider a variation of this problem where there is a bias towards variables occurring positive—that is, variables occur negated w.p. 0<p<½  and positive otherwise—and study how the satisfiability threshold depends on p. For p<½ this model breaks many of the symmetries of the original random k‐SAT problem, for example, the distribution of satisfying assignments in the Boolean cube is no longer uniform. For any fixed k, we find the asymptotics of the threshold as p approaches 0 or ½ . The former confirms earlier predictions based on numerical studies and heuristic methods from statistical physics.

Place, publisher, year, edition, pages
John Wiley & Sons, 2021
Keywords
ombinatorial probability, phase transition, random k-SAT, random constraint satisfaction problem
National Category
Discrete Mathematics Computer Sciences
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-147516 (URN)10.1002/rsa.20996 (DOI)000618278000001 ()2-s2.0-85101442885 (Scopus ID)
Note

Originally included in thesis in manuscript form.

Detta var en omarbetad, längre version av ett manuskript som ingick i författarens licentiatavhandling. Den tidigare versionen finns i följande post:

http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-121417

This was a revised, longer version of a manuscript which was included in the licentiate thesis from the same author. The previous version can be found in the following post:

http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-121417

Available from: 2018-05-04 Created: 2018-05-04 Last updated: 2023-03-23Bibliographically approved
Organisations

Search in DiVA

Show all publications