umu.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Markström, Klas
Publications (10 of 53) Show all publications
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: 2017-12-04Bibliographically 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.

Keyword
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: 2017-12-05Bibliographically 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: 2017-12-04Bibliographically approved
Aaghabali, M., Akbari, S., Friedland, S., Markström, K. & Tajfirouz, Z. (2015). Upper bounds on the number of perfect matchings and directed 2-factors in graphs with given number of vertices and edges. European journal of combinatorics (Print), 45, 132-144
Open this publication in new window or tab >>Upper bounds on the number of perfect matchings and directed 2-factors in graphs with given number of vertices and edges
Show others...
2015 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 45, p. 132-144Article in journal (Refereed) Published
Abstract [en]

We give an upper bound on the number of perfect matchings in simple graphs with a given number of vertices and edges. We apply this result to give an upper bound on the number of 2-factors in a directed complete bipartite balanced graph on 2n vertices. The upper bound is sharp for even n. For odd n we state a conjecture on a sharp upper bound.

National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-99326 (URN)10.1016/j.ejc.2014.11.001 (DOI)000348746000013 ()2-s2.0-84914161777 (Scopus ID)
Available from: 2015-02-06 Created: 2015-02-06 Last updated: 2017-12-04Bibliographically approved
Lundow, P.-H. & Markström, K. (2014). Finite size scaling of the 5D Ising model with free boundary conditions. Nuclear Physics B, 889, 249-260
Open this publication in new window or tab >>Finite size scaling of the 5D Ising model with free boundary conditions
2014 (English)In: Nuclear Physics B, ISSN 0550-3213, E-ISSN 1873-1562, Vol. 889, p. 249-260Article in journal (Refereed) Published
Abstract [en]

There has been a long running debate on the finite size scaling for the Ising model with free boundary conditions above the upper critical dimension, where the standard picture gives an L2 scaling for the susceptibility and an alternative theory has promoted an L5/2 scaling, as would be the case for cyclic boundary. In this paper we present results from simulation of the far largest systems used so far, up to sideL=160 and find that this data clearly supports the standard scaling. Further we present a discussion of why rigorous results for the random-cluster model provide both supports for the standard scaling picture and a clear explanation of why the scalings for free and cyclic boundary should be different.

National Category
Other Physics Topics
Identifiers
urn:nbn:se:umu:diva-99325 (URN)10.1016/j.nuclphysb.2014.10.011 (DOI)000347016900013 ()
Available from: 2015-02-06 Created: 2015-02-06 Last updated: 2017-12-04Bibliographically approved
Vinci, W., Markström, K., Boixo, S., Roy, A., Spedalieri, F. M., Warburton, P. A. & Severini, S. (2014). Hearing the shape of the Ising model with a programmable superconducting-flux annealer. Scientific Reports, 4, 5703
Open this publication in new window or tab >>Hearing the shape of the Ising model with a programmable superconducting-flux annealer
Show others...
2014 (English)In: Scientific Reports, ISSN 2045-2322, E-ISSN 2045-2322, Vol. 4, p. 5703-Article in journal (Refereed) Published
Abstract [en]

Two objects can be distinguished if they have different measurable properties. Thus, distinguishability depends on the Physics of the objects. In considering graphs, we revisit the Ising model as a framework to define physically meaningful spectral invariants. In this context, we introduce a family of refinements of the classical spectrum and consider the quantum partition function. We demonstrate that the energy spectrum of the quantum Ising Hamiltonian is a stronger invariant than the classical one without refinements. For the purpose of implementing the related physical systems, we perform experiments on a programmable annealer with superconducting flux technology. Departing from the paradigm of adiabatic computation, we take advantage of a noisy evolution of the device to generate statistics of low energy states. The graphs considered in the experiments have the same classical partition functions, but different quantum spectra. The data obtained from the annealer distinguish non-isomorphic graphs via information contained in the classical refinements of the functions but not via the differences in the quantum spectra.

Place, publisher, year, edition, pages
Nature Publishing Group, 2014
National Category
Physical Sciences
Identifiers
urn:nbn:se:umu:diva-91834 (URN)10.1038/srep05703 (DOI)000338991000008 ()
Available from: 2014-08-29 Created: 2014-08-18 Last updated: 2017-12-05Bibliographically approved
Lo, A. & Markström, K. (2014). l-Degree Turan Density. SIAM Journal on Discrete Mathematics, 28(3), 1214-1225
Open this publication in new window or tab >>l-Degree Turan Density
2014 (English)In: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 28, no 3, p. 1214-1225Article in journal (Refereed) Published
Abstract [en]

Let H-n be a k-graph on n vertices. For 0 <= l < k and an l-subset T of V (H-n), define the degree deg(T) of T to be the number of (k - l)-subsets S such that S boolean OR T is an edge in H-n. Let the minimum l-degree of H-n be delta(l) (H-n) = min{deg(T) : T subset of V (H-n) and vertical bar T vertical bar = l}. Given a family F of k-graphs, the l-degree Turan number ex(l) (n, F) is the largest delta(l) (H-n) over all F-free k-graphs H-n on n vertices. Hence, ex(0) (n, F) is the Turan number. We define l-degree Turan density to be pi(kappa)(l) (F) = lim sup(n ->infinity) ex(l)(n, F)/kappa(n-l). In this paper, we show that for k > l > 1, the set of pi(kappa)(l) (F) is dense in the interval [0, 1). Hence, there is no "jump" for l-degree Turan density when k > l > 1. We also give a lower bound on pi(kappa)(l) (F) in terms of an ordinary Turan density.

National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-92706 (URN)10.1137/120895974 (DOI)000343230800012 ()
Available from: 2014-09-01 Created: 2014-09-01 Last updated: 2017-12-05Bibliographically approved
Lo, A. & Markström, K. (2014). Perfect matchings in 3-partite 3-uniform hypergraphs. Journal of combinatorial theory. Series A (Print), 127, 22-57
Open this publication in new window or tab >>Perfect matchings in 3-partite 3-uniform hypergraphs
2014 (English)In: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 127, p. 22-57Article in journal (Refereed) Published
Abstract [en]

Let H be a 3-partite 3-uniform hypergraph, i.e. a 3-uniform hypergraph such that every edge intersects every partition class in exactly one vertex, with each partition class of size n. We determine a Dirac-type vertex degree threshold for perfect matchings in 3-partite 3-uniform hypergraphs.

Keyword
Hypergraph, k-partite, Perfect matching, Minimum degree
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-92704 (URN)10.1016/j.jcta.2014.05.004 (DOI)000341739300002 ()
Available from: 2014-09-01 Created: 2014-09-01 Last updated: 2017-12-05Bibliographically approved
Christofides, D. & Markström, K. (2014). The range of thresholds for diameter 2 in random Cayley graphs. Paper presented at 6th European Conference on Combinatorics, Graph Theory and Applications (EuroComb), AUG 29-SEP 02, 2011, Budapest, HUNGARY. European journal of combinatorics (Print), 35, 141-154
Open this publication in new window or tab >>The range of thresholds for diameter 2 in random Cayley graphs
2014 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 35, p. 141-154Article in journal (Refereed) Published
Abstract [en]

Given a group G, the model g(G, p) denotes the probability space of all Cayley graphs of G where each element of the generating set is chosen independently at random with probability p. Given a family of groups (G(k)) and a c is an element of R+ we say that c is the threshold for diameter 2 for (G(k)) if for any epsilon > 0 with high probability Gamma is an element of g(G(k), p) has diameter greater than 2 if p <= root(c - epsilon)log n/n and diameter at most 2 if p >= root(c + epsilon)log n/n. In Christofides and Markstrom (in press) [5] we proved that if c is a threshold for diameter 2 for a family of groups (G(k)) then c is an element of [1/4, 2] and provided two families of groups with thresholds 1/4 and 2 respectively. In this paper we study the question of whether every c is an element of [1/4, 2] is the threshold for diameter 2 for some family of groups. Rather surprisingly it turns out that the answer to this question is negative. We show that every c is an element of [1/4, 4/3] is a threshold but a c is an element of (4/3, 2] is a threshold if and only if it is of the form 4n/(3n - 1) for some positive integer n. 

National Category
Mathematics
Identifiers
urn:nbn:se:umu:diva-82279 (URN)10.1016/j.ejc.2013.06.030 (DOI)000324786900014 ()
Conference
6th European Conference on Combinatorics, Graph Theory and Applications (EuroComb), AUG 29-SEP 02, 2011, Budapest, HUNGARY
Available from: 2014-02-18 Created: 2013-10-29 Last updated: 2017-12-06Bibliographically approved
Christofides, D. & Markström, K. (2014). The thresholds for diameter 2 in random Cayley graphs. Random structures & algorithms (Print), 45(2), 218-235
Open this publication in new window or tab >>The thresholds for diameter 2 in random Cayley graphs
2014 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 45, no 2, p. 218-235Article in journal (Refereed) Published
Abstract [en]

Given a group G, the model G(G,p) denotes the probability space of all Cayley graphs of G where each element of the generating set is chosen independently at random with probability p. In this article we show that for any epsilon>0 and any family of groups G(k) of order n(k) for which nk, a graph kG(Gk,p) with high probability has diameter at most 2 if p(2+epsilon)lognknk and with high probability has diameter greater than 2 if p(14+epsilon)lognknk. We also provide examples of families of graphs which show that both of these results are best possible. Of particular interest is that for some families of groups, the corresponding random Cayley graphs achieve Diameter 2 significantly faster than the Erds-Renyi random graphs.

Place, publisher, year, edition, pages
John Wiley & Sons, 2014
Keyword
random graphs, Cayley graphs, diameter
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-92705 (URN)10.1002/rsa.20486 (DOI)000340278700003 ()
Available from: 2014-09-01 Created: 2014-09-01 Last updated: 2018-02-13Bibliographically approved
Organisations

Search in DiVA

Show all publications