Source author record

Klas Markström

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.PR Computational Complexity cond-mat.stat-mech math.AT math.NT quant-ph

Catalog footprint

Research overview

23works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Polarised random k-SAT

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 $\frac{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.

preprint2020arXiv

Existence thresholds and Ramsey properties of random posets

Let $\mathcal P(n)$ denote the power set of $[n]$ , ordered by inclusion, and let $\mathcal P (n,p)$ denote the random poset obtained from $\mathcal P(n)$ by retaining each element from $\mathcal P (n)$ independently at random with probability $p$ and discarding it otherwise. Given any fixed poset $F$ we determine the threshold for the property that $\mathcal P(n,p)$ contains $F$ as an induced subposet. We also asymptotically determine the number of copies of a fixed poset $F$ in $\mathcal P(n)$ . Finally, we obtain a number of results on the Ramsey properties of the random poset $\mathcal P(n,p)$ .

preprint2020arXiv

Partite Turán-densities for complete $r-$ uniform hypergraphs on $r+1$ vertices

In this paper we investigate density conditions for finding a complete $r$ -uniform hypergraph $K_{r+1}^{(r)}$ on $r+1$ vertices in an $(r+1)$ -partite $r$ -uniform hypergraph $G$ . First we prove an optimal condition in terms of the densities of the $(r+1)$ induced $r$ -partite subgraphs of $G$ . Second, we prove a version of this result where we assume that $r$ -tuples of vertices in $G$ have their neighbours evenly distributed in $G$ . Third, we also prove a counting result for the minimum number of copies of $K_{r+1}^{(r)}$ when $G$ satisfies our density bound, and present some open problems. A striking difference between the graph, $r=2$ , and the hypergraph, $r \geq 3$ , cases is that in the first case both the existence threshold and the counting function are non-linear in the involved densities, whereas for hypergraphs they are given by a linear function. Also, the smallest density of the $r$ -partite parts needed to ensure the existence of a complete $r$ -graph with $(r+1)$ vertices is equal to the golden ratio $τ=0.618\ldots$ for $r=2$ , while it is $\frac{r}{r+1}$ for $r\geq3$ .

preprint2020arXiv

Random Uniform and Pure Random Simplicial Complexes

In this paper we introduce a method which allows us to study properties of the random uniform simplicial complex. That is, we assign equal probability to all simplicial complexes with a given number of vertices and then consider properties of a complex under this measure. We are able to determine or present bounds for a number of topological and combinatorial properties. We also study the random pure simplicial complex of dimension $d$ , generated by letting any subset of size $d+1$ of a set of $n$ vertices be a facet with probability $p$ and considering the simplicial complex generated by these facets. We compare the behaviour of these models for suitable values of $d$ and $p$ . Finally we use the equivalence between simplicial complexes and monotone boolean functions to study the behaviour of typical such functions. Specifically we prove that most monotone boolean functions are evasive, hence proving that the well known Evasiveness conjecture is generically true for monotone boolean functions without symmetry assumptions.

preprint2016arXiv

Full subgraphs

Let $G=(V,E)$ be a graph of density $p$ on $n$ vertices. Following Erdős, Łuczak and Spencer, an $m$ -vertex subgraph $H$ of $G$ is called {\em full} if $H$ has minimum degree at least $p(m - 1)$ . Let $f(G)$ denote the order of a largest full subgraph of $G$ . If $p\binom{n}{2}$ is a non-negative integer, define $f(n,p) = \min\{f(G) : \vert V(G)\vert = n, \ \vert E(G)\vert = p\binom{n}{2} \}.$ Erdős, Łuczak and Spencer proved that for $n \geq 2$ , $(2n)^{\frac{1}{2}} - 2 \leq f(n, {\frac{1}{2}}) \leq 4n^{\frac{2}{3}}(\log n)^{\frac{1}{3}}.$ In this paper, we prove the following lower bound: for $n^{-\frac{2}{3}} <p_n <1-n^{-\frac{1}{7}}$ , $f(n,p) \geq \frac{1}{4}(1-p)^{\frac{2}{3}}n^{\frac{2}{3}} -1.$ Furthermore we show that this is tight up to a multiplicative constant factor for infinitely many $p$ near the elements of $\{\frac{1}{2},\frac{2}{3},\frac{3}{4},\dots\}$ . In contrast, we show that for any $n$ -vertex graph $G$ , either $G$ or $G^c$ contains a full subgraph on $Ω(\frac{n}{\log n})$ vertices. Finally, we discuss full subgraphs of random and pseudo-random graphs, and several open problems.

preprint2016arXiv

Speed and concentration of the covering time for structured coupon collectors

Let $V$ be an $n$ -set, and let $X$ be a random variable taking values in the powerset of $V$ . Suppose we are given a sequence of random coupons $X_1, X_2, \ldots$ , where the $X_i$ are independent random variables with distribution given by $X$ . The covering time $T$ is the smallest integer $t\geq 0$ such that $\bigcup_{i=1}^tX_i=V$ . The distribution of $T$ is important in many applications in combinatorial probability, and has been extensively studied. However the literature has focussed almost exclusively on the case where $X$ is assumed to be symmetric and/or uniform in some way. In this paper we study the covering time for much more general random variables $X$ ; we give general criteria for $T$ being sharply concentrated around its mean, precise tools to estimate that mean, as well as examples where $T$ fails to be concentrated and when structural properties in the distribution of $X$ allow for a very different behaviour of $T$ relative to the symmetric/uniform case.

preprint2015arXiv

From the Ising and Potts models to the general graph homomorphism polynomial

In this note we study some of the properties of the generating polynomial for homomorphisms from a graph to at complete weighted graph on $q$ vertices. We discuss how this polynomial relates to a long list of other well known graph polynomials and the partition functions for different spin models, many of which are specialisations of the homomorphism polynomial. We also identify the smallest graphs which are not determined by their homomorphism polynomials for $q=2$ and $q=3$ and compare this with the corresponding minimal examples for the $U$ -polynomial, which generalizes the well known Tutte-polynomal.

preprint2015arXiv

Problem collection from the IML programme: Graphs, Hypergraphs, and Computing

This collection of problems and conjectures is based on a subset of the open problems from the seminar series and the problem sessions of the Institut Mitag-Leffler programme Graphs, Hypergraphs, and Computing. Each problem contributor has provided a write up of their proposed problem and the collection has been edited by Klas Markström.

preprint2015arXiv

Random subcube intersection graphs I: cliques and covering

We study random subcube intersection graphs, that is, graphs obtained by selecting a random collection of subcubes of a fixed hypercube $Q_d$ to serve as the vertices of the graph, and setting an edge between a pair of subcubes if their intersection is non-empty. Our motivation for considering such graphs is to model `random compatibility' between vertices in a large network. For both of the models considered in this paper, we determine the thresholds for covering the underlying hypercube $Q_d$ and for the appearance of s-cliques. In addition we pose some open problems.

preprint2014arXiv

$\ell$ -degree Turán density

Let $H_n$ be a $k$ -graph on $n$ vertices. For $0 \le \ell <k$ and an $\ell$ -subset $T$ of $V(H_n)$ , define the degree $°(T)$ of $T$ to be the number of $(k-\ell)$ -subsets~ $S$ such that $S \cup T$ is an edge in~ $H_n$ . Let the minimum $\ell$ -degree of $H_n$ be $δ_{\ell}(H_n) = \min \{ °(T) : T \subseteq V(H_n)$ and $|T|=\ell\}$ . Given a family $\mathcal{F}$ of $k$ -graphs, the $\ell$ -degree Turán number $\text{ex}_{\ell}(n, \mathcal{F})$ is the largest $δ_{\ell}(H_n)$ over all $\mathcal{F}$ -free $k$ -graphs $H_n$ on $n$ vertices. Hence, $\text{ex}_0(n, \mathcal{F})$ is the Turán number. We define $\ell$ -degree Turán density to be $π^k_{\ell}(\mathcal{F}) = \limsup_{n \rightarrow \infty} \frac{\text{ex}_{\ell}(n, \mathcal{F} )}{ \binom{n- \ell}{k}}.$ In this paper, we show that for $k> \ell >1$ , the set of $π_{\ell}^k(\mathcal{F})$ is dense in the interval $[0,1)$ . Hence, there is no "jump" for $\ell$ -degree Turán density when $k>\ell >1$ . We also give a lower bound on $π_{\ell}^k(\mathcal{F})$ in terms of an ordinary Turán density.

preprint2014arXiv

$F$ -factors in hypergraphs via absorption

Given integers $n \ge k >l \ge 1$ and a $k$ -graph $F$ with $|V(F)|$ divisible by $n$ , define $t_l^k(n,F)$ to be the smallest integer $d$ such that every $k$ -graph $H$ of order $n$ with minimum $l$ -degree $δ_l(H) \ge d$ contains an $F$ -factor. A classical theorem of Hajnal and Szemerédi implies that $t^2_1(n,K_t) = (1-1/t)n$ for integers $t$ . For $k \ge 3$ , $t^k_{k-1}(n,K_k^k)$ (the $δ_{k-1}(H)$ threshold for perfect matchings) has been determined by Kühn and Osthus (asymptotically) and Rödl, Ruciński and Szemerédi (exactly) for large $n$ . In this paper, we generalise the absorption technique of Rödl, Ruciński and Szemerédi to $F$ -factors. We determine the asymptotic values of $t^k_1(n,K_k^k(m))$ for $k = 3,4$ and $m \ge 1$ . In addition, we show that for $t>k = 3$ and $γ>0$ , $t^3_{2}(n,K_t^3) \le (1- \frac{2}{t^2-3t+4} + γ) n$ provided $n$ is large and $t | n$ . We also bound $t^3_{2}(n,K_t^3)$ from below. In particular, we deduce that $t^3_2(n,K_4^3) = (3/4+o(1))n$ answering a question of Pikhurko. In addition, we prove that $t^k_{k-1}(n,K_t^k) \le (1- \binom{t-1}{k-1}^{-1} + γ)n$ for $γ>0$ , $k \ge 6$ and $t \ge (3+ \sqrt5)k/2$ provided $n$ is large and $t | n$ .

preprint2014arXiv

Hearing the Shape of the Ising Model with a Programmable Superconducting-Flux Annealer

Two objects can be distinguished if they have different measurable properties. Thus, distinguishability depends on the Physics of the objects. In considering graphs, we revisit the Ising model as a framework to define physically meaningful spectral invariants. In this context, we introduce a family of refinements of the classical spectrum and consider the quantum partition function. We demonstrate that the energy spectrum of the quantum Ising Hamiltonian is a stronger invariant than the classical one without refinements. For the purpose of implementing the related physical systems, we perform experiments on a programmable annealer with superconducting flux technology. Departing from the paradigm of adiabatic computation, we take advantage of a noisy evolution of the device to generate statistics of low energy states. The graphs considered in the experiments have the same classical partition functions, but different quantum spectra. The data obtained from the annealer distinguish non-isomorphic graphs via information contained in the classical refinements of the functions but not via the differences in the quantum spectra.

preprint2014arXiv

Improved bounds for the shortness coefficient of cyclically 4-edge connected cubic graphs and snarks

We present a construction which shows that there is an infinite set of cyclically 4-edge connected cubic graphs on $n$ vertices with no cycle longer than $c_4 n$ for $c_4=\frac{12}{13}$ , and at the same time prove that a certain natural family of cubic graphs cannot be used to lower the shortness coefficient $c_4$ to 0. The graphs we construct are snarks so we get the same upper bound for the shortness coefficient of snarks, and we prove that the constructed graphs have an oddness growing linearly with the number of vertices.

preprint2014arXiv

Perfect matchings in 3-partite 3-uniform hypergraphs

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.

preprint2014arXiv

The straight line complexity of small factorials and primorials

In this paper we determine the straight-line complexity of $n!$ for $n\leq 22$ and give bounds for the complexities up to $n=46$ . In the same way we determine the straight-line complexity of the product of the first primes up to $p=31$ and gives bounds for $p\leq 43$ . Our results are based on an exhaustive computer search of the short length straight-line programs.

preprint2013arXiv

Generation and Properties of Snarks

For many of the unsolved problems concerning cycles and matchings in graphs it is known that it is sufficient to prove them for \emph{snarks}, the class of nontrivial 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\leq 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.

preprint2012arXiv

A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs

A perfect $K_t$ -matching in a graph $G$ is a spanning subgraph consisting of vertex disjoint copies of $K_t$ . A classic theorem of Hajnal and Szemerédi states that if $G$ is a graph of order $n$ with minimum degree $δ(G) \ge (t-1)n/t$ and $t| n$ , then $G$ contains a perfect $K_t$ -matching. Let $G$ be a $t$ -partite graph with vertex classes $V_1$ ,..., $V_t$ each of size $n$ . We show that if every vertex $x \in V_i$ is joined to at least $((t-1)/t + γ)n$ vertices of $V_j$ for $i \ne j$ , then $G$ contains a perfect $K_t$ -matching, thus verifying a conjecture of Fisher asymptotically. Furthermore, we consider a generalisation to hypergraphs in terms of the codegree.

preprint2012arXiv

Minimum codegree threshold for $(K_4^3-e)$ -factors

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 γ>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+γ)n and 4|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. Therefore, all minimum codegree thresholds for the existence of F-factors are known asymptotically for 3-uniform hypergraphs F on 4 vertices.

preprint2012arXiv

The range of thresholds for diameter 2 in random Cayley graphs

Given a group G, the model \mathcal{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 \in \mathbb{R}_+ we say that c is the threshold for diameter 2 for (G_k) if for any \varepsilon > 0 with high probability Γ\in \mathcal{G}(G_k,p) has diameter greater than 2 if p \leqslant \sqrt{(c - \eps)\frac{\log{n}}{n}} and diameter at most 2 if p \geqslant \sqrt{(c + \eps)\frac{\log{n}}{n}}. In [5] we proved that if c is a threshold for diameter 2 for a family of groups (G_k) then c \in [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 \in [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 \in [1/4,4/3] is a threshold but a c \in (4/3,2] is a threshold if and only if it is of the form 4n/(3n-1) for some positive integer n.

preprint2011arXiv

Random Latin square graphs

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.

preprint2011arXiv

The thresholds for diameter 2 in random Cayley graphs

Given a group G, the model $\mathcal{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 $ε> 0$ and any family of groups G_k of order n_k for which $n_k \to \infty$ , a graph $Γ_k \in \mathcal{G}(G_k,p)$ with high probability has diameter at most 2 if $p \geqslant \sqrt{(2 + ε) \frac{\log{n_k}}{n_k}}$ and with high probability has diameter greater than 2 if $p \leqslant \sqrt{(1/4 + ε)\frac{\log{n_k}}{n_k}}$ . 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 Erdős-Renyi random graphs.

preprint2011arXiv

Turán and Ramsey Properties of Subcube Intersection Graphs

The discrete cube $\{0,1\}^d$ is a fundamental combinatorial structure. A subcube of $\{0,1\}^d$ is a subset of $2^k$ of its points formed by fixing $k$ coordinates and allowing the remaining $d-k$ to vary freely. The subcube structure of the discrete cube is surprisingly complicated and there are many open questions relating to it. 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 as Turán and Ramsey type questions in intersection graphs of subcubes where 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. Turán and Ramsey type problems are at the heart of extremal combinatorics and so these problems are mathematically natural. However, a second motivation is a connection with some questions in social choice theory arising from a simple model of agreement in a society. Specifically, if we have to make a binary choice on each of $n$ separate issues then it is reasonable to assume that the set of choices which are acceptable to an individual will be represented by a subcube. Consequently, the pattern of intersections within a family of subcubes will have implications for the level of agreement within a society. We pose a number of questions and conjectures relating directly to the Turán and Ramsey problems as well as raising some further directions for study of subcube intersection graphs.

preprint2011arXiv

Two questions of Erdős on hypergraphs above the Tur{á}n threshold}

For ordinary graphs it is known that any graph $G$ with more edges than the Tur{á}n number of $K_s$ must contain several copies of $K_s$ , and a copy of $K_{s+1}^-$ , the complete graph on $s+1$ vertices with one missing edge. Erdős asked if the same result is true for $K^3_s$ , 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 ${K^3_{s+1}}^-$ , we show that for $s=4$ the answer is negative for all large $n$ as well, by proving that the Tur{á}n density of ${K^3_5}^-$ is greater than that of $K^3_4$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Klas Markström

Research overview

Is this your work?

23 publications

Polarised random k-SAT

Existence thresholds and Ramsey properties of random posets

Partite Turán-densities for complete $r-$ uniform hypergraphs on $r+1$ vertices

Random Uniform and Pure Random Simplicial Complexes

Full subgraphs

Speed and concentration of the covering time for structured coupon collectors

From the Ising and Potts models to the general graph homomorphism polynomial

Problem collection from the IML programme: Graphs, Hypergraphs, and Computing

Random subcube intersection graphs I: cliques and covering

$\ell$ -degree Turán density

$F$ -factors in hypergraphs via absorption

Hearing the Shape of the Ising Model with a Programmable Superconducting-Flux Annealer

Improved bounds for the shortness coefficient of cyclically 4-edge connected cubic graphs and snarks

Perfect matchings in 3-partite 3-uniform hypergraphs

The straight line complexity of small factorials and primorials

Generation and Properties of Snarks

A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs

Minimum codegree threshold for $(K_4^3-e)$ -factors

The range of thresholds for diameter 2 in random Cayley graphs

Random Latin square graphs

The thresholds for diameter 2 in random Cayley graphs

Turán and Ramsey Properties of Subcube Intersection Graphs

Two questions of Erdős on hypergraphs above the Tur{á}n threshold}

See the researcher in context

Building this map preview

Klas Markström

Research overview

Is this your work?

23 publications

Polarised random k-SAT

Existence thresholds and Ramsey properties of random posets

Partite Turán-densities for complete r−r-r−uniform hypergraphs on r+1r+1r+1 vertices

Random Uniform and Pure Random Simplicial Complexes

Full subgraphs

Speed and concentration of the covering time for structured coupon collectors

From the Ising and Potts models to the general graph homomorphism polynomial

Problem collection from the IML programme: Graphs, Hypergraphs, and Computing

Random subcube intersection graphs I: cliques and covering

ℓ\ellℓ-degree Turán density

FFF-factors in hypergraphs via absorption

Hearing the Shape of the Ising Model with a Programmable Superconducting-Flux Annealer

Improved bounds for the shortness coefficient of cyclically 4-edge connected cubic graphs and snarks

Perfect matchings in 3-partite 3-uniform hypergraphs

The straight line complexity of small factorials and primorials

Generation and Properties of Snarks

A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs

Minimum codegree threshold for (K43−e)(K_4^3-e)(K43​−e)-factors

The range of thresholds for diameter 2 in random Cayley graphs

Random Latin square graphs

The thresholds for diameter 2 in random Cayley graphs

Turán and Ramsey Properties of Subcube Intersection Graphs

Two questions of Erdős on hypergraphs above the Tur{á}n threshold}

See the researcher in context

Building this map preview

Partite Turán-densities for complete $r-$ uniform hypergraphs on $r+1$ vertices

$\ell$ -degree Turán density

$F$ -factors in hypergraphs via absorption

Minimum codegree threshold for $(K_4^3-e)$ -factors