umu.sePublications
Change search
Refine search result
12 1 - 50 of 53
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the 'Create feeds' function.
  • 1. Aaghabali, M.
    et al.
    Akbari, S.
    Friedland, S.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Tajfirouz, Z.
    Upper bounds on the number of perfect matchings and directed 2-factors in graphs with given number of vertices and edges2015In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 45, 132-144 p.Article in journal (Refereed)
    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.
    Andren, Daniel
    et al.
    Umeå University, Faculty of Science and Technology, Mathematics and Mathematical Statistics.
    Hellström, Lars
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Mathematics and Mathematical Statistics.
    On the complexity of matrix reduction over finite fields2006Report (Other academic)
  • 3.
    Andren, Daniel
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    The bivariate ising polynomial of a graph2009In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 157, no 11, 2515-2524 p.Article in journal (Refereed)
    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.

  • 4.
    Andrén, Daniel
    et al.
    Umeå University, Faculty of Science and Technology, Mathematics and Mathematical Statistics.
    Hellström, Lars
    Umeå University, Faculty of Science and Technology, Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Mathematics and Mathematical Statistics.
    Fast multiplication of matrices over a finitely generated semiring2008In: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 107, no 6, 230-234 p.Article in journal (Refereed)
    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.

  • 5.
    Andrén, Daniel
    et al.
    Umeå University, Faculty of Science and Technology, Mathematics and Mathematical Statistics.
    Hellström, Lars
    Umeå University, Faculty of Science and Technology, Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Mathematics and Mathematical Statistics.
    On the complexity of matrix reduction over finite fields2007In: Advances in Applied Mathematics, ISSN 0196-8858, Vol. 39, no 4, 428-452 p.Article in journal (Refereed)
    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.

  • 6.
    Behndig, Anders
    et al.
    Umeå University, Faculty of Medicine, Department of Clinical Sciences, Ophthalmology.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Determination of the aqueous humor volume by three-dimensional mapping of the anterior chamber.2005In: Ophthalmic Research, ISSN 0030-3747, E-ISSN 1423-0259, Vol. 37, no 1, 13-16 p.Article in journal (Refereed)
    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.

  • 7. Brinkmann, Gunnar
    et al.
    Goedgebeur, Jan
    Hägglund, Jonas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Generation and properties of snarks2013In: Journal of combinatorial theory. Series B (Print), ISSN 0095-8956, E-ISSN 1096-0902, Vol. 103, no 4, 468-488 p.Article in journal (Refereed)
    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.

  • 8. Christofides, Demetres
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Random Latin square graphs2012In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 41, no 1, 47-65 p.Article in journal (Refereed)
    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

  • 9. Christofides, Demetres
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    The guessing number of undirected graph2011In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 18, no 1, P192- p.Article in journal (Refereed)
    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.

  • 10. Christofides, Demetres
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    The range of thresholds for diameter 2 in random Cayley graphs2014In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 35, 141-154 p.Article in journal (Refereed)
    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. 

  • 11.
    Christofides, Demetres
    et al.
    School of Computing and Mathematics, UCLan Cyprus, Pyla, Cyprus.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    The thresholds for diameter 2 in random Cayley graphs2014In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 45, no 2, 218-235 p.Article in journal (Refereed)
  • 12. Demetres, Christofides
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Mathematics and Mathematical Statistics.
    Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales2008In: Random Structures and Algorithms, ISSN 1042-9832, Vol. 32, no 1, 88-100 p.Article in journal (Refereed)
    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.

  • 13.
    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å University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On the Validations of the Asymptotic Matching Conjectures2008In: Journal of statistical physics, ISSN 0022-4715, E-ISSN 1572-9613, Vol. 133, no 3, 513-533 p.Article in journal (Refereed)
    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.

  • 14. Friedland, S.
    et al.
    Lundow, P. H.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    The 1-vertex transfer matrix and accurate estimation of channel capacity2010In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 57, no 8, 3692-3699 p.Article in journal (Refereed)
    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.

  • 15. Hamma, Alioscia
    et al.
    Markopoulou, Fotini
    Lloyd, Seth
    Caravelli, Francesco
    Severini, Simone
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Quantum bose-hubbard model with an evolving graph as a toy model for emergent spacetime2010In: Physical Review D. Particles and fields, ISSN 0556-2821, E-ISSN 1089-4918, Vol. 81, no 10, 104032-22 pages p.Article in journal (Refereed)
    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.

  • 16.
    Häggkvist, Roland
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Cycle double covers and spanning minors I2006In: Journal of combinatorial theory. Series B (Print), ISSN 0095-8956, E-ISSN 1096-0902, Vol. 96, no 2, 183-206 p.Article in journal (Refereed)
    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.

  • 17.
    Häggkvist, Roland
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Cycle double covers and spanning minors II2006In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 306, no 8-9, 762-778 p.Article in journal (Refereed)
    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].

  • 18.
    Häggkvist, Roland
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Rosengren, Anders
    Department of Physics, AlbaNova University Center, KTH, SE-106 91 Stockholm, Sweden.
    Andrén, Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    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å University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Computation of the Ising partition function for two-dimensional square grids2004In: 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, no 4, 19- p., 046104Article in journal (Refereed)
    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.

  • 19.
    Häggkvist, Roland
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Rosengren, Anders
    Department of Physics, AlbaNova University Center, KTH, SE-106 91, Stockholm, Sweden .
    Andrén, Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    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å University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    A Monte Carlo sampling scheme for the Ising model2004In: Journal of statistical physics, ISSN 0022-4715, E-ISSN 1572-9613, Vol. 114, no 1-2, 455-480 p.Article in journal (Refereed)
    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.

  • 20.
    Häggkvist, Roland
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Rosengren, Anders
    Lundow, Per Håkan
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Andrén, Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Kundrotas, P.
    On the Ising model for the simple cubic lattice2007In: Advances in Physics, ISSN 0001-8732, E-ISSN 1460-6976, Vol. 56, no 5, 653-755 p.Article, review/survey (Refereed)
    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.

  • 21.
    Hägglund, Jonas
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On stable cycles and cycle double covers of graphs with large circumference2012In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 312, no 17, 2540-2544 p.Article in journal (Refereed)
    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.

  • 22. Johansson, Anders
    et al.
    Johansson, Robert
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Factors of r-partite graphs and bounds for the strong chromatic number2010In: Ars combinatoria, ISSN 0381-7032, Vol. 95, 277-287 p.Article in journal (Refereed)
    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.

  • 23.
    Johnson, J. Robert
    et al.
    Queen Mary Univ London, Sch Math Sci, London E1 4NS, England.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Turán and Ramsey properties of subcube intersection graphs2013In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 22, no 1, 55-70 p.Article in journal (Refereed)
    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.

  • 24.
    Jonsson, Maria
    et al.
    Umeå University, Faculty of Medicine, Department of Clinical Sciences, Ophthalmology.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Behndig, Anders
    Umeå University, Faculty of Medicine, Department of Clinical Sciences, Ophthalmology.
    Slit-scan tomography evaluation of the anterior chamber and corneal configurations at different ages.2006In: Acta Ophthalmologica Scandinavica, ISSN 1395-3907, E-ISSN 1600-0420, Vol. 84, no 1, 116-120 p.Article in journal (Refereed)
    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.

  • 25. Leader, Imre
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Uncountable families of vertex-transitive graphs of finite degree2006In: Discrete Mathematics, Vol. 306, no 7, 678-679 p.Article in journal (Refereed)
    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.

  • 26.
    Lo, Allan
    et al.
    Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands, England.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs2013In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 22, no 1, 97-111 p.Article in journal (Refereed)
    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.

  • 27. Lo, Allan
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    F-Factors in Hypergraphs Via Absorption2015In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 31, no 3, 679-712 p.Article in journal (Refereed)
    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.

  • 28. Lo, Allan
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    l-Degree Turan Density2014In: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 28, no 3, 1214-1225 p.Article in journal (Refereed)
    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.

  • 29. Lo, Allan
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Minimum codegree threshold for (K-4(3)-e)-factors2013In: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 120, no 3, 708-721 p.Article in journal (Refereed)
    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.

  • 30.
    Lo, Allan
    et al.
    Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands, England.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Perfect matchings in 3-partite 3-uniform hypergraphs2014In: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 127, 22-57 p.Article in journal (Refereed)
    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.

  • 31. Lundow, P. H.
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Broken-cycle-free subgraphs and the log-concavity conjecture for chromatic polynomials2006In: Experimental Mathematics, ISSN 1058-6458, E-ISSN 1944-950X, Vol. 15, no 3, 343-353 p.Article in journal (Refereed)
    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.

  • 32. Lundow, P. H.
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Critical behavior of the Ising model on the four-dimensional cubic lattice2009In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, E-ISSN 1550-2376, Vol. 80, no 3, 031104-4 pages p.Article in journal (Refereed)
    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.

  • 33. Lundow, P. H.
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Non-vanishing boundary effects and quasi-first-order phase transitions in high dimensional Ising models2011In: Nuclear Physics B, ISSN 0550-3213, E-ISSN 1873-1562, Vol. 845, no 1, 120-139 p.Article in journal (Refereed)
    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.

  • 34. Lundow, P. H.
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Rosengren, A.
    The Ising model for the bcc, fcc and diamond lattices: A comparison2009In: Philosophical Magazine, ISSN 1478-6435, E-ISSN 1478-6443, Vol. 89, no 22-24, 2009-2042 p.Article in journal (Refereed)
    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.

  • 35.
    Lundow, Per-Håkan
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Complete graph asymptotics for the Ising and random-cluster models on five-dimensional grids with a cyclic boundary2015In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, E-ISSN 1550-2376, Vol. 91, 022112Article in journal (Refereed)
    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.

  • 36.
    Lundow, Per-Håkan
    et al.
    KTH Physics, AlbaNova University Center, SE-106 91 Stockholm, Sweden.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Exact and Approximate Compression of Transfer Matrices for Graph Homomorphisms2008In: LMS Journal of Computation and Mathematics, ISSN 1461-1570, E-ISSN 1461-1570, Vol. 11, 1-14 p.Article in journal (Refereed)
    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.

  • 37.
    Lundow, Per-Håkan
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Finite size scaling of the 5D Ising model with free boundary conditions2014In: Nuclear Physics B, ISSN 0550-3213, E-ISSN 1873-1562, Vol. 889, 249-260 p.Article in journal (Refereed)
    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.

  • 38.
    Lundow, Per-Håkan
    et al.
    Department of theoretical physics, AlbaNova University Center, KTH, SE-106 91 Stockholm, Sweden.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Reconstruction of the finite size canonical ensemble from incomplete micro-canonical data2009In: Central European Journal of Physics, ISSN 1895-1082, E-ISSN 1644-3608, Vol. 7, no 3, 490-502 p.Article in journal (Refereed)
    Abstract [en]

    In this paper we discuss how partial knowledge of the density of states for a model can be used to give good approximations of the energy distributions in a given temperature range. From these distributions one can then obtain the statistical moments corresponding to e. g. the internal energy and the specific heat. These questions have gained interest apropos of several recent methods for estimating the density of states of spin models. As a worked example we finally apply these methods to the 3-state Potts model for cubic lattices of linear order up to 128. We give estimates of e. g. latent heat and critical temperature, as well as the micro-canonical properties of interest.

  • 39.
    Lundow, Per-Håkan
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    The discontinuity of the specific heat for the 5D Ising model2015In: Nuclear Physics B, ISSN 0550-3213, E-ISSN 1873-1562, Vol. 895, 305-318 p.Article in journal (Refereed)
    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.

  • 40.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    A note on uniquely pancyclic graphs2009In: The Australasian Journal of Combinatorics, ISSN 1034-4942, Vol. 44, 105-110 p.Article in journal (Refereed)
    Abstract [en]

    In this paper we consider uniquely pancyclic graphs, ie n vertex graphs with exactly one cycle of each length from 3 to n. The first result of the paper gives new upper and lower bounds on the number of edges in a uniquely pancyclic graph. Next we report on a computer search for new uniquely pancyclic graphs. We found that there are no new such graphs on n ≤  59 vertices and that there are no uniquely pancyclic graphs with exactly 5 chords.

  • 41.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Closure properties and negatively associated measures violating the Van Den Berg-Kesten inequality2010In: Electronic Communications in Probability, ISSN 1083-589X, E-ISSN 1083-589X, Vol. 15, 449-456 p.Article in journal (Refereed)
    Abstract [en]

    We first give an example of a negatively associated measure which does not satisfy the van den Berg-Kesten inequality. Next we show that the class of measures satisfying the van den Berg-Kesten inequality is not closed under either of conditioning, introduction of external fields or convex combinations. Finally we show that this class also includes measure which have rank sequence which is not logconcave.

  • 42.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Complete minors in cubic graphs with few short cycles and random cubic graphs2004In: Ars combinatoria, ISSN 0381-7032, Vol. 70, 289-295 p.Article in journal (Refereed)
    Abstract [en]

    We first prove that for any fixed kappa a cubic graph with few short cycles contains a K-kappa-minor. This is a direct generalisation of a result on girth by Thomassen. We then use this theorem to show that for any fixed k a random cubic graph contains a Kk-minor asymptotically almost surely.

  • 43.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Even cycle decompositions of 4-regular graphs and line graphs2012In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 312, no 17, 2676-2681 p.Article in journal (Refereed)
    Abstract [en]

    An even cycle decomposition of a graph is a partition of its edge into even cycles. We first give some results on the existence of even cycle decomposition in general 4-regular graphs, showing that K 5 is not the only graph in this class without such a decomposition. Motivated by connections to the cycle double cover conjecture we go on to consider even cycle decompositions of line graphs of 2-connected cubic graphs. We conjecture that in this class even cycle decompositions always exists and prove the conjecture for cubic graphs with oddness at most 2. We also discuss even cycle double covers of cubic graphs.

  • 44.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Extremal hypergraphs and bounds for the Turan density of the 4-uniform K-52009In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 309, no 16, 5231-5234 p.Article in journal (Refereed)
    Abstract [en]

    In this paper we find, for n <= 16, the maximum number of edges in a 4-uniform hypergraph which does not have the complete 4-uniform hypergraph on five vertices, K-5(4), as a subgraph. Equivalently, we find all optimal (n, n-4, n-5) covering designs for n <= 16. Using these results we find a new upper bound for the Turin density of K-5(4). pi(K-5(4)) <= 1753/2380 = 0.73655.... Finally we make some notes on the structure of the extremal 4-graphs for this problem and the conjectured extremal family. (C) 2009 Published by Elsevier B.V.

  • 45.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Mathematics and Mathematical Statistics.
    Locality and hard SAT-instances2006In: Journal on Satisfiability, Boolean Modeling and Computation, Vol. 2Article in journal (Refereed)
    Abstract [en]

    In this note we construct a family of SAT-instance based on Eulerian graphs which are aimed at being hard for resolution based SAT-solvers. We discuss some experiments made with instances of this type and how a solver can try to avoid at least some of the pitfalls presented by these instances. Finally we look at how the density of subformulae can influence the hardness of SAT instances.

  • 46.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Negative association does not imply log-concavity of the rank sequence2007In: Journal of Applied Probability, ISSN 0021-9002, E-ISSN 1475-6072, Vol. 44, no 4, 1119-1121 p.Article in journal (Refereed)
    Abstract [en]

    We present a minimum counterexample to the conjecture that a negatively associated random variable has an ultra-log-concave rank sequence. The rank sequence does not in fact even need to be unimodal.

  • 47.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Two Questions of Erdos on Hypergraphs above the Turan Threshold2014In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 76, no 2, 101-105 p.Article in journal (Refereed)
    Abstract [en]

    For ordinary graphs it is known that any graph G with more edges than the Turan number of Ks must contain several copies of Ks, and a copy of Ks+1-, the complete graph on s+1 vertices with one missing edge. Erdos asked if the same result is true for Ks3, the complete 3-uniform hypergraph on s vertices. In this note, we show that for small values of n, the number of vertices in G, the answer is negative for s=4. For the second property, that of containing a Ks+13-, we show that for s=4 the answer is negative for all large n as well, by proving that the Turan density of K53- is greater than that of K43.

  • 48.
    Markström, Klas
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Rucinski, Andrzej
    Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees2011In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 32, no 5, 677-687 p.Article in journal (Refereed)
    Abstract [en]

    We establish a new lower bound on the l-wise collective minimum degree which guarantees the existence of a perfect matching in a k-uniform hypergraph, where 1 <= l < k/2. For l = 1, this improves a long-standing bound of Daykin and Haggkvist (1981) [5]. Our proof is a modification of the approach of Han et al. (2009) from [12]. In addition, we fill a gap left by the results solving a similar question for the existence of Hamilton cycles. (C) 2011 Published by Elsevier Ltd

  • 49.
    Markström, Klas
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Talbot, John
    On the density of 2-colorable 3-graphs in which any four points span at most two edges2010In: Journal of combinatorial designs (Print), ISSN 1063-8539, E-ISSN 1520-6610, Vol. 18, no 2, 105-114 p.Article in journal (Refereed)
    Abstract [en]

    Let ex(2) (n, kappa(-)(4)) be the maximum number of edges in a 2-colorable kappa(-)(4)-free 3-graph (where kappa(-)(4) ={123,124,134}). The 2-chromatic Turan density of kappa(-)(4) is pi(2)(kappa(-)(4))= lim(n ->infinity)ex(2)(n,kappa(-)(4))/ (n 3). We improve the previously best known lower and upper bounds of 0.25682 and 3/10-epsilon, respectively, by showing that 0.2572049 <= pi(2) (kappa(-)(4)) < 0.291. This implies the following new upper bound for the Turin density of kappa(-)(4) pi(kappa(-)(4)) <= 0.32908. In order to establish these results we use a combination of the properties of computer-generated extremal 3-graphs for small n and an argument based on "super-saturation". Our computer results determine the exact values of ex(n, kappa(-)(4)) for n <= 19 and ex(2)(n, kappa(-)(4)) for n <= 17, as well as the sets of extremal 3-graphs for those n. (C) 2009 Wiley Periodicals, Inc. J Combin Designs 18: 105-114, 2010

  • 50.
    Markström, Klas
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Thomason, Andrew
    Wagner, Peter
    Properly Edge-Coloured Subgraphs in Colourings of Bounded Degree2011In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 27, no 2, 243-249 p.Article in journal (Refereed)
    Abstract [en]

    The smallest n such that every colouring of the edges of K (n) must contain a monochromatic star K (1,s+1) or a properly edge-coloured K (t) is denoted by f (s, t). Its existence is guaranteed by the ErdAs-Rado Canonical Ramsey theorem and its value for large t was discussed by Alon, Jiang, Miller and Pritikin (Random Struct. Algorithms 23:409-433, 2003). In this note we primarily consider small values of t. We give the exact value of f (s, 3) for all s a parts per thousand yen 1 and the exact value of f (2, 4), as well as reducing the known upper bounds for f (s, 4) and f (s, t) in general.

12 1 - 50 of 53
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf