Anders Martinsson
YOU?
Author Swipe
View article: Universality for transversal Hamilton cycles in random graphs
Universality for transversal Hamilton cycles in random graphs Open
A tuple $(G_1,\dots,G_n)$ of graphs on the same vertex set of size $n$ is said to be Hamilton-universal if for every map $χ: [n]\to[n]$ there exists a Hamilton cycle whose $i$-th edge comes from $G_{χ(i)}$. Bowtell, Morris, Pehova and Stad…
View article: Triangle-free $d$-degenerate graphs have small fractional chromatic number
Triangle-free $d$-degenerate graphs have small fractional chromatic number Open
A well-known conjecture by Harris states that any triangle-free $d$-degenerate graph has fractional chromatic number at most $O\left(\frac{d}{\ln d}\right)$. This conjecture has gained much attention in recent years, and is known to have m…
View article: Random independent sets in triangle-free graphs
Random independent sets in triangle-free graphs Open
We establish several new results on the existence of probability distributions on the independent sets in triangle-free graphs where each vertex is present with a given probability. This setting was introduced and studied under the name of…
View article: Local Shearer bound
Local Shearer bound Open
We prove the following local strengthening of Shearer's classic bound on the independence number of triangle-free graphs: For every triangle-free graph $G$ there exists a probability distribution on its independent sets such that every ver…
View article: Resolution of the Kohayakawa–Kreuter conjecture
Resolution of the Kohayakawa–Kreuter conjecture Open
A graph is said to be Ramsey for a tuple of graphs if every ‐coloring of the edges of contains a monochromatic copy of in color , for some . A fundamental question at the intersection of Ramsey theory and the theory of random graphs is to …
View article: Vertex-critical graphs far from edge-criticality
Vertex-critical graphs far from edge-criticality Open
Let $r$ be any positive integer. We prove that for every sufficiently large $k$ there exists a $k$ -chromatic vertex-critical graph $G$ such that $\chi (G-R)=k$ for every set $R \subseteq E(G)$ with $|R|\le r$ . This partially solves a pro…
View article: Improved bounds for zero-sum cycles in $\mathbb{Z}_p^d$
Improved bounds for zero-sum cycles in $\mathbb{Z}_p^d$ Open
For a finite Abelian group $(Γ,+)$, let $n(Γ)$ denote the smallest positive integer $n$ such that for each labelling of the arcs of the complete digraph of order $n$ using elements from $Γ$, there exists a directed cycle such that the tota…
View article: On connectivity in random graph models with limited dependencies
On connectivity in random graph models with limited dependencies Open
We consider random graph models in which the events describing the inclusion of potential edges have to be independent of each other if the corresponding edges are non‐adjacent and ask: what is the minimum probability , such that for any d…
View article: Reconstructibility of the K-count from n − 1 cards
Reconstructibility of the K-count from n − 1 cards Open
The Reconstruction Conjecture of Kelly and Ulam states that any graph G with n ≥ 3 vertices can be reconstructed from the multiset D(G) of unlabelled subgraphs G−v for all v∈V(G). We refer to D(G) as the deck of G and G−v∈D(G) as the cards…
View article: Resolution of the Kohayakawa-Kreuter conjecture
Resolution of the Kohayakawa-Kreuter conjecture Open
A graph $G$ is said to be Ramsey for a tuple of graphs $(H_1,\dots,H_r)$ if every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H_i$ in color $i$, for some $i$. A fundamental question at the intersection of Ramsey theo…
View article: Mastermind with a linear number of queries
Mastermind with a linear number of queries Open
Since the 1960s Mastermind has been studied for the combinatorial and information theoretical interest the game has to offer. Many results have been discovered starting with Erdős and Rényi determining the optimal number of queries needed …
View article: Mastermind with a linear number of queries
Mastermind with a linear number of queries Open
Since the 1960s Mastermind has been studied for the combinatorial and information-theoretical interest the game has to offer. Many results have been discovered starting with Erdős and Rényi determining the optimal number of queries needed …
View article: Vertex-critical graphs far from edge-criticality
Vertex-critical graphs far from edge-criticality Open
Let $r$ be any positive integer. We prove that for every sufficiently large $k$ there exists a $k$-chromatic vertex-critical graph $G$ such that $χ(G-R)=k$ for every set $R \subseteq E(G)$ with $|R|\le r$. This partially solves a problem p…
View article: Optimal schemes for combinatorial query problems with integer feedback
Optimal schemes for combinatorial query problems with integer feedback Open
A query game is a pair of a set $Q$ of queries and a set $\mathcal{F}$ of functions, or codewords $f:Q\rightarrow \mathbb{Z}.$ We think of this as a two-player game. One player, Codemaker, picks a hidden codeword $f\in \mathcal{F}$. The ot…
View article: Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs
Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs Open
Four-Color-Theorem Rooted minorsHadwiger's famous coloring conjecture states that every tchromatic graph contains a K t -minor.Holroyd [11] conjectured the following strengthening of Hadwiger's conjecture: If G is a t-chromatic graph and S…
View article: On the approximability of the burning number
On the approximability of the burning number Open
The burning number of a graph $G$ is the smallest number $b$ such that the vertices of $G$ can be covered by balls of radii $0, 1, \dots, b-1$. As computing the burning number of a graph is known to be NP-hard, even on trees, it is natural…
View article: Synchronizing random automata through repeated 'a' inputs
Synchronizing random automata through repeated 'a' inputs Open
In a recent article by Chapuy and Perarnau, it was shown that a uniformly chosen automaton on $n$ states with a $2$-letter alphabet has a synchronizing word of length $O(\sqrt{n}\log n)$ with high probability. In this note, we improve this…
View article: On Connectivity in Random Graph Models with Limited Dependencies
On Connectivity in Random Graph Models with Limited Dependencies Open
For any positive edge density $p$, a random graph in the Erdős-Renyi $G_{n,p}$ model is connected with non-zero probability, since all edges are mutually independent. We consider random graph models in which edges that do not share endpoin…
View article: Finding a good tree to burn
Finding a good tree to burn Open
The burning number of a graph $G$ is the smallest positive integer $k$ such that the vertex set of $G$ can be covered with balls of radii $0, 1, \dots, k-1$. A well-known conjecture by Bonato, Janssen and Roshabin states that any connected…
View article: Cycle lengths modulo k in expanders
Cycle lengths modulo k in expanders Open
Given a constant $α>0$, an $n$-vertex graph is called an $α$-expander if every set $X$ of at most $n/2$ vertices in $G$ has an external neighborhood of size at least $α|X|$. Addressing a question posed by Friedman and Krivelevich in [Combi…
View article: Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances Open
We introduce stronger notions for approximate single-source shortest-path distances, show how to efficiently compute them from weaker standard notions, and demonstrate the algorithmic power of these new notions and transformations. One app…
View article: Strengthening Hadwiger's conjecture for $4$- and $5$-chromatic graphs
Strengthening Hadwiger's conjecture for $4$- and $5$-chromatic graphs Open
Hadwiger's famous coloring conjecture states that every $t$-chromatic graph contains a $K_t$-minor. Holroyd [Bull. London Math. Soc. 29, (1997), pp. 139--144] conjectured the following strengthening of Hadwiger's conjecture: If $G$ is a $t…
View article: Solving Static Permutation Mastermind using $O(n \log n)$ Queries
Solving Static Permutation Mastermind using $O(n \log n)$ Queries Open
Permutation Mastermind is a version of the classical mastermind game in which the number of positions $n$ is equal to the number of colors $k$, and repetition of colors is not allowed, neither in the codeword nor in the queries. In this pa…
View article: Hat guessing numbers of strongly degenerate graphs
Hat guessing numbers of strongly degenerate graphs Open
Assume $n$ players are placed on the $n$ vertices of a graph $G$. The following game was introduced by Winkler: An adversary puts a hat on each player, where each hat has a colour out of $q$ available colours. The players can see the hat o…
View article: Reconstructibility of the $K_r$-count from $n-1$ cards
Reconstructibility of the $K_r$-count from $n-1$ cards Open
The Reconstruction Conjecture of Kelly and Ulam states that any graph $G$ with $n\geq 3$ vertices can be reconstructed from the multiset $\mathcal{D}(G)$ of unlabelled subgraphs $G-v$ for all $v\in V(G)$. We refer to $\mathcal{D}(G)$ as th…
View article: A simplified proof of the Johansson-Molloy Theorem using the Rosenfeld\n counting method
A simplified proof of the Johansson-Molloy Theorem using the Rosenfeld\n counting method Open
We show that any triangle-free graph with maximum degree $\\Delta$ has\nchromatic number at most $\\left(1+o(1)\\right)\\Delta/\\log \\Delta.$\n
View article: A simplified proof of the Johansson-Molloy Theorem using the Rosenfeld counting method
A simplified proof of the Johansson-Molloy Theorem using the Rosenfeld counting method Open
We show that any triangle-free graph with maximum degree $Δ$ has chromatic number at most $\left(1+o(1)\right)Δ/\log Δ.$
View article: Arithmetic Progressions in Sumsets of Sparse Sets
Arithmetic Progressions in Sumsets of Sparse Sets Open
See the abstract in the attached pdf.
View article: Note on Long Paths in Eulerian Digraphs
Note on Long Paths in Eulerian Digraphs Open
Long paths and cycles in Eulerian digraphs have received a lot of attention recently. In this short note, we show how to use methods from [Knierim, Larcher, Martinsson, Noever, JCTB 148:125--148] to find paths of length $d/(\log d+1)$ in E…
View article: Solving Static Permutation Mastermind using $O(n \log n)$ Queries
Solving Static Permutation Mastermind using $O(n \log n)$ Queries Open
Permutation Mastermind is a version of the classical mastermind game in which the number of positions $n$ is equal to the number of colors $k$, and repetition of colors is not allowed, neither in the codeword nor in the queries. In this pa…