| 1. |
|
|
| 2. |
- Andrén, Lina, et al.
(författare)
-
Restricted completion of sparse partial Latin squares
- 2019
-
Ingår i: Combinatorics, probability & computing. - : Cambridge University Press. - 0963-5483 .- 1469-2163. ; 28:5, s. 675-695
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 3. |
- Casselgren, Carl Johan, et al.
(författare)
-
Edge precoloring extension of hypercubes
- 2020
-
Ingår i: Journal of Graph Theory. - : John Wiley & Sons. - 0364-9024 .- 1097-0118. ; 95:3, s. 410-444
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 4. |
- Andrén, Daniel, 1973-, et al.
(författare)
-
On the complexity of matrix reduction over finite fields
- 2007
-
Ingår i: Advances in Applied Mathematics. - : Academic Press. - 0196-8858 .- 1090-2074. ; 39:4, s. 428-452
-
Tidskriftsartikel (refereegranskat)abstract
- 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$ smallFinally 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.
|
|
| 5. |
- Lundow, Per Håkan, et al.
(författare)
-
EXACT AND APPROXIMATE COMPRESSION OF TRANSFER MATRICES FOR GRAPH HOMOMORPHISMS
- 2008
-
Ingår i: LMS Journal of Computation and Mathematics. - : Cambridge University Press. - 1461-1570. ; 11, s. 1-14
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 6. |
- Burghart, Fabian, 1996-
(författare)
-
Building and Destroying Urns, Graphs, and Trees
- 2023
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In this thesis, consisting of an introduction and four papers, different models in the mathematical area of combinatorial probability are investigated.In Paper I, two operations for combining generalised Pólya urns, called disjoint union and product, are defined. This is then shown to turn the set of isomorphism classes of Pólya urns into a semiring, and we find that assigning to an urn its intensity matrix is a semiring homomorphism.In paper II, a modification and generalisation of the random cutting model is introduced. For a finite graph with given source and target vertices, we remove vertices at random and discard all resulting components without a source node. The results concern the number of cuts needed to remove all target vertices and the size of the remaining graph, and suggest that this model interpolates between the traditional cutting model and site percolation.In paper III, we define several polynomial invariants for rooted trees based on the modified cutting model in Paper II.We find recursive identities for these invariants and, using an approach via irreducibility of polynomials, prove that two specific invariants are complete, that is, they distinguish rooted trees up to isomorphism.In paper IV, joint with Paul Thévenin, we consider an operation of concatenating t random perfect matchings on 2n vertices. Our analysis of the resulting random graph as t tends to infinity shows that there is a giant component if and only if n is odd, and that the size of this giant component as well as the number of components is asymptotically normally distributed.
|
|
| 7. |
- Danielsson, Joel Larsson, et al.
(författare)
-
Polarised random κ-SAT
- 2023
-
Ingår i: Combinatorics, probability & computing. - : Cambridge University Press. - 0963-5483 .- 1469-2163. ; 32:6, s. 885-899
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 8. |
- Danielsson, Joel, et al.
(författare)
-
Polarised random k-SAT
- 2022
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- In this paper we study a variation of the random k-SAT problem, called polarized random k-SAT. In this model there is a polarization parameter p, and in half of the clauses each variable occurs negated with probability p and pure otherwise, while in the other half the probabilities are interchanged. For p=1/2 we get the classical random k-SAT model, and at the other extreme we have the fully polarized model where p=0, or 1. Here there are only two types of clauses: clauses where all k variables occur pure, and clauses where all k variables occur negated. That is, for p=0 we get an instance of random monotone k-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 polarized random k-SAT is an upper bound on the threshold for random k-SAT. In fact, we conjecture that asymptotically the two thresholds coincide.
|
|
| 9. |
- Demetres, Christofides, et al.
(författare)
-
Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales
- 2008
-
Ingår i: Random structures & algorithms (Print). - : Wiley-Blackwell. - 1042-9832 .- 1098-2418. ; 32:1, s. 88-100
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 10. |
- Markström, Klas
(författare)
-
From the ising and potts models to the general graph homomorphism polynomial
- 2017
-
Ingår i: Graph polynomials. - Boca Raton : CRC Press, [2017] | Series: Discrete mathematics and its applications : CRC Press. - 9781498755917 - 9781498755900 ; , s. 123-138
-
Bokkapitel (refereegranskat)abstract
- A number of classical models in statistical physics, such as the Ising model, Potts model, and lattice gas, can be formulated in terms of the generating function for weighted versions of homo-morphisms from G to some graph H. This chapter discusses the generating polynomial for homomorphisms from a graph G to the most general weighted graph on q vertices. For a fixed q, this is an object of polynomial size which contains a wealth of information about the graph G, but as we will later show it is not a complete graph invariant. The chapter describes this generating function as a polynomial, then recalls the definitions of a number of well-known graph polynomials, and partition functions from physics, and then proceeds to study the properties and relationships of these polynomials. There has been several approaches to defining an analogue of the Tutte polynomial for directed graphs as well.
|
|
