Please wait ... |

Link to record
https://umu.diva-portal.org/smash/person.jsf?pid=authority-person:63648 $(function(){PrimeFaces.cw("InputTextarea","widget_formSmash_upper_j_idt142_recordDirectLink",{id:"formSmash:upper:j_idt142:recordDirectLink",widgetVar:"widget_formSmash_upper_j_idt142_recordDirectLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt142_j_idt144",{id:"formSmash:upper:j_idt142:j_idt144",widgetVar:"widget_formSmash_upper_j_idt142_j_idt144",target:"formSmash:upper:j_idt142:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Permanent link

Direct link

Markström, Klas

Open this publication in new window or tab >>Enumeration of sets of mutually orthogonal latin rectangles### Jäger, Gerold

### Öhman, Lars-Daniel

### Markström, Klas

### Shcherbak, Denys

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_some",{id:"formSmash:j_idt204:0:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_otherAuthors",{id:"formSmash:j_idt204:0:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_otherAuthors",multiple:true}); 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]

##### 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)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_j_idt379",{id:"formSmash:j_idt204:0:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_j_idt385",{id:"formSmash:j_idt204:0:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_j_idt391",{id:"formSmash:j_idt204:0:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_j_idt391",multiple:true});
#####

##### Funder

eSSENCE - An eScience CollaborationSwedish Research Council, 2014-4897
Available from: 2024-04-08 Created: 2024-04-08 Last updated: 2024-04-08Bibliographically approved

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

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.

Open this publication in new window or tab >>Minimum-degree conditions for rainbow triangles### Falgas-Ravry, Victor

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Markström, Klas

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Räty, Eero

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_some",{id:"formSmash:j_idt204:1:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_otherAuthors",{id:"formSmash:j_idt204:1:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_otherAuthors",multiple:true}); 2024 (English)In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118Article in journal (Refereed) Epub ahead of print
##### Abstract [en]

##### 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)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_j_idt379",{id:"formSmash:j_idt204:1:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_j_idt385",{id:"formSmash:j_idt204:1:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_j_idt391",{id:"formSmash:j_idt204:1:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_j_idt391",multiple:true});
#####

##### 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

Let G:=(G_{1},G_{2},G_{3}) be a triple of graphs on a common vertex set *V* of size *n*. A rainbow triangle in G is a triple of edges (e_{1},e_{2},e_{3}) with e_{i }∈ G_{i} for each *i* and {e_{1},e_{2},e_{3}} forming a triangle in *V*. In this paper we consider the following question: what triples of minimum degree conditions (∂(G_{1}),∂(G_{2}),∂(G_{3})) 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.

Open this publication in new window or tab >>Rainbow variations on a theme by mantel: extremal problems for Gallai colouring templates### Falgas-Ravry, Victor

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Markström, Klas

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Räty, Eero

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_some",{id:"formSmash:j_idt204:2:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_otherAuthors",{id:"formSmash:j_idt204:2:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_otherAuthors",multiple:true}); 2024 (English)In: Combinatorica, ISSN 0209-9683, E-ISSN 1439-6912Article in journal (Refereed) Epub ahead of print
##### Abstract [en]

##### 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)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_j_idt379",{id:"formSmash:j_idt204:2:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_j_idt385",{id:"formSmash:j_idt204:2:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_j_idt391",{id:"formSmash:j_idt204:2:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_j_idt391",multiple:true});
#####

##### Funder

Swedish Research Council, 2021-03687Olle Engkvists stiftelse, 213-0204
Available from: 2024-05-16 Created: 2024-05-16 Last updated: 2024-05-16

Let G:=(G_{1},G_{2},G_{3}) be a triple of graphs on the same vertex set V of size n. A rainbow triangle in G is a triple of edges (e_{1},e_{2},e_{3}) with e_{i }∈ G_{i} for each i and {e_{1},e_{2},e_{3}} 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 (α_{1},α_{2},α_{3}) such that if |E(G_{i})| >α_{i}n^{2} 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.

Open this publication in new window or tab >>The largest Condorcet domain on 8 alternatives### Leedham-Green, Charles

### Markström, Klas

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Riis, Søren

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_some",{id:"formSmash:j_idt204:3:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_otherAuthors",{id:"formSmash:j_idt204:3:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_otherAuthors",multiple:true}); 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]

##### 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)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_j_idt379",{id:"formSmash:j_idt204:3:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_j_idt385",{id:"formSmash:j_idt204:3:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_j_idt391",{id:"formSmash:j_idt204:3:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_j_idt391",multiple:true});
#####

Available from: 2023-09-19 Created: 2023-09-19 Last updated: 2024-05-10Bibliographically approved

Queen Mary University of London, London, United Kingdom.

Queen Mary University of London, London, United Kingdom.

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.

Open this publication in new window or tab >>Polarised random* κ*-SAT### Danielsson, Joel Larsson

### Markström, Klas

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_some",{id:"formSmash:j_idt204:4:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_otherAuthors",{id:"formSmash:j_idt204:4:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_otherAuthors",multiple:true}); 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]

##### 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)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_j_idt379",{id:"formSmash:j_idt204:4:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_j_idt385",{id:"formSmash:j_idt204:4:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_j_idt391",{id:"formSmash:j_idt204:4:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_j_idt391",multiple:true});
#####

Available from: 2023-08-09 Created: 2023-08-09 Last updated: 2024-01-02Bibliographically approved

Lund University, Lund, Sweden.

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.

Open this publication in new window or tab >>Revising the universality class of the four-dimensional Ising model### Lundow, Per-Håkan

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Markström, Klas

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_some",{id:"formSmash:j_idt204:5:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_otherAuthors",{id:"formSmash:j_idt204:5:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_otherAuthors",multiple:true}); 2023 (English)In: Nuclear Physics B, ISSN 0550-3213, E-ISSN 1873-1562, Vol. 993, article id 116256Article in journal (Refereed) Published
##### Abstract [en]

##### 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)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_j_idt379",{id:"formSmash:j_idt204:5:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_j_idt385",{id:"formSmash:j_idt204:5:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_j_idt391",{id:"formSmash:j_idt204:5:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_j_idt391",multiple:true});
#####

Available from: 2023-07-18 Created: 2023-07-18 Last updated: 2023-07-18Bibliographically approved

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.

Open this publication in new window or tab >>Small youden rectangles, near youden rectangles, and their connections to other row-column designs### Jäger, Gerold

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Markström, Klas

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Shcherbak, Denys

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Öhman, Lars-Daniel

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_some",{id:"formSmash:j_idt204:6:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_otherAuthors",{id:"formSmash:j_idt204:6:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_otherAuthors",multiple:true}); 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]

##### 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)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_j_idt379",{id:"formSmash:j_idt204:6:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_j_idt385",{id:"formSmash:j_idt204:6:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_j_idt391",{id:"formSmash:j_idt204:6:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_j_idt391",multiple:true});
#####

##### 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

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.

Open this publication in new window or tab >>Avoiding and Extending Partial Edge Colorings of Hypercubes### Casselgren, Carl Johan

### Johansson, Per

### Markström, Klas

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_some",{id:"formSmash:j_idt204:7:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_otherAuthors",{id:"formSmash:j_idt204:7:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_otherAuthors",multiple:true}); 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]

##### 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)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_j_idt379",{id:"formSmash:j_idt204:7:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_j_idt385",{id:"formSmash:j_idt204:7:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_j_idt391",{id:"formSmash:j_idt204:7:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_j_idt391",multiple:true});
#####

##### Funder

Swedish Research Council, 2017-05077
Available from: 2022-05-06 Created: 2022-05-06 Last updated: 2023-03-23Bibliographically approved

Department of Mathematics, Linköping University, Linköping, Sweden.

Department of Mathematics, Linköping University, Linköping, Sweden.

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 ψ.

Open this publication in new window or tab >>Efficient computation of permanents, with applications to Boson sampling and random matrices### Lundow, Per-Håkan

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Markström, Klas

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_some",{id:"formSmash:j_idt204:8:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_otherAuthors",{id:"formSmash:j_idt204:8:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_otherAuthors",multiple:true}); 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]

##### 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)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_j_idt379",{id:"formSmash:j_idt204:8:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_j_idt385",{id:"formSmash:j_idt204:8:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_j_idt391",{id:"formSmash:j_idt204:8:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_j_idt391",multiple:true});
#####

##### 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

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.

Open this publication in new window or tab >>Biased random *k*-SAT### Larsson, Joel

### Markström, Klas

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_some",{id:"formSmash:j_idt204:9:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_otherAuthors",{id:"formSmash:j_idt204:9:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_otherAuthors",multiple:true}); 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]

##### 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)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_j_idt379",{id:"formSmash:j_idt204:9:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_j_idt385",{id:"formSmash:j_idt204:9:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_j_idt391",{id:"formSmash:j_idt204:9:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_j_idt391",multiple:true});
#####

##### Note

Mathematics Institute, University of Warwick,Coventry, UK.

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.

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