Umeå University's logo

umu.sePublications
Change search
Refine search result
1 - 10 of 10
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)
  • Disputation date (earliest first)
  • Disputation date (latest 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)
  • Disputation date (earliest first)
  • Disputation date (latest 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. Andren, Lina J.
    et al.
    Casselgren, Carl Johan
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Restricted completion of sparse partial Latin squares2019In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 28, no 5, p. 675-695Article in journal (Refereed)
    Abstract [en]

    An n × n partial Latin square P is called α-dense if each row and column has at most αn non-empty cells and each symbol occurs at most αn times in P. An n × n array A where each cell contains a subset of {1,…, n} is a (βn, βn, βn)-array if each symbol occurs at most βn times in each row and column and each cell contains a set of size at most βn. Combining the notions of completing partial Latin squares and avoiding arrays, we prove that there are constants α, β > 0 such that, for every positive integer n, if P is an α-dense n × n partial Latin square, A is an n × n (βn, βn, βn)-array, and no cell of P contains a symbol that appears in the corresponding cell of A, then there is a completion of P that avoids A; that is, there is a Latin square L that agrees with P on every non-empty cell of P, and, for each i, j satisfying 1 ≤ i, j ≤ n, the symbol in position (i, j) in L does not appear in the corresponding cell of A.

  • 2.
    Andren, Lina J.
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Casselgren, Carl Johan
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Avoiding Arrays of Odd Order by Latin Squares2013In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 22, no 2, p. 184-212Article in journal (Refereed)
    Abstract [en]

    We prove that there is a constant c such that, for each positive integer k, every (2k + 1) x (2k + 1) array A on the symbols 1, ... , 2k + 1 with at most c(2k + 1) symbols in every cell, and each symbol repeated at most c(2k + 1) times in every row and column is avoidable; that is, there is a (2k + 1) x (2k + 1) Latin square S on the symbols 1, ... , 2k + 1 such that, for each i, j is an element of {1, ... , 2k + 1}, the symbol in position (i, j) of S does not appear in the corresponding cell in Lambda. This settles the last open case of a conjecture by Haggkvist. Using this result, we also show that there is a constant rho, such that, for any positive integer n, if each cell in an n x n array B is assigned a set of m <= rho n symbols, where each set is chosen independently and uniformly at random from {1, ... , n}, then the probability that B is avoidable tends to 1 as n -> infinity.

  • 3.
    Danielsson, Joel Larsson
    et al.
    Lund University, Lund, Sweden.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Polarised random κ-SAT2023In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 32, no 6, p. 885-899Article in journal (Refereed)
    Abstract [en]

    In this paper we study a variation of the random κ-SAT problem, called polarised random κ-SAT, which contains both the classical random κ-SAT model and the random version of monotone κ-SAT another well-known NP-complete version of SAT. In this model there is a polarisation parameter p, and in half of the clauses each variable occurs negated with probability p and pure otherwise, while in the other half the probabilities are interchanged. For p = 1/2 we get the classical random κ-SAT model, and at the other extreme we have the fully polarised model where p = 0, or 1. Here there are only two types of clauses: clauses where all κ variables occur pure, and clauses where all κ variables occur negated. That is, for p = 0, and p=1, we get an instance of random monotone κ-SAT. We show that the threshold of satisfiability does not decrease as p moves away from 1/2 and thus that the satisfiability threshold for polarised random κ-SAT with p ≠ 1/2 is an upper bound on the threshold for random κ-SAT. Hence the satisfiability threshold for random monotone κ-SAT is at least as large as for random κ-SAT, and we conjecture that asymptotically, for a fixed κ, the two thresholds coincide.

    Download full text (pdf)
    fulltext
  • 4.
    Day, A. Nicholas
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Falgas-Ravry, Victor
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Maker-Breaker percolation games I: crossing grids2021In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 30, no 2, p. 200-227Article in journal (Refereed)
    Abstract [en]

    Motivated by problems in percolation theory, we study the following two-player positional game. Let ?(mxn) be a rectangular grid-graph with m vertices in each row and n vertices in each column. Two players, Maker and Breaker, play in alternating turns. On each of her turns, Maker claims p (as yet unclaimed) edges of the board ?(mxn), while on each of his turns Breaker claims q (as yet unclaimed) edges of the board and destroys them. Maker wins the game if she manages to claim all the edges of a crossing path joining the left-hand side of the board to its right-hand side, otherwise Breaker wins. We call this game the (p, q)-crossing game on ?(mxn). Given m, n is an element of N, for which pairs (p, q) does Maker have a winning strategy for the (p, q)-crossing game on ?(mxn)? The (1, 1)-case corresponds exactly to the popular game of Bridg-it, which is well understood due to it being a special case of the older Shannon switching game. In this paper we study the general (p, q)-case. Our main result is to establish the following transition. If >= 2, then Maker wins the game on arbitrarily long versions of the narrowest board possible, that is, Maker has a winning strategy for the (2, )-crossing game on ?x(+1 for any is an element of N. pqqqmq)mIf p <= 2q - 1, then for every width n of the board, Breaker has a winning strategy for the (p, q)-crossing game on ?mxn for all sufficiently large board-lengths m. Our winning strategies in both cases adapt more generally to other grids and crossing games. In addition we pose many new questions and problems.

    Download full text (pdf)
    fulltext
  • 5.
    Falgas-Ravry, Victor
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Sperner's Problem for G-Independent Families2015In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 24, no 3, p. 528-550Article in journal (Refereed)
    Abstract [en]

    Given a graph G, let Q(G) denote the collection of all independent (edge-free) sets of vertices in G. We consider the problem of determining the size of a largest antichain in Q(G). When G is the edgeless graph, this problem is resolved by Sperner's theorem. In this paper, we focus on the case where G is the path of length n - 1, proving that the size of a maximal antichain is of the same order as the size of a largest layer of Q(G).

  • 6.
    Falgas-Ravry, Victor
    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.
    Zhao, Yi
    Triangle-degrees in graphs and tetrahedron coverings in 3-graphs2021In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 30, no 2, p. 175-199Article in journal (Refereed)
    Abstract [en]

    We investigate a covering problem in 3-uniform hypergraphs (3-graphs): Given a 3-graph F, what is c(1)(n, F), the least integer d such that if G is an n-vertex 3-graph with minimum vertex-degree delta(1)(G) > d then every vertex of G is contained in a copy of F in G?

    We asymptotically determine c(1)(n, F) when F is the generalized triangle K-4((3)), and we give close to optimal bounds in the case where F is the tetrahedron K-4((3)) (the complete 3-graph on 4 vertices).

    This latter problem turns out to be a special instance of the following problem for graphs: Given an nvertex graph G with m> n(2)/4 edges, what is the largest t such that some vertex in G must be contained in t triangles? We give upper bound constructions for this problem that we conjecture are asymptotically tight. We prove our conjecture for tripartite graphs, and use flag algebra computations to give some evidence of its truth in the general case.

    Download full text (pdf)
    fulltext
  • 7.
    Falgas-Ravry, Victor
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Vaughan, Emil R.
    Univ London, Sch Elect Engn & Comp Sci, London E1 4NS, England.
    Applications of the semi-definite method to the Turan density problem for 3-graphs2013In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 22, no 1, p. 21-54Article in journal (Refereed)
    Abstract [en]

    In this paper, we prove several new Turan density results for 3-graphs with independent neighbourhoods. We show: pi(K-4, C-5, F-3,F-2) = 12/49, pi(K-4, F-3,F-2) = 5/18 and pi(J(4), F-3,F-2) = pi(J(5), F-3,F-2) = 3/8, where J(t) is the 3-graph consisting of a single vertex x together with a disjoint set A of size t and all (vertical bar A vertical bar 2) 3-edges containing x. We also prove two Turan density results where we forbid certain induced subgraphs: pi(F-3,F-2, induced K-4(-)) = 3/8 and pi(K-5, 5-set spanning exactly 8 edges) = 3/4. The latter result is an analogue for K-5 of Razborov's result that pi(K-4, 4-set spanning exactly 1 edge) = 5/9. We give several new constructions, conjectures and bounds for Turan densities of 3-graphs which should be of interest to researchers in the area. Our main tool is 'Flagmatic', an implementation of Razborov's semi-definite method, which we are making publicly available. In a bid to make the power of Razborov's method more widely accessible, we have tried to make Flagmatic as user-friendly as possible, hoping to remove thereby the major hurdle that needs to be cleared before using the semi-definite method. Finally, we spend some time reflecting on the limitations of our approach, and in particular on which problems we may be unable to solve. Our discussion of the 'complexity barrier' for the semi-definite method may be of general interest.

  • 8.
    Häggkvist, Roland
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Johansson, Anders
    Orthogonal latin rectangles2008In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 17, no 4, p. 519-536Article in journal (Refereed)
    Abstract [en]

    We use a greedy probabilistic method to prove that, for every epsilon > 0, every m x n Latin rectangle on n symbols has an orthogonal mate, where m = (1 - epsilon)n. That is, we show the existence of a second Latin rectangle such that no pair of the mn cells receives the same pair of symbols in the two rectangles.

  • 9.
    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, p. 55-70Article 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.

  • 10.
    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, p. 97-111Article 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.

1 - 10 of 10
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