5 citations · 10 across the 7 of their papers we have counts for
9 papers · 1 filter
On the approximability of the burning number
Anders Martinsson
The burning number of a graph is the smallest number such that the vertices of can be covered by balls of radii . As computing the burning number of a…
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 states with a -letter alphabet has a synchronizing word of length $O(\sqrt{n}\l…
On Connectivity in Random Graph Models with Limited Dependencies
Johannes Lengler, Anders Martinsson, Kalina Petrova +4
For any positive edge density , a random graph in the Erdős-Renyi model is connected with non-zero probability, since all edges are mutually independent. We consider r…
Finding a good tree to burn
Anders Martinsson
The burning number of a graph is the smallest positive integer such that the vertex set of can be covered with balls of radii . A well-known conjectur…
Cycle lengths modulo in expanders
Anders Martinsson, Raphael Steiner
Given a constant , an -vertex graph is called an -expander if every set of at most vertices in has an external neighborhood of size at least . Addres…
Arithmetic Progressions in Sumsets of Sparse Sets
Noga Alon, Ryan Alweiss, Yang P. Liu +2
A set of positive integers is \emph{log-sparse} if there is an absolute constant so that for any positive integer the sequence contains at most…