A. Martinsson

activity

20122023

most citedOn the existence of accessible paths in various models of fitness landscapes

39 citations · 89 across the 25 of their papers we have counts for

collaborators

36 papers

math.CO2023★ 3 cited

On the approximability of the burning number

Anders Martinsson

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…

math.CO2023★ 1 cited

Synchronizing random automata through repeated 'a' inputs

Anders Martinsson

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}\l…

math.CO2023

On Connectivity in Random Graph Models with Limited Dependencies

Johannes Lengler, Anders Martinsson, Kalina Petrova +4

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 r…

math.CO2023

Finding a good tree to burn

Anders Martinsson

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 conjectur…

cs.DS2022★ 1 cited

Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances

Václav Rozhoň, Bernhard Haeupler, Anders Martinsson +2

We introduce stronger notions for approximate single-source shortest-path distances, show how to efficiently compute them from weaker standard notions, and demonstrate the algorith…

math.CO2022

Strengthening Hadwiger's conjecture for $4$ - and $5$ -chromatic graphs

Anders Martinsson, Raphael Steiner

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 follo…

math.CO2022

Cycle lengths modulo $k$ in expanders

Anders Martinsson, Raphael Steiner

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 ∣$ . Addres…

math.CO2022

Optimal schemes for combinatorial query problems with integer feedback

Anders Martinsson

A query game is a pair of a set $Q$ of queries and a set $F$ of functions, or codewords $f : Q \to Z .$ We think of this as a two-player game. One player, Co…

math.CO2021

Hat guessing numbers of strongly degenerate graphs

Charlotte Knierim, Anders Martinsson, Raphael Steiner

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…

math.CO2021

Reconstructibility of the $K_{r}$ -count from $n - 1$ cards

Charlotte Knierim, Anders Martinsson

The Reconstruction Conjecture of Kelly and Ulam states that any graph $G$ with $n \geq 3$ vertices can be reconstructed from the multiset $D (G)$ of unlabelled subgraphs $G…

math.CO2021

A simplified proof of the Johansson-Molloy Theorem using the Rosenfeld counting method

Anders Martinsson

We show that any triangle-free graph with maximum degree $Δ$ has chromatic number at most $(1 + o (1)) Δ/ lo g Δ.$

math.CO2021

Arithmetic Progressions in Sumsets of Sparse Sets

Noga Alon, Ryan Alweiss, Yang P. Liu +2

A set of positive integers $A \subset Z_{> 0}$ is \emph{log-sparse} if there is an absolute constant $C$ so that for any positive integer $x$ the sequence contains at most…

math.CO2021

Note on Long Paths in Eulerian Digraphs

Charlotte Knierim, Maxime Larcher, Anders Martinsson

Long Paths and Cycles in eulerian digraphs have gotten a lot of attention recently. In this short note, we show how to use methods from Knierim, Larcher, Martinsson, Noever (2021)…

math.CO2021

Solving Static Permutation Mastermind using $O (n lo g n)$ Queries

Maxime Larcher, Anders Martinsson, Angelika Steger

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 allo…

math.CO2020

Mastermind with a Linear Number of Queries

Anders Martinsson, Pascal Su

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…

math.CO2020★ 3 cited

The Chromatic Number of Dense Random Block Graphs

Anders Martinsson, Konstantinos Panagiotou, Pascal Su +1

The chromatic number $χ (G)$ of a graph $G$ , that is, the smallest number of colors required to color the vertices of $G$ so that no two adjacent vertices are assigned the same colo…

math.CO2019

Long Cycles, Heavy Cycles and Cycle Decompositions in Digraphs

Charlotte Knierim, Maxime Larcher, Anders Martinsson +1

Hajós conjectured in 1968 that every Eulerian $n$-vertex graph can be decomposed into at most $⌊(n - 1) /2 ⌋$ edge-disjoint cycles. This has been confirmed for some spec…

cs.DM2019

Navigating an Infinite Space with Unreliable Movements

Anders Martinsson, Jara Uitto

We consider a search problem on a $2$ -dimensional infinite grid with a single mobile agent. The goal of the agent is to find her way home, which is located in a grid cell chosen by…

cs.LG2019★ 5 cited

Optimal Kronecker-Sum Approximation of Real Time Recurrent Learning

Frederik Benzing, Marcelo Matheus Gauy, Asier Mujika +2

One of the central goals of Recurrent Neural Networks (RNNs) is to learn long-term dependencies in sequential data. Nevertheless, the most popular training method, Truncated Backpr…

cs.DS2018

Optimal strategies for patrolling fences

Bernhard Haeupler, Fabian Kuhn, Anders Martinsson +2

A classical multi-agent fence patrolling problem asks: What is the maximum length $L$ of a line that $k$ agents with maximum speeds $v_{1}, \dots, v_{k}$ can patrol if each point on the…

math.CO2018★ 5 cited

The edge-statistics conjecture for $ℓ ≪ k^{6/5}$

Anders Martinsson, Frank Mousset, Andreas Noever +1

Let $k$ and $ℓ$ be positive integers. We prove that if $1 \leq ℓ \leq o_{k} (k^{6/5})$ , then in every large enough graph $G$ , the fraction of $k$ -vertex subsets that induce exac…

math.PR2018★ 4 cited

When Does Hillclimbing Fail on Monotone Functions: An entropy compression argument

Johannes Lengler, Anders Martinsson, Angelika Steger

Hillclimbing is an essential part of any optimization algorithm. An important benchmark for hillclimbing algorithms on pseudo-Boolean functions $f : {0, 1}^{n} \to R$ are (s…

math.PR2018

The "No Justice in the Universe" phenomenon: why honesty of effort may not be rewarded in tournaments

Peter Hegarty, Anders Martinsson, Edvin Wedin

In 2000 Allen Schwenk, using a well-known mathematical model of matchplay tournaments in which the probability of one player beating another in a single match is fixed for each pai…

cs.DM2018

Even flying cops should think ahead

Anders Martinsson, Florian Meier, Patrick Schnider +1

We study the entanglement game, which is a version of cops and robbers, on sparse graphs. While the minimum degree of a graph G is a lower bound for the number of cops needed to ca…

On the approximability of the burning number

Synchronizing random automata through repeated 'a' inputs

On Connectivity in Random Graph Models with Limited Dependencies

Finding a good tree to burn

Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances

Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs

Cycle lengths modulo k in expanders

Optimal schemes for combinatorial query problems with integer feedback

Hat guessing numbers of strongly degenerate graphs

Reconstructibility of the Kr​-count from n−1 cards

A simplified proof of the Johansson-Molloy Theorem using the Rosenfeld counting method

Arithmetic Progressions in Sumsets of Sparse Sets

Note on Long Paths in Eulerian Digraphs

Solving Static Permutation Mastermind using O(nlogn) Queries

Mastermind with a Linear Number of Queries

The Chromatic Number of Dense Random Block Graphs

Long Cycles, Heavy Cycles and Cycle Decompositions in Digraphs

Navigating an Infinite Space with Unreliable Movements

Optimal Kronecker-Sum Approximation of Real Time Recurrent Learning

Optimal strategies for patrolling fences

The edge-statistics conjecture for ℓ≪k6/5

When Does Hillclimbing Fail on Monotone Functions: An entropy compression argument

The "No Justice in the Universe" phenomenon: why honesty of effort may not be rewarded in tournaments

Even flying cops should think ahead

Strengthening Hadwiger's conjecture for $4$ - and $5$ -chromatic graphs

Cycle lengths modulo $k$ in expanders

Reconstructibility of the $K_{r}$ -count from $n - 1$ cards

Solving Static Permutation Mastermind using $O (n lo g n)$ Queries

The edge-statistics conjecture for $ℓ ≪ k^{6/5}$