Umeå University's logo

umu.sePublications
Change search
Refine search result
1234 1 - 50 of 188
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. 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, p. 132-144Article 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. Akbari, Saieed
    et al.
    Friedland, Shmuel
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Zare, Sanaz
    On 1-sum flows in undirected graphs2016In: The Electronic Journal of Linear Algebra, ISSN 1537-9582, E-ISSN 1081-3810, Vol. 31, p. 646-665Article in journal (Refereed)
    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, 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.

  • 4.
    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.

  • 5.
    Andrén, Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On the Ising problem and some matrix operations2007Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    The first part of the dissertation concerns the Ising problem proposed to Ernst Ising by his supervisor Wilhelm Lenz in the early 20s. The Ising model, or perhaps more correctly the Lenz-Ising model, tries to capture the behaviour of phase transitions, i.e. how local rules of engagement can produce large scale behaviour.

    Two decades later Lars Onsager solved the Ising problem for the quadratic lattice without an outer field. Using his ideas solutions for other lattices in two dimensions have been constructed. We describe a method for calculating the Ising partition function for immense square grids, up to linear order 320 (i.e. 102400 vertices).

    In three dimensions however only a few results are known. One of the most important unanswered questions is at which temperature the Ising model has its phase transition. In this dissertation it is shown that an upper bound for the critical coupling Kc, the inverse absolute temperature, is 0.29 for the tree dimensional cubic lattice.

    To be able to get more information one has to use different statistical methods. We describe one sampling method that can use simple state generation like the Metropolis algorithm for large lattices. We also discuss how to reconstruct the entropy from the model, in order to obtain parameters as the free energy.

    The Ising model gives a partition function associated with all finite graphs. In this dissertation we show that a number of interesting graph invariants can be calculated from the coefficients of the Ising partition function. We also give some interesting observations about the partition function in general and show that there are, for any N, N non-isomorphic graphs with the same Ising partition function.

    The second part of the dissertation is about matrix operations. We consider the problem of multiplying them when the entries are elements in a finite semiring or in an additively finitely generated semiring. We describe a method that uses O(n3 / log n) arithmetic operations.

    We also consider the problem of reducing n x n matrices over a finite field of size q using O(n2 / logq n) row operations in the worst case.

    Download full text (pdf)
    FULLTEXT01
  • 6.
    Andrén, Daniel
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Hellström, Lars
    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 the complexity of matrix reduction over finite fields2007In: Advances in Applied Mathematics, ISSN 0196-8858, E-ISSN 1090-2074, Vol. 39, no 4, p. 428-452Article 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.

  • 7.
    Andrén, Lina J.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Avoidability by Latin squares of arrays of even orderManuscript (preprint) (Other academic)
    Abstract [en]

    We prove that for any k and any 2k × 2k array A such that no cell in A contains more than   k/2550 symbols, and no symbol occurs more than k/2550 times in any row or column, there is a Latin square such that no 2550cell in the Latin square contains a symbol that occurs in the corresponding cell in A. This proves a conjecture of Häggkvist [8] in the special case of arrays with even side.

  • 8.
    Andrén, Lina J.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Avoidability of random arraysManuscript (preprint) (Other academic)
    Abstract [en]

    An n×n array that in each cell contains a subset of the symbols 1, . . . , n is avoidable if there exists a Latin square of order n such that no cell in the Latin square contains a symbol which belongs to the set of symbols in the corresponding cell of the array. Some results on deterministic conditions for avoidability of arrays have been found, but here we study the problem of having an array with randomly assigned subsets of C in its cells. This is equivalent to the problem of list-edge-coloring  with randomly assigned lists from the set {1, . . . , n}. We show that an array where each symbol appears in each cell with probability p will be avoidable with very high probability even if p is such that the expected number of symbols forbidden in each cell is slightly higher than what deterministic theorems can prove is avoidable.

  • 9.
    Andrén, Lina J.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Avoiding (m, m, m)-arrays of order n = 2kManuscript (preprint) (Other academic)
    Abstract [en]

    An (m, m, m)-array of order n is an n × n array such that each cell is assigned a set of at most m symbols from {1,...,n} such that no symbol occurs more than m times in any row or column. An (m,m,m)- array is called avoidable if there exists a Latin square such that no cell in the Latin square contains a symbol that also belongs to the set assigned to the corresponding cell in the array. We show that there is a constant γ such that if m ≤ γ2k, then any (m,m,m)-array of order 2k is avoidable. Such a constant γ has been conjectured to exist for all n by Häggkvist.

  • 10.
    Andrén, Lina J.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On Latin squares and avoidable arrays2010Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    This thesis consists of the four papers listed below and a survey of the research area.

    I Lina J. Andrén: Avoiding (m, m, m)-arrays of order n = 2k

    II Lina J. Andrén: Avoidability of random arrays

    III Lina J. Andr´en: Avoidability by Latin squares of arrays with even order

    IV Lina J. Andrén, Carl Johan Casselgren and Lars-Daniel Öhman: Avoiding arrays of odd order by Latin squares

    Papers I, III and IV are all concerned with a conjecture by Häggkvist saying that there is a constant c such that for any positive integer n, if m ≤ cn, then for every n × n array A of subsets of {1, . . . , n} such that no cell contains a set of size greater than m, and none of the elements 1, . . . , n belongs to more than m of the sets in any row or any column of A, there is a Latin square L on the symbols 1, . . . , n such that there is no cell in L that contains a symbol that belongs to the set in the corresponding cell of A. Such a Latin square is said to avoid A. In Paper I, the conjecture is proved in the special case of order n = 2k . Paper III improves on the techniques of Paper I, expanding the proof to cover all arrays of even order. Finally, in Paper IV, similar methods are used together with a recoloring theorem to prove the conjecture for all orders. Paper II considers another aspect of the problem by asking to what extent way a deterministic result concerning the existence of Latin squares that avoid certain arrays can be used when the sets in the array are assigned randomly.

    Download full text (pdf)
    FULLTEXT01
  • 11.
    Andrén, Lina J.
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Casselgren, Carl Johan
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Avoiding arrays of odd order by Latin squaresManuscript (preprint) (Other academic)
    Abstract [en]

    We prove that there exists a constant c such that for each pos- itive integer k every (2k+1)×(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)×(2k+1) Latin square S on the symbols 1,...,2k+1 such that for each cell (i, j) in S the symbol in (i, j) does not appear in the corresponding cell in A. This settles the last open case of a conjecture by Häggkvist.

  • 12.
    Asratian, Armen S.
    et al.
    Linköping University, Linköping, Sweden.
    Casselgren, Carl Johan
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Vandenbussche, Jennifer
    Southern Polytechnic State University, Marietta, Georgia.
    West, Douglas B.
    University of Illinois, Urbana, Illinois.
    Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs2009In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 61, no 2, p. 88-97Article in journal (Refereed)
    Abstract [en]

    An interval coloring of a graph G is a proper coloring of E(G) by positive integers such that the colors on the edges incident to any vertex are consecutive. A (3,4)-biregular bigraph is a bipartite graph in which each vertex of one part has degree 3 and each vertex of the other has degree 4; it is unknown whether these all have interval colorings. We prove that G has an interval coloring using 6 colors when G is a (3,4)-biregular bigraph having a spanning subgraph whose components are paths with endpoints at 3-valent vertices and lengths in {2, 4, 6, 8}. We provide several sufficient conditions for the existence of such a subgraph.

  • 13.
    Bagan, Guillaume
    et al.
    Univ. Lyon, Université Lyon 1, Lyon, France.
    Deschamps, Quentin
    Univ. Lyon, Université Lyon 1, Lyon, France.
    Duchêne, Eric
    Univ. Lyon, Université Lyon 1, Lyon, France.
    Durain, Bastien
    École Normale Supérieure de Lyon, Lyon, France.
    Effantin, Brice
    Univ. Lyon, Université Lyon 1, Lyon, France.
    Gledel, Valentin
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Oijid, Nacim
    Univ. Lyon, Université Lyon 1, Lyon, France.
    Parreau, Aline
    Univ. Lyon, Université Lyon 1, Lyon, France.
    Incidence, a scoring positional game on graphs2023In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, article id 113570Article in journal (Refereed)
    Abstract [en]

    Positional games have been introduced by Hales and Jewett in 1963 and have been extensively investigated in the literature since then. These games are played on a hypergraph where two players alternately select an unclaimed vertex of it. In the Maker-Breaker convention, if Maker manages to fully take a hyperedge, she wins, otherwise, Breaker is the winner. In the Maker-Maker convention, the first player to take a hyperedge wins, and if no one manages to do it, the game ends by a draw. In both cases, the game stops as soon as Maker has taken a hyperedge. By definition, this family of games does not handle scores and cannot represent games in which players want to maximize a quantity. In this work, we introduce scoring positional games, that consist in playing on a hypergraph until all the vertices are claimed, and by defining the score as the number of hyperedges a player has fully taken. We focus here on INCIDENCE, a scoring positional game played on a 2-uniform hypergraph, i.e. an undirected graph. In this game, two players alternately claim the vertices of a graph and score the number of edges for which they own both end vertices. In the Maker-Breaker version, Maker aims at maximizing the number of edges she owns, while Breaker aims at minimizing it. In the Maker-Maker version, both players try to take more edges than their opponent. We first give some general results on scoring positional games such that their membership in Milnor's universe and some general bounds on the score. We prove that, surprisingly, computing the score in the Maker-Breaker version of INCIDENCE is PSPACE-complete whereas in the Maker-Maker convention, the relative score can be obtained in polynomial time. In addition, for the Maker-Breaker convention, we give a formula for the score on paths by using some equivalences due to Milnor's universe. This result implies that the score on cycles can also be computed in polynomial time.

    Download full text (pdf)
    fulltext
  • 14.
    Baltz, Andreas
    et al.
    Christian-Albrechts Universität Kiel.
    El Ouali, Mourad
    Christian-Albrechts Universität Kiel.
    Jäger, Gerold
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Sauerland, Volkmar
    Christian-Albrechts Universität Kiel.
    Srivastav, Anand
    Christian-Albrechts Universität Kiel.
    Exact and heuristic algorithms for the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection2015In: Journal of the Operational Research Society, ISSN 0160-5682, E-ISSN 1476-9360, Vol. 66, no 4, p. 615-626Article in journal (Refereed)
    Abstract [en]

    We introduce and study the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection (TSP-MTWHS), which generalises the well-known Travelling Salesman Problem with Time Windows and the recently introduced Travelling Salesman Problem with Hotel Selection. The TSP-MTWHS consists in determining a route for a salesman (eg, an employee of a services company) who visits various customers at different locations and different time windows. The salesman may require a several-day tour during which he may need to stay in hotels. The goal is to minimise the tour costs consisting of wage, hotel costs, travelling expenses and penalty fees for possibly omitted customers. We present a mixed integer linear programming (MILP) model for this practical problem and a heuristic combining cheapest insert, 2-OPT and randomised restarting. We show on random instances and on real world instances from industry that the MILP model can be solved to optimality in reasonable time with a standard MILP solver for several small instances. We also show that the heuristic gives the same solutions for most of the small instances, and is also fast, efficient and practical for large instances.

  • 15.
    Baltz, Andreas
    et al.
    Christian-Albrechts Universität Kiel, Germany.
    Jäger, Gerold
    Christian-Albrechts Universität Kiel, Germany.
    Srivastav, Anand
    Christian-Albrechts Universität Kiel, Germany.
    Construction of Sparse Asymmetric Connectors2003In: Proceedings of European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2003), 2003Conference paper (Refereed)
  • 16.
    Baltz, Andreas
    et al.
    Christian-Albrechts-Universität Kiel, Germany.
    Jäger, Gerold
    Christian-Albrechts-Universität Kiel, Germany.
    Srivastav, Anand
    Christian-Albrechts-Universität Kiel, Germany.
    Constructions of Sparse Asymmetric Connectors2003In: Proceedings of 23rd Conference of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2003) / [ed] P.K. Lodaya and J. Radhakrishnan, Berlin-Heidelberg: Springer Berlin/Heidelberg, 2003, p. 13-22Conference paper (Refereed)
  • 17.
    Baltz, Andreas
    et al.
    Mathematisches seminar, Christian-Albrechts-Universität zu Kiel, Germany.
    Jäger, Gerold
    Mathematisches seminar, Christian-Albrechts-Universität zu Kiel, Germany.
    Srivastav, Anand
    Mathematisches seminar, Christian-Albrechts-Universität zu Kiel, Germany.
    Constructions of Sparse Asymmetric Connectors with Number Theoretic Methods2005In: Networks, ISSN 0028-3045, E-ISSN 1097-0037, Vol. 45, no 3, p. 119-124Article in journal (Refereed)
    Abstract [en]

    We consider the problem of connecting a set I of n inputs to a set O of N outputs (n ≤ N) by as few edges as possible such that for every injective mapping f : I → O there are n vertex disjoint paths from i to f(i) of length k for a given k . For k = Ω(log N + logn) Oruς (1994) gave the presently best (n,N)-connector with O(N+n·log n) edges. For k=2 and N the square of a prime, Richards and Hwang (1985) described a construction using edges. We show by a probabilistic argument that an optimal (n,N)-connector has Θ (N) edges, if for some ε>0. Moreover, we give explicit constructions based on a new number theoretic approach that need at most edges for arbitrary choices of n and N. The improvement we achieve is based on applying a generalization of the Erdös-Heilbronn conjecture on the size of restricted sums.

  • 18.
    Behrstock, Jason
    et al.
    Department of Mathematics, Lehman College and The Graduate Center, CUNY, NY, New York, United States.
    Falgas-Ravry, Victor
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Susse, Tim
    Division of Science, Math and Computing, Bard College at Simon's Rock, MA, Great Barrington, United States.
    Square percolation and the threshold for quadratic divergence in random right-angled Coxeter groups2022In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 60, no 4, p. 594-630Article in journal (Refereed)
    Abstract [en]

    Given a graph (Formula presented.), its auxiliary square-graph (Formula presented.) is the graph whose vertices are the non-edges of (Formula presented.) and whose edges are the pairs of non-edges which induce a square (i.e., a 4-cycle) in (Formula presented.). We determine the threshold edge-probability (Formula presented.) at which the Erdős–Rényi random graph (Formula presented.) begins to asymptotically almost surely (a.a.s.) have a square-graph with a connected component whose squares together cover all the vertices of (Formula presented.). We show (Formula presented.), a polylogarithmic improvement on earlier bounds on (Formula presented.) due to Hagen and the authors. As a corollary, we determine the threshold (Formula presented.) at which the random right-angled Coxeter group (Formula presented.) a.a.s. becomes strongly algebraically thick of order 1 and has quadratic divergence.

  • 19.
    Björklund, Johanna
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    The impact of state merging on predictive accuracy in probabilistic tree automata: Dietze’s conjecture revisited2023In: Fundamentals of computation theory: 24th International Symposium, FCT 2023, Trier, Germany, September 18–21, 2023, Proceedings / [ed] Henning Fernau; Klaus Jansen, Springer Nature, 2023, p. 74-87Conference paper (Refereed)
    Abstract [en]

    Dietze’s conjecture concerns the problem of equipping a tree automaton M with weights to make it probabilistic, in such a way that the resulting automaton N predicts a given corpus C as accurately as possible. The conjecture states that the accuracy cannot increase if the states in M are merged with respect to an equivalence relation ∼ so that the result is a smaller automaton M∼. Put differently, merging states can never improve predictions. This is under the assumption that both M and M∼ are bottom-up deterministic and accept every tree in C. We prove that the conjecture holds, using a construction that turns any probabilistic version N∼ of M∼ into a probabilistic version N of M, such that N assigns at least as great a weight to each tree in C as N∼ does.

  • 20.
    Björklund, Johanna
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Cleophas, Loek
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Department of Information Science, Stellenbosch University, Stellenbosch, South Africa.
    Minimization of Finite State Automata Through Partition Aggregation2016In: Logical Aspects of Computational Linguistics: Celebrating 20 Years of LACL (1996–2016) / [ed] Amblard, M DeGroote, P Pogodalla, S Retore, C, SPRINGER-VERLAG BERLIN , 2016, p. 328-328Conference paper (Refereed)
  • 21. Brignall, Robert
    et al.
    Sliacan, Jakub
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Combinatorial specifications for juxtapositions of permutation classes2019In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 26, no 4, article id P4.4Article in journal (Refereed)
    Abstract [en]

    We show that, given a suitable combinatorial specification for a permutation class C, one can obtain a specification for the juxtaposition (on either side) of C with Av(21) or Av(12), and that if the enumeration for C is given by a rational or algebraic generating function, so is the enumeration for the juxtaposition. Furthermore this process can be iterated, thereby providing an effective method to enumerate any 'skinny' k x 1 grid class in which at most one cell is non-monotone, with a guarantee on the nature of the enumeration given the nature of the enumeration of the non-monotone cell.

    Download full text (pdf)
    fulltext
  • 22.
    Casselgren, Carl Johan
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On avoiding some families of arrays2012In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 312, no 5, p. 963-972Article in journal (Refereed)
    Abstract [en]

    An n×n array A with entries from {1,…,n} is avoidable if there is an n×n Latin square L such that no cell in L contains a symbol that occurs in the corresponding cell in A. We show that the problem of determining whether an array that contains at most two entries per cell is avoidable is NP-complete, even in the case when the array has entries from only two distinct symbols. Assuming that PNP, this disproves a conjecture by Öhman. Furthermore, we present several new families of avoidable arrays. In particular, every single entry array (arrays where each cell contains at most one symbol) of order n≥2k with entries from at most k distinct symbols and where each symbol occurs in at most n−2 cells is avoidable, and every single entry array of order n, where each of the symbols 1,…,n occurs in at most cells, is avoidable. Additionally, if k≥2, then every single entry array of order at least n≥4, where at most k rows contain non-empty cells and where each symbol occurs in at most nk+1 cells, is avoidable.

    Download full text (pdf)
    On avoiding some families of arrays
  • 23.
    Casselgren, Carl Johan
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On some graph coloring problems2011Doctoral thesis, comprehensive summary (Other academic)
    Download full text (pdf)
    FULLTEXT01
  • 24. Casselgren, Carl Johan
    et al.
    Häggkvist, Roland
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Coloring Complete and Complete Bipartite Graphs from Random Lists2016In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 32, no 2, p. 533-542Article in journal (Refereed)
    Abstract [en]

    Assign to each vertex v of the complete graph on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set , where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as ) of the existence of a proper coloring of , such that for every vertex v of . We show that this property exhibits a sharp threshold at . Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph with parts of size m and n, respectively. We show that if , , and L is a random (f(n), [n])-list assignment for the line graph of , then with probability tending to 1, as , there is a proper coloring of the line graph of with colors from the lists.

  • 25. Casselgren, Carl Johan
    et al.
    Häggkvist, Roland
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Completing partial Latin squares with one filled row, column and symbol2013In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 313, no 9, p. 1011-1017Article in journal (Refereed)
    Abstract [en]

    Let P be an n x n partial Latin square every non-empty cell of which lies in a fixed row r, a fixed column c or contains a fixed symbols. Assume further that s is the symbol of cell (r, c) in P. We prove that P is completable to a Latin square if n >= 8 and n is divisible by 4, or n <= 7 and n is not an element of {3, 4, 5}. Moreover, we present a polynomial algorithm for the completion of such a partial Latin square. (C) 2013 Elsevier B.V. All rights reserved.

  • 26.
    Casselgren, Carl Johan
    et al.
    Department of Mathematics, Linköping University, Linköping, Sweden.
    Johansson, Per
    Department of Mathematics, Linköping University, Linköping, Sweden.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Avoiding and Extending Partial Edge Colorings of Hypercubes2022In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 38, no 3, article id 79Article in journal (Refereed)
    Abstract [en]

    We consider the problem of extending and avoiding partial edge colorings of hypercubes; that is, given a partial edge coloring φ of the d-dimensional hypercube Qd, we are interested in whether there is a proper d-edge coloring of Qd that agrees with the coloring φ on every edge that is colored under φ; or, similarly, if there is a proper d-edge coloring that disagrees with φ on every edge that is colored under φ. In particular, we prove that for any d≥ 1 , if φ is a partial d-edge coloring of Qd, then φ is avoidable if every color appears on at most d/8 edges and the coloring satisfies a relatively mild structural condition, or φ is proper and every color appears on at most d- 2 edges. We also show that φ is avoidable if d is divisible by 3 and every color class of φ is an induced matching. Moreover, for all 1 ≤ k≤ d, we characterize for which configurations consisting of a partial coloring φ of d- k edges and a partial coloring ψ of k edges, there is an extension of φ that avoids ψ.

    Download full text (pdf)
    fulltext
  • 27. Casselgren, Carl Johan
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Pham, Lan Anh
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Edge precoloring extension of hypercubes2020In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 95, no 3, p. 410-444Article in journal (Refereed)
    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.

    Download full text (pdf)
    fulltext
  • 28. Casselgren, Carl Johan
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Pham, Lan Anh
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Latin cubes with forbidden entries2019In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 26, no 1, article id P1.2Article in journal (Refereed)
    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. 

    Download full text (pdf)
    fulltext
  • 29. Casselgren, Carl Johan
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Pham, Lan Anh
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Restricted extension of sparse partial edge colorings of hypercubesManuscript (preprint) (Other academic)
    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.

  • 30. Casselgren, Carl Johan
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Pham, Lan Anh
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Restricted extension of sparse partial edge colorings of hypercubes2020In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 343, no 11, article id 112033Article in journal (Refereed)
    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. (C) 2020 Elsevier B.V. All rights reserved.

  • 31. Casselgren, Carl Johan
    et al.
    Pham, Lan Anh
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Latin cubes of even order with forbidden entriesManuscript (preprint) (Other academic)
    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 γ>0 such that if n=2t 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.

  • 32. Casselgren, Carl Johan
    et al.
    Pham, Lan Anh
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Latin cubes of even order with forbidden entries2020In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 85, article id 103045Article in journal (Refereed)
    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 gamma > 0 such that if n is even and A is a 3-dimensional n x n x n array where every cell contains at most gamma n symbols, and every symbol occurs at most gamma 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 i, j, k is an element of {1, ..., n}, the symbol in position (i, j, k) of L does not appear in the corresponding cell of A.

  • 33.
    Casselgren, Carl Johan
    et al.
    Department of Mathematics, Linköping University, Linköping, Sweden.
    Pham, Lan Anh
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Restricted extension of sparse partial edge colorings of complete graphs2021In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 28, no 2, article id P2.8Article in journal (Refereed)
    Abstract [en]

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

    Download full text (pdf)
    fulltext
  • 34. Chen, Guantao
    et al.
    van der Holst, Hein
    Kostochka, Alexandr
    Li, Nana
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    Extremal Union-Closed Set Families2019In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 35, no 6, p. 1495-1502Article in journal (Refereed)
    Abstract [en]

    A family of finite sets is called union-closed if it contains the union of any two sets in it. The Union-Closed Sets Conjecture of Frankl from 1979 states that each union-closed family contains an element that belongs to at least half of the members of the family. In this paper, we study structural properties of union-closed families. It is known that under the inclusion relation, every union-closed family forms a lattice. We call two union-closed families isomorphic if their corresponding lattices are isomorphic. Let F be a union-closed family and boolean OR(F is an element of F) F be the universe of F. Among all union-closed families isomorphic to F, we develop an algorithm to find one with a maximum universe, and an algorithm to find one with a minimum universe. We also study properties of these two extremal union-closed families in connection with the Union-Closed Set Conjecture. More specifically, a lower bound of sizes of sets of a minimum counterexample to the dual version of the Union-Closed Sets Conjecture is obtained.

  • 35.
    Cherkashin, Danila
    et al.
    Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, 8 Acad. G. Bonchev Str., Sofia, Bulgaria.
    Gordeev, Alexey
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics. The Euler International Mathematical Institute, St. Petersburg, Russian Federation.
    Strukov, Georgii
    The Euler International Mathematical Institute, St. Petersburg, Russian Federation.
    Erdős–hajnal problem for h-free hypergraphs2024In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 40, no 1, article id 10Article in journal (Refereed)
    Abstract [en]

    This paper deals with the minimum number mH(r) of edges in an H-free hypergraph with the chromatic number more than r. We show how bounds on Ramsey and Turán numbers imply bounds on mH(r) .

  • 36.
    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, p. 218-235Article 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. 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.

  • 37.
    Cutler, Jonathan
    et al.
    Umeå University, Faculty of Science and Technology, Department of mathematics. Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, USA.
    Montagh, Balazs
    Unavoidable subgraphs of colored graphs2008In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 308, no 19, p. 4396-4413Article in journal (Refereed)
    Abstract [en]

    A natural generalization of graph Ramsey theory is the study of unavoidable sub-graphs in large colored graphs. In this paper. we find a minimal family of unavoidable graphs in two-edge-colored graphs. Namely, for a positive even integer k, let y(k) be the family of two-edge-colored graphs on k vertices such that one of the colors forms either two disjoint K-k/2's or simply one K-k/2. Bollobas conjectured that for all k and epsilon > 0, there exists an n(k, epsilon) such that if n >= n(k, epsilon) then every two-edge-coloring of K-n, in which the density of each color is at least epsilon, contains a member of this family. We solve this conjecture and present a series of results bounding it (k, s) for different ranges of epsilon. In particular, if epsilon is sufficiently close to 1/2, the gap between out upper and lower bounds for n(k, epsilon) is smaller than those for the classical Ramsey number R(k, k).

  • 38. Cutler, Jonathan
    et al.
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Latin squares with forbidden entries2004Report (Other academic)
  • 39.
    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
  • 40.
    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
  • 41.
    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 II: Escaping to infinity2021In: Journal of combinatorial theory. Series B (Print), ISSN 0095-8956, E-ISSN 1096-0902, Vol. 151, p. 482-508Article in journal (Refereed)
    Abstract [en]

    Let Lambda be an infinite connected graph, and let v(0) be a vertex of Lambda. We consider the following positional game. Two players, Maker and Breaker, play in alternating turns. Initially all edges of Lambda are marked as unsafe. On each of her turns, Maker marks p unsafe edges as safe, while on each of his turns Breaker takes q unsafe edges and deletes them from the graph. Breaker wins if at any time in the game the component containing v(0) becomes finite. Otherwise if Maker is able to ensure that v(0) remains in an infinite component indefinitely, then we say she has a winning strategy. This game can be thought of as a variant of the celebrated Shannon switching game. Given (p, q) and (Lambda, v(0)), we would like to know: which of the two players has a winning strategy?

    Our main result in this paper establishes that when Lambda = Z(2) and v(0) is any vertex, Maker has a winning strategy whenever p >= 2q, while Breaker has a winning strategy whenever 2p <= q. In addition, we completely determine which of the two players has a winning strategy for every pair (p, q) when Lambda is an infinite d -regular tree. Finally, we give some results for general graphs and lattices and pose some open problems. (C) 2020 Elsevier Inc. All rights reserved.

  • 42.
    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.
    Treglown, Andrew
    University of Birmingham, Birmingham, United Kingdom.
    Extremal problems for multigraphs2022In: Journal of combinatorial theory. Series B (Print), ISSN 0095-8956, E-ISSN 1096-0902, Vol. 154, p. 1-48Article in journal (Refereed)
    Abstract [en]

    An (n,s,q)-graph is an n-vertex multigraph in which every s-set of vertices spans at most q edges. Turán-type questions on the maximum of the sum of the edge multiplicities in such multigraphs have been studied since the 1990s. More recently, Mubayi and Terry (2019) [13] posed the problem of determining the maximum of the product of the edge multiplicities in (n,s,q)-graphs. We give a general lower bound construction for this problem for many pairs (s,q), which we conjecture is asymptotically best possible. We prove various general cases of our conjecture, and in particular we settle a conjecture of Mubayi and Terry on the (s,q)=(4,6a+3) case of the problem (for a≥2); this in turn answers a question of Alon. We also determine the asymptotic behaviour of the problem for ‘sparse’ multigraphs (i.e. when q≤2(s2)). Finally we introduce some tools that are likely to be useful for attacking the problem in general.

  • 43.
    Day, A. Nicholas
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Lo, Allan
    University of Birmingham, Birmingham, United Kingdom.
    Upper density of monochromatic paths in edge-coloured infinite complete graphs and bipartite graphs2023In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 110, article id 103625Article in journal (Refereed)
    Abstract [en]

    The upper density of an infinite graph G with V(G)⊆N is defined as d¯(G)=lim supn→∞|V(G)∩{1,…,n}|/n. Let KN be the infinite complete graph with vertex set N. Corsten, DeBiasio, Lamaison and Lang showed that in every 2-edge-colouring of KN, there exists a monochromatic path with upper density at least (12+8)/17, which is best possible. In this paper, we extend this result to k-edge-colouring of KN for k≥3. We conjecture that every k-edge-coloured KN contains a monochromatic path with upper density at least 1/(k−1), which is best possible (when k−1 is a prime power). We prove that this is true when k=3 and asymptotically when k=4. Furthermore, we show that this problem can be deduced from its bipartite variant, which is of independent interest.

  • 44.
    Day, A. Nicholas
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Sarkar, Amites
    Department of Mathematics, Western Washington University, WA, Bellingham, United States.
    On a Conjecture of Nagy on Extremal Densities2021In: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 35, no 1, p. 294-306Article in journal (Refereed)
    Abstract [en]

    We disprove a conjecture of Nagy on the maximum number of copies N(G, H) of a_xed graph G in a large graph H with prescribed edge density. Nagy conjectured that for all G, the quantity N(G, H) is asymptotically maximized by either a quasi-star or a quasi-clique. We show this is false for in_nitely many graphs, the smallest of which has six vertices and six edges. We also propose some new conjectures for the behavior of N(G, H) and present some evidence for them.

  • 45. Demetres, Christofides
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales2008In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 32, no 1, p. 88-100Article 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.

  • 46.
    Denley, Tristan
    et al.
    Austin Peay State University.
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Extending partial latin cubes2014In: Ars combinatoria, ISSN 0381-7032, Vol. 113, p. 405-414Article in journal (Refereed)
    Abstract [en]

    In the spirit of Ryser's theorem, we prove sufficient conditions on k, and m so that k xexm Latin boxes, i.e. partial Latin cubes whose filled cells form a k x x m rectangular box, can be extended to akxnxm latin box, and also to akxnxn latin box, where n is the number of symbols used, and likewise the order of the Latin cube. We also prove a partial Evans type result for Latin cubes, namely that any partial Latin cube of order n with at most n 1 filled cells is completable, given certain conditions on the spatial distribution of the filled cells.

  • 47.
    Dong, Changxing
    et al.
    Computer Science Institute, University of Halle Wittenberg, Germany .
    Ernst, Christian
    Computer Science Institute, University of Halle Wittenberg, Germany .
    Jäger, Gerold
    Computer Science Institute, University of Halle Wittenberg, Germany .
    Richter, Dirk
    Computer Science Institute, University of Halle Wittenberg, Germany .
    Molitor, Paul
    Computer Science Institute, University of Halle Wittenberg, Germany .
    Effective Heuristics for Large Euclidean TSP Instances Based on Pseudo Backbones2009In: Proceedings of 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2009) / [ed] Sonia Cafieri, Antonio Mucherino, Giacomo Nannicini, Fabien Tarissan and Leo Liberti, 2009, p. 3-6Conference paper (Refereed)
    Abstract [en]

    We present two approaches for the Euclidean TSP which compute high quality tours for large instances. Both approaches are based on pseudo backbones consisting of all common edges of good tours. The first approach starts with some pre-computed good tours. Using this approach we found record tours for seven VLSI instances. The second approach is window based and constructs from scratch very good tours of huge TSPinstances, e. g., the World TSP.

  • 48.
    Dong, Changxing
    et al.
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Jäger, Gerold
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Richter, Dirk
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Molitor, Paul
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Effective Tour Searching for TSP by Contraction of Pseudo Backbone Edges2009In: Proceedings of 5th International Conference on Algorithmic Aspects in Information and Management (AAIM 2009) / [ed] A. Goldberg and Y. Zhou, Berlin-Heidelberg: Springer , 2009, p. 175-187Conference paper (Refereed)
    Abstract [en]

    We introduce a reduction technique for the well-known TSP. The basic idea of the approach consists of transforming a TSP instance to another one with smaller size by contracting pseudo backbone edges computed in a preprocessing step, where pseudo backbone edges are edges which are likely to be in an optimal tour. A tour of the small instance can be re-transformed to a tour of the original instance. We experimentally investigated TSP benchmark instances by our reduction technique combined with the currently leading TSP heuristic of Helsgaun. The results strongly demonstrate the effectivity of this reduction technique: for the six VLSI instances xvb13584, pjh17845, fnc19402, ido21215, boa28924, and fht47608 we could set world records, i.e., find better tours than the effective reduction of the problem size so that we can search the more important tour subspace more intensively.

  • 49.
    El Ouali, Mourad
    et al.
    Computer Science Institute, Christian-Albrechts-University of Kiel, Germany.
    Jäger, Gerold
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    The b-Matching Problem in Hypergraphs: Hardness and Approximability2012In: COCOA 2012: Combinatorial Optimization and Applications / [ed] Guohui Lin, Berlin-Heidelberg: Springer Berlin-Heidelberg , 2012, p. 200-211Conference paper (Refereed)
    Abstract [en]

    In this paper we analyze the maximum cardinality b-matching problem in l-uniform hypergraphs with respect to the complexity class Max-Snp, where b-matching is defined as follows: for given b ∈ ℕ and a hypergraph H=(V,E)" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">H=(V,E)H=(V,E) a subset Mb&#x2286;E" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">Mb⊆EMb⊆E with maximum cardinality is sought so that no vertex is contained in more than b hyperedges of M b . We show that if the maximum degree of the vertices is bounded by a constant B ∈ ℕ , this problem has no approximation scheme, unless P=NP" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">P=NPP=NP. This result generalizes a result of Kann from b = 1 to the case that b ∈ ℕ with 0&lt;b&#x2264;B3" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">0<b≤B30<b≤B3. Furthermore, we extend a result of Srivastav and Stangier, who gave an approximation algorithm for the unweighted b-matching problem.

  • 50.
    Ernst, Christian
    et al.
    Martin-Luther-University Halle-Wittenberg, Germany and GISA GmbH, D-06112 Halle (Saale), Germany.
    Dong, Changxing
    Martin-Luther-University Halle-Wittenberg, Germany.
    Jäger, Gerold
    Martin-Luther-University Halle-Wittenberg, Germany and Christian-Albrechts-University Kiel, Germany.
    Richter, Dirk
    Martin-Luther-University Halle-Wittenberg, Germany.
    Molitor, Paul
    Martin-Luther-University Halle-Wittenberg, Germany.
    Finding Good Tours for Huge Euclidean TSP Instances by Iterative Backbone Contraction2010In: Proceedings of 6th International Conference on Algorithmic Aspects in Information and Management (AAIM 2010) / [ed] B. Chen, Berlin-Heidelberg: Springer , 2010, Vol. 6124, p. 119-130Conference paper (Refereed)
    Abstract [en]

    This paper presents an iterative, highly parallelizable approach to find good tours for very large instances of the Euclidian version of the well-known Traveling Salesman Problem (TSP). The basic idea of the approach consists of iteratively transforming the TSP instance to another one with smaller size by contracting pseudo backbone edges. The iteration is stopped, if the new TSP instance is small enough for directly applying an exact algorithm or an efficient TSP heuristic. The pseudo backbone edges of each iteration are computed by a window based technique in which the TSP instance is tiled in non-disjoint sub-instances. For each of these sub-instances a good tour is computed, independently of the other sub-instances. An edge which is contained in the computed tour of every sub-instance (of the current iteration) containing this edge is denoted to be a pseudo backbone edge. Paths of pseudo-backbone edges are contracted to single edges which are fixed during the subsequent process.

1234 1 - 50 of 188
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