umu.sePublikationer
Ändra sökning
Avgränsa sökresultatet
12 1 - 50 av 69
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Träffar per sida
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sortering
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
Markera
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
  • 1. Aaghabali, M.
    et al.
    Akbari, S.
    Friedland, S.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Tajfirouz, Z.
    Upper bounds on the number of perfect matchings and directed 2-factors in graphs with given number of vertices and edges2015Ingår i: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 45, s. 132-144Artikel i tidskrift (Refereegranskat)
    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.

  • 2. Akbari, Saieed
    et al.
    Friedland, Shmuel
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Zare, Sanaz
    On 1-sum flows in undirected graphs2016Ingår i: The Electronic Journal of Linear Algebra, ISSN 1537-9582, E-ISSN 1081-3810, Vol. 31, s. 646-665Artikel i tidskrift (Refereegranskat)
    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.

  • 3.
    Andren, Daniel
    et al.
    Umeå universitet, Teknisk-naturvetenskaplig fakultet, Matematik och matematisk statistik.
    Hellström, Lars
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskaplig fakultet, Matematik och matematisk statistik.
    On the complexity of matrix reduction over finite fields2006Rapport (Övrigt vetenskapligt)
  • 4.
    Andren, Daniel
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    The bivariate ising polynomial of a graph2009Ingår i: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 157, nr 11, s. 2515-2524Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    In this paper we discuss the two variable Ising polynomials in a graph theoretical setting. This polynomial has its origin in physics as the partition function of the Ising model with an external field. We prove some basic properties of the Ising polynomial and demonstrate that it encodes a large amount of combinatorial information about a graph. We also give examples which prove that certain properties, such as the chromatic number, are not determined by the Ising polynomial. Finally we prove that there exist large families of non-isomorphic planar triangulations with identical Ising polynomial. (C) 2009 Published by Elsevier B.V.

  • 5.
    Andrén, Daniel
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Hellström, Lars
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Fast multiplication of matrices over a finitely generated semiring2008Ingår i: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 107, nr 6, s. 230-234Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    In this paper we show that n×n matrices with entries from a semiring R which is generated additively by q generators can be multiplied in time O(q2nω), where nω is the complexity for matrix multiplication over a ring (Strassen: ω<2.807, Coppersmith and Winograd: ω<2.376).

    We first present a combinatorial matrix multiplication algorithm for the case of semirings with q elements, with complexity O(n3/log2qn), matching the best known methods in this class.

    Next we show how the ideas used can be combined with those of the fastest known boolean matrix multiplication algorithms to give an O(q2nω) algorithm for matrices of, not necessarily finite, semirings with q additive generators.

    For finite semirings our combinatorial algorithm is simple enough to be a practical algorithm and is expected to be faster than the O(q2nω) algorithm for matrices of practically relevant sizes.

  • 6.
    Andrén, Daniel
    et al.
    Umeå universitet, Teknisk-naturvetenskaplig fakultet, Matematik och matematisk statistik.
    Hellström, Lars
    Umeå universitet, Teknisk-naturvetenskaplig fakultet, Matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskaplig fakultet, Matematik och matematisk statistik.
    On the complexity of matrix reduction over finite fields2007Ingår i: Advances in Applied Mathematics, ISSN 0196-8858, Vol. 39, nr 4, s. 428-452Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We study matrix elimination over finite fields, and present an algorithm which is asymptotically faster than the traditional Gauss--Jordan elimination. We also bound the average and worst-case complexity for the problem, proving that our algorithm is close to being optimal, and show related concentration results for random matrices.

    Next we present the results of a large computational study of the complexities for small matrices and fields. Here we determine the exact distribution of the complexity for matrices from $\mathrm{GL}_{n}(\mathbb{F}_{q})$, with $n$ an $q$ small

    Finally we consider an extension of the problems studied for finite fields to finite semifields. We give a conjecture on the behaviour of a natural analogue of $\mathrm{GL}_{n}$ for semifields and prove this for a certain class of semifields.

  • 7.
    Behndig, Anders
    et al.
    Umeå universitet, Medicinska fakulteten, Institutionen för klinisk vetenskap, Oftalmiatrik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Determination of the aqueous humor volume by three-dimensional mapping of the anterior chamber.2005Ingår i: Ophthalmic Research, ISSN 0030-3747, E-ISSN 1423-0259, Vol. 37, nr 1, s. 13-16Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    In this study involving 12 patients planned for routine cataract surgery, we used the topography of the anterior chamber depth and the corneal diameter obtained from Orbscan II data to calculate the aqueous humor volume. Prior to the surgical procedure, a small amount of fluorescein was injected into the anterior chamber and an aqueous humor sample was taken, from which the aqueous humor volume could be calculated by fluorometry. The volumes obtained from Orbscan II data were validated by the fluorometric measurements and compared to three theoretical formulas for aqueous humor volume calculation. The aqueous humor volume calculations based on the Orbscan II data aligned better to the fluorometric values (R(2) = 0.890) than the values obtained by Heim's formula (R(2) = 0.677), Brubaker's formula (R(2) = 0.671), and Schenker's formula (R(2) = 0.585), or the assumption of a constant aqueous humor volume.

  • 8. Brinkmann, Gunnar
    et al.
    Goedgebeur, Jan
    Hägglund, Jonas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Generation and properties of snarks2013Ingår i: Journal of combinatorial theory. Series B (Print), ISSN 0095-8956, E-ISSN 1096-0902, Vol. 103, nr 4, s. 468-488Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    For many of the unsolved problems concerning cycles and matchings in graphs it is known that it is sufficient to prove them for snarks, the class of non-trivial 3-regular graphs which cannot be 3-edge coloured.

    In the first part of this paper we present a. new algorithm for generating all non-isomorphic snarks of a given order. Our implementation of the new algorithm is 14 times faster than previous programs for generating snarks, and 29 times faster for generating weak snarks. Using this program we have generated all non-isomorphic snarks on n <= 36 vertices. Previously lists up to n = 28 vertices have been published.

    In the second part of the paper we analyze the sets of generated snarks with respect to a number of properties and conjectures. We find that some of the strongest versions of the cycle double cover conjecture hold for all snarks of these orders, as does Jaeger's Petersen colouring conjecture, which in turn implies that Fulkerson's conjecture has no small counterexamples. In contrast to these positive results we also find counterexamples to eight previously published conjectures concerning cycle coverings and the general cycle structure of cubic graphs.

    (C) 2013 Published by Elsevier Inc.

  • 9. Casselgren, Carl Johan
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Pham, Lan Anh
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Edge precoloring extension of hypercubesManuskript (preprint) (Övrigt vetenskapligt)
    Abstract [en]

    We consider the problem of extending partial edge colorings of hypercubes. In particular, we obtain an analogue of the positive solution to the famous Evans' conjecture on completing partial Latin squares by proving that every proper partial edge coloring of at most (d-1) edges of the d-dimensional hypercube Qd can be extended to a proper d-edge coloring of Qd. Additionally, we characterize which partial edge colorings of Qd with precisely d precolored edges are extendable to proper d-edge colorings of Qd.

  • 10. Casselgren, Carl Johan
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Pham, Lan Anh
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Latin cubes with forbidden entries2019Ingår i: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 26, nr 1, artikel-id P1.2Artikel i tidskrift (Refereegranskat)
    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. 

  • 11. Casselgren, Carl Johan
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Pham, Lan Anh
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Restricted extension of sparse partial edge colorings of hypercubesManuskript (preprint) (Övrigt vetenskapligt)
    Abstract [en]

    We consider the following type of question: Given a partial proper d-edge coloring of the d-dimensional hypercube Qd, and lists of allowed colors for the non-colored edges of Qd, can we extend the partial coloring to a proper d-edge coloring using only colors from the lists? We prove that this question has a positive answer in the case when both the partial coloring and the color lists satisfy certain sparsity conditions.

  • 12. Christofides, Demetres
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Random Latin square graphs2012Ingår i: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 41, nr 1, s. 47-65Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    In this paper we introduce new models of random graphs, arising from Latin squares which include random Cayley graphs as a special case. We investigate some properties of these graphs including their clique, independence and chromatic numbers, their expansion properties as well as their connectivity and Hamiltonicity. The results obtained are compared with other models of random graphs and several similarities and differences are pointed out. For many properties our results for the general case are as strong as the known results for random Cayley graphs and sometimes improve the previously best results for the Cayley case. (C) 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011

  • 13. Christofides, Demetres
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    The guessing number of undirected graph2011Ingår i: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 18, nr 1, s. P192-Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Riis [Electron. J. Combin., 14(1):R44, 2007] introduced a guessing game for graphs which is equivalent to finding protocols for network coding. In this paper we prove upper and lower bounds for the winning probability of the guessing game on undirected graphs. We find optimal bounds for perfect graphs and minimally imperfect graphs, and present a conjecture relating the exact value for all graphs to the fractional chromatic number.

  • 14. Christofides, Demetres
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    The range of thresholds for diameter 2 in random Cayley graphs2014Ingår i: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 35, s. 141-154Artikel i tidskrift (Refereegranskat)
    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. 

  • 15.
    Christofides, Demetres
    et al.
    School of Computing and Mathematics, UCLan Cyprus, Pyla, Cyprus.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    The thresholds for diameter 2 in random Cayley graphs2014Ingår i: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 45, nr 2, s. 218-235Artikel i tidskrift (Refereegranskat)
    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.

  • 16. Demetres, Christofides
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales2008Ingår i: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 32, nr 1, s. 88-100Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    The Alon-Roichman theorem states that for every $\ge > 0$ there is a constant $c(\ge)$, such that the Cayley graph of a finite group $G$ with respect to $c(\ge)\log{\abs{G}}$ elements of $G$, chosen independently and uniformly at random, has expected second largest eigenvalue less than $\ge$. In particular, such a graph is an expander with high probability.

    Landau and Russell, and independently Loh and Schulman, improved the bounds of the theorem. Following Landau and Russell we give a simpler proof of the result, improving the bounds even further. When considered for a general group $G$, our bounds are in a sense best possible.

    We also give a generalisation of the Alon-Roichman theorem to random coset graphs.

  • 17. Falgas-Ravry, Victor
    et al.
    Larsson, Joel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Speed and concentration of the covering time for structured coupon collectorsManuskript (preprint) (Övrigt vetenskapligt)
    Abstract [en]

    Let be an n-set, and let be a random variable taking values in the powerset of V. Suppose we are given a sequence of random coupons X1,X2,…, where the Xi are independent random variables with distribution given by X. The covering time T is the smallest integer t≥0 such that ⋃ti=1Xi=V. The distribution of T is important in many applications in combinatorial probability, and has been extensively studied. However the literature has focussed almost exclusively on the case where X is assumed to be symmetric and/or uniform in some way.

    In this paper we study the covering time for much more general random variables X; we give general criteria for being sharply concentrated around its mean, precise tools to estimate that mean, as well as examples where fails to be concentrated and when structural properties in the distribution of allow for a very different behaviour of relative to the symmetric/uniform case.

  • 18.
    Falgas-Ravry, Victor
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Random subcube intersection graphs I: cliques and covering2016Ingår i: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 23, nr 3, artikel-id P3.43Artikel i tidskrift (Refereegranskat)
    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.

  • 19.
    Falgas-Ravry, Victor
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Verstraëte, Jacques
    University of California-San Diego.
    Full subgraphs2018Ingår i: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 88, nr 3, s. 411-427Artikel i tidskrift (Refereegranskat)
    Publikationen är tillgänglig i fulltext från 2020-12-31 17:27
  • 20.
    Friedland, S.
    et al.
    Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago, Chicago, IL, 60607-7045, USA; Berlin Mathematical School, Berlin, Germany.
    Krop, E.
    Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago, Chicago, IL, 60607-7045, USA .
    Lundow, Per-Håkan
    Department of Physics, AlbaNova University Center, KTH, 106 91, Stockholm, Sweden .
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    On the Validations of the Asymptotic Matching Conjectures2008Ingår i: Journal of statistical physics, ISSN 0022-4715, E-ISSN 1572-9613, Vol. 133, nr 3, s. 513-533Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    In this paper we review the asymptotic matching conjectures for r-regular bipartite graphs, and their connections in estimating the monomer-dimer entropies in d-dimensional integer lattice and Bethe lattices. We prove new rigorous upper and lower bounds for the monomer-dimer entropies, which support these conjectures. We describe a general construction of infinite families of r-regular tori graphs and give algorithms for computing the monomer-dimer entropy of density p, for any p is an element of[0,1], for these graphs. Finally we use tori graphs to test the asymptotic matching conjectures for certain infinite r-regular bipartite graphs.

  • 21. Friedland, S.
    et al.
    Lundow, P. H.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    The 1-vertex transfer matrix and accurate estimation of channel capacity2010Ingår i: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 57, nr 8, s. 3692-3699Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    The notion of a 1-vertex transfer matrix for multidimensional codes is introduced. It is shown that the capacity of such codes, or the topological entropy, can be expressed as the limit of the logarithm of spectral radii of 1-vertex transfer matrices. Storage and computations using the 1-vertex transfer matrix are much smaller than storage and computations needed for the standard transfer matrix. The method is applied to estimate the first 15 digits of the entropy of the 2-D (0, 1) run length limited channel. A large-scale computation of eigenvalues for the (0, 1) run length limited channel in 2-D and 3-D have been carried out. This was done in order to be able to compare the computational cost of the new method with the standard transfer matrix and have rigorous bounds to compare the estimates with. This in turn leads to improvements on the best previous lower and upper bounds for these channels.

  • 22. Hamma, Alioscia
    et al.
    Markopoulou, Fotini
    Lloyd, Seth
    Caravelli, Francesco
    Severini, Simone
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Quantum bose-hubbard model with an evolving graph as a toy model for emergent spacetime2010Ingår i: Physical Review D. Particles and fields, ISSN 0556-2821, E-ISSN 1089-4918, Vol. 81, nr 10, s. 104032-22 pagesArtikel i tidskrift (Refereegranskat)
    Abstract [en]

    We present a toy model for interacting matter and geometry that explores quantum dynamics in a spin system as a precursor to a quantum theory of gravity. The model has no a priori geometric properties; instead, locality is inferred from the more fundamental notion of interaction between the matter degrees of freedom. The interaction terms are themselves quantum degrees of freedom so that the structure of interactions and hence the resulting local and causal structures are dynamical. The system is a Hubbard model where the graph of the interactions is a set of quantum evolving variables. We show entanglement between spatial and matter degrees of freedom. We study numerically the quantum system and analyze its entanglement dynamics. We analyze the asymptotic behavior of the classical model. Finally, we discuss analogues of trapped surfaces and gravitational attraction in this simple model.

  • 23.
    Häggkvist, Roland
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Cycle double covers and spanning minors I2006Ingår i: Journal of combinatorial theory. Series B (Print), ISSN 0095-8956, E-ISSN 1096-0902, Vol. 96, nr 2, s. 183-206Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Define a graph to be a Kotzig graph if it is $m$-regular and has an $m$-edge colouring in which each pair of colours form a Hamiltonian cycle. We show that every cubic graph with spanning subgraph consisting of a subdivision of a Kotzig graph together with even cycles has a cycle double cover, in fact a 6-CDC. We prove this for two other families of graphs similar to Kotzig graphs as well. In particular, let $F$ be a 2-factor in a cubic graph $G$ and denote by $G_{F}$ the pseudograph obtained by contracting each component in $F$. We show that if there exist a cycle in $G_{F}$ through all vertices of odd degree, then $G$ has a CDC. We conjecture that every 3-connected cubic graph contains a spanning subgraph homeomorphic to a Kotzig graph. In a sequel we show that every cubic graph with a spanning homeomorph of a 2-connected cubic graph on at most 10 vertices has a CDC.

  • 24.
    Häggkvist, Roland
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Cycle double covers and spanning minors II2006Ingår i: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 306, nr 8-9, s. 762-778Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    In this paper we continue our investigations from [R. Häggkvist, K. Markström, Cycle double covers and spanning minors, Technical Report 07, Department of Mathematics, Umeå University, Sweden, 2001, J. Combin. Theory, Ser. B, to appear] regarding spanning subgraphs which imply the existence of cycle double covers. We prove that if a cubic graph G has a spanning subgraph isomorphic to a subdivision of a bridgeless cubic graph on at most 10 vertices then G has a CDC. A notable result is thus that a cubic graph with a spanning Petersen minor has a CDC, a result also obtained by Goddyn [L. Goddyn, Cycle covers of graphs, Ph.D. Thesis, University of Waterloo, 1988].

  • 25.
    Häggkvist, Roland
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Rosengren, Anders
    Department of Physics, AlbaNova University Center, KTH, SE-106 91 Stockholm, Sweden.
    Andrén, Daniel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Kundoras, Petras
    Department of Physics, AlbaNova University Center, KTH, SE-106 91 Stockholm, Sweden.
    Lundow, Per-Håkan
    Department of Physics, AlbaNova University Center, KTH, SE-106 91 Stockholm, Sweden.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Computation of the Ising partition function for two-dimensional square grids2004Ingår i: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics, ISSN 1063-651X, E-ISSN 1095-3787, Vol. 69, nr 4, s. 19-, artikel-id 046104Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    An improved method for obtaining the Ising partition function for $n \times n$ square grids with periodic boundary is presented. Our method applies results from Galois theory in order to split the computation into smaller parts and at the same time avoid the use of numerics. Using this method we have computed the exact partition function for the $320 \times 320$-grid, the $256 \times 256$-grid, and the $160 \times 160$-grid, as well as for a number of smaller grids. We obtain scaling parameters and compare with what theory prescribes.

  • 26.
    Häggkvist, Roland
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Rosengren, Anders
    Department of Physics, AlbaNova University Center, KTH, SE-106 91, Stockholm, Sweden .
    Andrén, Daniel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Kundrotas, Petras
    Department of Physics, AlbaNova University Center, KTH, SE-106 91, Stockholm, Sweden; Department of Biosciences at Novum, Karolinska institutet, SE-141 57, Huddinge, Sweden.
    Lundow, Per-Håkan
    Department of Physics, AlbaNova University Center, KTH, SE-106 91, Stockholm, Sweden .
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    A Monte Carlo sampling scheme for the Ising model2004Ingår i: Journal of statistical physics, ISSN 0022-4715, E-ISSN 1572-9613, Vol. 114, nr 1-2, s. 455-480Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    In this paper we describe a Monte Carlo sampling scheme for the Ising model and similar discrete-state models. The scheme does not involve any particular method of state generation but rather focuses on a new way of measuring and using the Monte Carlo data. We show how to reconstruct the entropy S of the model, from which, e.g., the free energy can be obtained. Furthermore we discuss how this scheme allows us to more or less completely remove the effects of critical fluctuations near the critical temperature and likewise how it reduces critical slowing down. This makes it possible to use simple state generation methods like the Metropolis algorithm also for large lattices.

  • 27.
    Häggkvist, Roland
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Rosengren, Anders
    Lundow, Per Håkan
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Andrén, Daniel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Kundrotas, P.
    On the Ising model for the simple cubic lattice2007Ingår i: Advances in Physics, ISSN 0001-8732, E-ISSN 1460-6976, Vol. 56, nr 5, s. 653-755Artikel, forskningsöversikt (Refereegranskat)
    Abstract [en]

    The Ising model was introduced in 1920 to describe a uniaxial system of magnetic moments, localized on a lattice, interacting via nearest-neighbour exchange interaction. It is the generic model for a continuous phase transition and arguably the most studied model in theoretical physics. Since it was solved for a two-dimensional lattice by Onsager in 1944, thereby representing one of the very few exactly solvable models in dimensions higher than one, it has served as a testing ground for new developments in analytic treatment and numerical algorithms. Only series expansions and numerical approaches, such as Monte Carlo simulations, are available in three dimensions. This review focuses on Monte Carlo simulation. We build upon a data set of unprecedented size. A great number of quantities of the model are estimated near the critical coupling. We present both a conventional analysis and an analysis in terms of a Puiseux series for the critical exponents. The former gives distinct values of the high- and low-temperature exponents; by means of the latter we can get these exponents to be equal at the cost of having true asymptotic behaviour being found only extremely close to the critical point. The consequences of this for simulations of lattice systems are discussed at length.

  • 28.
    Hägglund, Jonas
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    On stable cycles and cycle double covers of graphs with large circumference2012Ingår i: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 312, nr 17, s. 2540-2544Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    A cycle C in a graph is called stable if there exists no other cycle D in the same graph such that V(C)⊆V(D). In this paper, we study stable cycles in snarks and we show that if a cubic graph G has a cycle of length at least |V(G)|−9 then it has a cycle double cover. We also give a construction for an infinite snark family with stable cycles of constant length and answer a question by Kochol by giving examples of cyclically 5-edge connected snarks with stable cycles.

  • 29.
    Hägglund, Jonas
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Shortest cycle covers and cycle double covers with large 2-regular subgraphs2013Ingår i: Journal of Combinatorics, ISSN 2156-3527, E-ISSN 2150-959X, Vol. 4, nr 4, s. 457-468Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    In this paper, we show that many snarks have a shortest cycle cover of length 4/3 m + c for a constant c, where m is the number of edges in the graph, in agreement with the conjecture that all snarks have shortest cycle covers of length 4/3 m + o(m). In particular, we prove that graphs with perfect matching index at most 4 have cycle covers of length 4/3 m and satisfy the (1,2)-covering conjecture of Zhang, and that graphs with large circumference have cycle covers of length close to 4/3 m. We also prove some results for graphs with low oddness and discuss the connection with Jaeger’s Petersen colouring conjecture.

  • 30. Johansson, Anders
    et al.
    Johansson, Robert
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Factors of r-partite graphs and bounds for the strong chromatic number2010Ingår i: Ars combinatoria, ISSN 0381-7032, Vol. 95, s. 277-287Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We give an optimal degree condition for a tripartite graph to have a spanning subgraph consisting of complete graphs of order 3. This result is used to give an upper bound of 2 Delta for the strong chromatic number of n vertex graphs with Delta >= n/6.

  • 31.
    Johnson, J. Robert
    et al.
    Queen Mary Univ London, Sch Math Sci, London E1 4NS, England.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Turán and Ramsey properties of subcube intersection graphs2013Ingår i: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 22, nr 1, s. 55-70Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    The discrete cube {0, 1}d is a fundamental combinatorial structure. A subcube of {0, 1}d is a subset of 2k of its points formed by fixing k coordinates and allowing the remaining d - k to vary freely. This paper is concerned with patterns of intersections among subcubes of the discrete cube. Two sample questions along these lines are as follows: given a family of subcubes in which no r + 1 of them have non-empty intersection, how many pairwise intersections can we have? How many subcubes can we have if among them there are no k which have non-empty intersection and no l which are pairwise disjoint? These questions are naturally expressed using intersection graphs. The intersection graph of a family of sets has one vertex for each set in the family with two vertices being adjacent if the corresponding subsets intersect. Let I(n, d) be the set of all n vertex graphs which can be represented as the intersection graphs of subcubes in {0, 1}d. With this notation our first question above asks for the largest number of edges in a Kr+1-free graph in I(n, d). As such it is a Turán-type problem. We answer this question asymptotically for some ranges of r and d. More precisely we show that if (k + 1)2 [d/k+1] &lt; n ≥k2[d/k] for some integer k ≥ 2 then the maximum edge density is (1 - 1/k - o(1)) provided that n is not too close to the lower limit of the range. The second question can be thought of as a Ramsey-type problem. The maximum such n can be defined in the same way as the usual Ramsey number but only considering graphs which are in I(n, d). We give bounds for this maximum n mainly concentrating on the case that l is fixed, and make some comparisons with the usual Ramsey number.

  • 32.
    Jonsson, Maria
    et al.
    Umeå universitet, Medicinska fakulteten, Institutionen för klinisk vetenskap, Oftalmiatrik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Behndig, Anders
    Umeå universitet, Medicinska fakulteten, Institutionen för klinisk vetenskap, Oftalmiatrik.
    Slit-scan tomography evaluation of the anterior chamber and corneal configurations at different ages.2006Ingår i: Acta Ophthalmologica Scandinavica, ISSN 1395-3907, E-ISSN 1600-0420, Vol. 84, nr 1, s. 116-120Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    PURPOSE: To evaluate the aqueous humour and corneal volumes, their correlations to age, sex and refractive status, and their changes with age. METHODS: A total of 153 eyes of 153 healthy volunteers and 58 eyes of 58 patients planned for cataract surgery were examined with Orbscan II slit-scan tomography and the autorefractometer-keratometer. In 16 eyes of 16 volunteers, the same examinations were performed twice with a 4-year interval. Anterior chamber volumes were calculated with a 3-dimensional mapping method, corneal volumes were calculated, and multiple refraction and corneal/anterior chamber configuration variables were registered. RESULTS: The aqueous humour volume is inversely correlated to the age of the individual (r = - 0.22, p = 0.001), with an average decrease of 1.4 +/- 2.6 microl per year on longitudinal follow-up (p = 0.042). Specifically, the posterior part of the anterior chamber undergoes a pronounced reduction in volume with time, whereas the volume of the anterior part increases slightly with time. Increasing steepness and peripheral thinning of the cornea (p = 0.034), and a reduction in corneal volume (p = 0.037) were also seen with increasing age. Males had less steeply curved corneas and higher aqueous humour volumes than females. CONCLUSION: The anterior segment of the eye undergoes continuous alterations with age, which differ significantly between the genders. These normal differences and alterations may be of importance in the planning of refractive procedures, and in the evaluation of disease processes.

  • 33.
    Jäger, Gerold
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Shcherbak, Denys
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Öhman, Lars-Daniel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Enumeration of t-tuples of Mutually Orthogonal Latin Rectangles and Finite GeometriesManuskript (preprint) (Övrigt vetenskapligt)
  • 34.
    Jäger, Gerold
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Öhman, Lars-Daniel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Shcherbak, Denys
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Triples of Orthogonal Latin and Youden Rectangles of small order2019Ingår i: Journal of combinatorial designs (Print), ISSN 1063-8539, E-ISSN 1520-6610, Vol. 27, nr 4, s. 229-250Artikel i tidskrift (Refereegranskat)
    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.

  • 35.
    Jäger, Gerold
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Shcherbak, Denys
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Öhman, Lars-Daniel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Enumeration of Youden Rectangles of Small ParametersManuskript (preprint) (Övrigt vetenskapligt)
  • 36.
    Larsson, Joel
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Biased random k-SATManuskript (preprint) (Övrigt vetenskapligt)
  • 37.
    Larsson, Joel
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Biased random k-SATManuskript (preprint) (Övrigt vetenskapligt)
    Abstract [en]

    The random k-SAT problem has become one of the most studied intersection points of combinatorics, computer science and physics. The basic problem is as follows: We have a set of n boolean variables and then pick m clauses of size k uniformly at random from the set of all such clauses on our variables (we give a more detailed definition later) and then ask: is the conjunction of these clauses satisfiable?

    We consider a variation of the problem where there is a bias towards variables occuring pure – i.e. variables occur negated w.p. 0<p<1/2 and pure otherwise – and study how the satisfiability threshold depends on p.

    For any fixed k, we find the asymptotics of the threshold as p approaches 0 or 1/2. The former confirms numerical studies.

  • 38.
    Larsson, Joel
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Polarized random k-SATManuskript (preprint) (Övrigt vetenskapligt)
    Abstract [en]

    We introduce a variation of the random k-SAT problem, which we call polarized random k-SAT. In polarized random k-SAT we have a polarization 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 k-SAT model.

    Of particular interest is the fully polarized model where p = 0. Here there are only two types of clauses: clauses where all k variables occur pure, and clauses where all k variables occur negated.

    We show that the threshold of satisfiability does not decrease as p moves away from 1. Thus the satisfiability threshold for polarized random k-SAT is an upper bound on the threshold for the classical random k-SAT. We also conjecture that the two thresholds coincide.

  • 39. Leader, Imre
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Uncountable families of vertex-transitive graphs of finite degree2006Ingår i: Discrete Mathematics, Vol. 306, nr 7, s. 678-679Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Recently the following question was relayed to the second author: What is the cardinality of the set of vertex transitive graphs of finite degree? Our aim in this short note is to show that there are $2^{\aleph_{0}}$ such graphs.

  • 40.
    Lo, Allan
    et al.
    Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands, England.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs2013Ingår i: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 22, nr 1, s. 97-111Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    A perfect Kt-matching in a graph G is a spanning subgraph consisting of vertex-disjoint copies of Kt A classic theorem of Hajnal and Szemerédi states that if G is a graph of order n with minimum degree δ(G) ≥(t - 1)n/t and t|n, then G contains a perfect Kt-matching. Let G be a t-partite graph with vertex classes V1, . . . , Vt each of size n. We show that, for any γ &gt; 0, if every vertex x ∈ Vi is joined to at least ((t - 1)/t + γ )n vertices of Vj for each j ≠ i, then G contains a perfect Kt-matching, provided n is large enough. Thus, we verify a conjecture of Fischer [6] asymptotically. Furthermore, we consider a generalization to hypergraphs in terms of the codegree.

  • 41. Lo, Allan
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    F-Factors in Hypergraphs Via Absorption2015Ingår i: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 31, nr 3, s. 679-712Artikel i tidskrift (Refereegranskat)
    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.

  • 42. Lo, Allan
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    l-Degree Turan Density2014Ingår i: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 28, nr 3, s. 1214-1225Artikel i tidskrift (Refereegranskat)
    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.

  • 43. Lo, Allan
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Minimum codegree threshold for (K-4(3)-e)-factors2013Ingår i: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 120, nr 3, s. 708-721Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Given hypergraphs H and F, an F-factor in H is a spanning subgraph consisting of vertex-disjoint copies of F. Let K-4(3) - e denote the 3-uniform hypergraph on 4 vertices with 3 edges. We Show that for any gamma > 0 there exists an integer n(0) such that every 3-uniform hypergraph H of order n > n(0) with minimum codegree at least (1/2 + gamma)n and 4 vertical bar n contains a (K-4(3) - e)-factor. Moreover, this bound is asymptotically the best possible and we further give a conjecture on the exact value of the threshold for the existence of a (K-4(3) - e)-factor. Thereby, all minimum codegree thresholds for the existence of F-factors are known asymptotically for 3-uniform hypergraphs F on 4 vertices. (C) 2012 Elsevier Inc. All rights reserved.

  • 44.
    Lo, Allan
    et al.
    Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands, England.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Perfect matchings in 3-partite 3-uniform hypergraphs2014Ingår i: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 127, s. 22-57Artikel i tidskrift (Refereegranskat)
    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.

  • 45. Lundow, P. H.
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Broken-cycle-free subgraphs and the log-concavity conjecture for chromatic polynomials2006Ingår i: Experimental Mathematics, ISSN 1058-6458, E-ISSN 1944-950X, Vol. 15, nr 3, s. 343-353Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    This paper concerns the coefficients of the chromatic polynomial of a graph. We first report on a computational verification of the strict log-concavity conjecture for chromatic polynomials for all graphs on at most 11 vertices, as well as for certain cubic graphs. In the second part of the paper we give a number of conjectures and theorems regarding the behavior of the coefficients of the chromatic polynomial, in part motivated by our computations. Here our focus is on epsilon(G), the average size of a broken-cycle-free subgraph of the graph G, whose behavior under edge deletion and contraction is studied.

  • 46. Lundow, P. H.
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Critical behavior of the Ising model on the four-dimensional cubic lattice2009Ingår i: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, E-ISSN 1550-2376, Vol. 80, nr 3, s. 031104-4 pagesArtikel i tidskrift (Refereegranskat)
    Abstract [en]

    In this paper we investigate the nature of the singularity of the Ising model of the four-dimensional cubic lattice. It is rigorously known that the specific heat has critical exponent alpha = 0 but a nonrigorous field-theory argument predicts an unbounded specific heat with a logarithmic singularity at T(c). We find that within the given accuracy the canonical ensemble data are consistent both with a logarithmic singularity and a bounded specific heat but that the microcanonical ensemble lends stronger support to a bounded specific heat. Our conclusion is that either much larger system sizes are needed for Monte Carlo studies of this model in four dimensions or the field-theory prediction of a logarithmic singularity is wrong.

  • 47. Lundow, P. H.
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Non-vanishing boundary effects and quasi-first-order phase transitions in high dimensional Ising models2011Ingår i: Nuclear Physics B, ISSN 0550-3213, E-ISSN 1873-1562, Vol. 845, nr 1, s. 120-139Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    In order to gain a better understanding of the Ising model in higher dimensions we have made a comparative study of how the boundary, open versus cyclic, of a d-dimensional simple lattice, for d = 1,...,5, affects the behaviour of the specific heat C and its microcanonical relative, the entropy derivative -partial derivative(2)S/partial derivative U(2). In dimensions 4 and 5 the boundary has a strong effect on the critical region of the model and for cyclic boundaries in dimension 5 we find that the model displays a quasi-first-order phase transition with a bimodal energy distribution. The latent heat decreases with increasing systems size but for all system sizes used in earlier papers the effect is clearly visible once a wide enough range of values for K is considered. Relations to recent rigorous results for high dimensional percolation and previous debates on simulation of Ising models and gauge fields are discussed. (C) 2010 Elsevier B.V. All rights reserved.

  • 48. Lundow, P. H.
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Rosengren, A.
    The Ising model for the bcc, fcc and diamond lattices: A comparison2009Ingår i: Philosophical Magazine, ISSN 1478-6435, E-ISSN 1478-6443, Vol. 89, nr 22-24, s. 2009-2042Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    A large-scale Monte Carlo simulation study of the Ising model for the simple cubic lattice was recently performed by us. In this paper, we complement that study with the bcc, fcc and diamond lattices. Both the canonical and microcanonical ensembles are employed. We give estimates of the critical temperature and also other quantities in the critical region. An analysis of the critical behaviour points to distinct high-and low-temperature exponents, especially for the specific heat, as was also obtained for the simple cubic lattice, although the agreement is good between the different lattices. The source of this discrepancy is briefly discussed.

  • 49.
    Lundow, Per-Håkan
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Complete graph asymptotics for the Ising and random-cluster models on five-dimensional grids with a cyclic boundary2015Ingår i: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, E-ISSN 1550-2376, Vol. 91, artikel-id 022112Artikel i tidskrift (Refereegranskat)
    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.

  • 50.
    Lundow, Per-Håkan
    et al.
    KTH Physics, AlbaNova University Center, SE-106 91 Stockholm, Sweden.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Exact and Approximate Compression of Transfer Matrices for Graph Homomorphisms2008Ingår i: LMS Journal of Computation and Mathematics, ISSN 1461-1570, E-ISSN 1461-1570, Vol. 11, s. 1-14Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    The aim of this paper is to extend the previous work on transfer matrix compression in the case of graph homomorphisms. For H-homomorphisms of lattice-like graphs we demonstrate how the automorphisms of H, as well as those of the underlying lattice, can be used to reduce the size of the relevant transfer matrices. As applications of this method we give currently best known bounds for the number of 4- and 5-colourings of the square grid, and the number of 3- and 4-colourings of the three-dimensional cubic lattice. Finally, we also discuss approximate compression of transfer matrices.

12 1 - 50 av 69
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf