umu.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Markström, Klas
Alternative names
Publications (10 of 69) Show all publications
Casselgren, C. J., Markström, K. & Pham, L. A. (2019). Latin cubes with forbidden entries. The Electronic Journal of Combinatorics, 26(1), Article ID P1.2.
Open this publication in new window or tab >>Latin cubes with forbidden entries
2019 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 26, no 1, article id P1.2Article in journal (Refereed) Published
Abstract [en]

We consider the problem of constructing Latin cubes subject to the condition that some symbols may not appear in certain cells. We prove that there is a constant y>0 such that if n=2k and A is a 3-dimensional n×n×n array where every cell contains at most γn symbols, and every symbol occurs at most γn times in every line of A, then A is avoidable; that is, there is a Latin cube L of order n such that for every 1 ≤ i,j,k ≤ n, the symbol in position (i,j,k) of L does not appear in the corresponding cell of A. 

Place, publisher, year, edition, pages
Newark: Department of Mathematical Science, University of Delaware, 2019
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-147511 (URN)000456790800002 ()
Funder
Swedish Research Council, 2014-4897
Note

Originally included in thesis in manuscript form.

Available from: 2018-05-04 Created: 2018-05-04 Last updated: 2019-04-24Bibliographically approved
Lundow, P.-H. & Markström, K. (2019). Revisiting the cavity-method threshold for random 3-SAT. Physical review. E, 99(2), Article ID 022106.
Open this publication in new window or tab >>Revisiting the cavity-method threshold for random 3-SAT
2019 (English)In: Physical review. E, ISSN 2470-0045, E-ISSN 2470-0053, Vol. 99, no 2, article id 022106Article in journal (Refereed) Published
Abstract [en]

A detailed Monte Carlo study of the satisfiability threshold for random 3-SAT has been undertaken. In combination with a monotonicity assumption we find that the threshold for random 3-SAT satisfies α3≤4.262. If the assumption is correct, this means that the actual threshold value for k=3 is lower than that given by the cavity method. In contrast the latter has recently been shown to give the correct value for large k. Our result thus indicate that there are distinct behaviors for k above and below some critical kc, and the cavity method may provide a correct mean-field picture for the range above kc.

Place, publisher, year, edition, pages
American Physical Society, 2019
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:umu:diva-162509 (URN)10.1103/PhysRevE.99.022106 (DOI)000458140700001 ()30934345 (PubMedID)
Available from: 2019-08-21 Created: 2019-08-21 Last updated: 2019-08-21Bibliographically 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: 2019-05-23Bibliographically approved
Falgas-Ravry, V., Markström, K. & Verstraëte, J. (2018). Full subgraphs. Journal of Graph Theory, 88(3), 411-427
Open this publication in new window or tab >>Full subgraphs
2018 (English)In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 88, no 3, p. 411-427Article in journal (Refereed) Published
Keywords
extremal graph theory, graph discrepancy, graph partitions
National Category
Mathematics
Identifiers
urn:nbn:se:umu:diva-144161 (URN)10.1002/jgt.22221 (DOI)000432013200004 ()2-s2.0-85034034448 (Scopus ID)
Funder
Swedish Research Council
Available from: 2018-01-23 Created: 2018-01-23 Last updated: 2018-06-13Bibliographically approved
Akbari, S., Friedland, S., Markström, K. & Zare, S. (2016). On 1-sum flows in undirected graphs. The Electronic Journal of Linear Algebra, 31, 646-665
Open this publication in new window or tab >>On 1-sum flows in undirected graphs
2016 (English)In: The Electronic Journal of Linear Algebra, ISSN 1537-9582, E-ISSN 1081-3810, Vol. 31, p. 646-665Article in journal (Refereed) Published
Abstract [en]

Let G = (V, E) be a simple undirected graph. For a given set L subset of R, a function omega: E -> L is called an L-flow. Given a vector gamma is an element of R-V , omega is a gamma-L-flow if for each v is an element of V, the sum of the values on the edges incident to v is gamma(v). If gamma(v) = c, for all v is an element of V, then the gamma-L-flow is called a c-sum L-flow. In this paper, the existence of gamma-L-flows for various choices of sets L of real numbers is studied, with an emphasis on 1-sum flows. Let L be a subset of real numbers containing 0 and denote L* := L \ {0}. Answering a question from [S. Akbari, M. Kano, and S. Zare. A generalization of 0-sum flows in graphs. Linear Algebra Appl., 438:3629-3634, 2013.], the bipartite graphs which admit a 1-sum R* -flow or a 1-sum Z* -flow are characterized. It is also shown that every k-regular graph, with k either odd or congruent to 2 modulo 4, admits a 1-sum {-1, 0, 1}-flow.

Place, publisher, year, edition, pages
INT LINEAR ALGEBRA SOC, 2016
Keywords
L-Flow, gamma-L-Flow, c-Sum flow, Bipartite graph
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-134293 (URN)10.13001/1081-3810.3003 (DOI)000396550500002 ()
Available from: 2017-05-09 Created: 2017-05-09 Last updated: 2018-06-09Bibliographically approved
Falgas-Ravry, V. & Markström, K. (2016). Random subcube intersection graphs I: cliques and covering. The Electronic Journal of Combinatorics, 23(3), Article ID P3.43.
Open this publication in new window or tab >>Random subcube intersection graphs I: cliques and covering
2016 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 23, no 3, article id P3.43Article in journal (Refereed) Published
Abstract [en]

We study random subcube intersection graphs, that is, graphs obtained by selecting a random collection of subcubes of a fixed hypercube Qd to serve as the vertices of the graph, and setting an edge between a pair of subcubes if their intersection is non-empty. Our motivation for considering such graphs is to model 'random compatibility' between vertices in a large network. For both of the models considered in this paper, we determine the thresholds for covering the underlying hypercube Qd and for the appearance of s-cliques. In addition we pose a number of open problems.

Keywords
Random graphs, Random intersection graphs
National Category
Mathematics
Identifiers
urn:nbn:se:umu:diva-127244 (URN)000385228700002 ()
Available from: 2016-11-14 Created: 2016-11-03 Last updated: 2018-06-09Bibliographically approved
Lundow, P.-H. & Markström, K. (2016). The scaling window of the 5D Ising model with free boundary conditions. Nuclear Physics B, 911, 163-172
Open this publication in new window or tab >>The scaling window of the 5D Ising model with free boundary conditions
2016 (English)In: Nuclear Physics B, ISSN 0550-3213, E-ISSN 1873-1562, Vol. 911, p. 163-172Article in journal (Refereed) Published
Abstract [en]

The five-dimensional Ising model with free boundary conditions has recently received a renewed interest in a debate concerning the finite-size scaling of the susceptibility near the critical temperature. We provide evidence in favour of the conventional scaling picture, where the susceptibility scales as L-2 inside a critical scaling window of width 1/L-2. Our results are based on Monte Carlo data gathered on system sizes up to L = 79(ca. three billion spins) for a wide range of temperatures near the critical point. We analyse the magnetisation distribution, the susceptibility and also the scaling and distribution of the size of the Fortuin-Kasteleyn cluster containing the origin. The probability of this cluster reaching the boundary determines the correlation length, and its behaviour agrees with the mean field critical exponent delta = 3, that the scaling window has width 1/L-2.

Place, publisher, year, edition, pages
Elsevier, 2016
National Category
Atom and Molecular Physics and Optics Probability Theory and Statistics
Identifiers
urn:nbn:se:umu:diva-127239 (URN)10.1016/j.nuclphysb.2016.08.003 (DOI)000384565800007 ()
Available from: 2016-11-14 Created: 2016-11-03 Last updated: 2018-06-09Bibliographically approved
Lundow, P.-H. & Markström, K. (2015). Complete graph asymptotics for the Ising and random-cluster models on five-dimensional grids with a cyclic boundary. Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, 91, Article ID 022112.
Open this publication in new window or tab >>Complete graph asymptotics for the Ising and random-cluster models on five-dimensional grids with a cyclic boundary
2015 (English)In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, E-ISSN 1550-2376, Vol. 91, article id 022112Article in journal (Refereed) Published
Abstract [en]

The finite-size scaling behavior for the Ising model in five dimensions, with either free or cyclic boundary, has been the subject of a long-running debate. The older papers have been based on ideas from, e.g., field theory or renormalization. In this paper we propose a detailed and exact scaling picture for critical region of the model with cyclic boundary. Unlike the previous papers our approach is based on a comparison with the existing exact and rigorous results for the FK-random-cluster model on a complete graph. Based on those results we predict several distinct scaling regions in an L  -dependent window around the critical point. We test these predictions by comparing with data from Monte Carlo simulations and find a good agreement. The main feature which differs between the complete graph and the five-dimensional model with free boundary is the existence of a bimodal energy distribution near the critical point in the latter. This feature was found by the same authors in an earlier paper in the form of a quasi-first-order phase transition for the same Ising model.

Place, publisher, year, edition, pages
American Physical Society, 2015
National Category
Condensed Matter Physics
Identifiers
urn:nbn:se:umu:diva-99987 (URN)10.1103/PhysRevE.91.022112 (DOI)000349910000001 ()
Available from: 2015-02-17 Created: 2015-02-17 Last updated: 2018-06-07Bibliographically approved
Lo, A. & Markström, K. (2015). F-Factors in Hypergraphs Via Absorption. Graphs and Combinatorics, 31(3), 679-712
Open this publication in new window or tab >>F-Factors in Hypergraphs Via Absorption
2015 (English)In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 31, no 3, p. 679-712Article in journal (Refereed) Published
Abstract [en]

Given integers n ≥ k > l ≥ 1 and a k-graph F with |V(F)| divisible by n, define t k l (n, F) to be the smallest integer d such that every k-graph H of order n with minimum l-degree δl(H) ≥ d contains an F-factor. A classical theorem of Hajnal and Szemerédi in (Proof of a Conjecture of P. Erd˝os, pp. 601–623, 1969) implies that t2 1 (n, Kt) = (1 − 1/t)n for integers t. For k ≥ 3, t k k−1(n, Kk k ) (the δk−1(H) threshold for perfect matchings) has been determined by Kühn and Osthus in (J Graph Theory 51(4):269–280, 2006) (asymptotically) and Rödl et al. in (J Combin Theory Ser A 116(3):613–636, 2009) (exactly) for large n. In this paper, we generalise the absorption technique of Rödl et al. in (J Combin Theory Ser A 116(3):613–636, 2009) to F-factors. We determine the asymptotic values of t k 1 (n, Kk k (m)) for k = 3, 4 and m ≥ 1. In addition, we show that for t > k = 3 and γ > 0, t3 2 (n, K3 t ) ≤ (1− 2 t2−3t+4 +γ )n provided n is large and t|n. We also bound t 3 2 (n, K3 t )from below. In particular, we deduce that t 3 2 (n, K3 4 ) = (3/4+o(1))n answering a question of Pikhurko in (Graphs Combin 24(4):391–404, 2008). In addition, we prove that t k k−1(n, Kk t ) ≤ (1 − t−1 k−1 −1 + γ )n for γ > 0, k ≥ 6 and t ≥ (3 + √ 5)k/2 provided n is large and t|n.

Keywords
Hypergraph, k-Graph, F-factor, Minimum degree, Primary 05C65, 05C70, 05C07
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-92703 (URN)10.1007/s00373-014-1410-8 (DOI)000353232900015 ()2-s2.0-84896417194 (Scopus ID)
Available from: 2014-09-01 Created: 2014-09-01 Last updated: 2018-06-07Bibliographically approved
Lundow, P.-H. & Markström, K. (2015). The discontinuity of the specific heat for the 5D Ising model. Nuclear Physics B, 895, 305-318
Open this publication in new window or tab >>The discontinuity of the specific heat for the 5D Ising model
2015 (English)In: Nuclear Physics B, ISSN 0550-3213, E-ISSN 1873-1562, Vol. 895, p. 305-318Article in journal (Refereed) Published
Abstract [en]

In this paper we investigate the behaviour of the specific heat around the critical point of the Ising model in dimension 5 to 7. We find a specific heat discontinuity, like that for the mean field Ising model, and provide estimates for the left and right hand limits of the specific heat at the critical point. We also estimate the singular exponents, describing how the specific heat approaches those limits. Additionally, we make a smaller scale investigation Of the same properties in dimension 6 and 7, and provide strongly improved estimates for the critical temperature K-c in d = 5, 6, 7 which bring the best MC-estimate closer to those obtained by long high temperature series expansions.

National Category
Mathematics
Identifiers
urn:nbn:se:umu:diva-106125 (URN)10.1016/j.nuclphysb.2015.04.013 (DOI)000355032900013 ()
Available from: 2015-07-14 Created: 2015-07-09 Last updated: 2018-06-07Bibliographically approved
Organisations

Search in DiVA

Show all publications