BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Anders Martinsson

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

ResearcherUnclaimed source record
math.COmath.PRSystems and ControlComputational GeometryData Structures and AlgorithmsDiscrete MathematicsInformation Theorymath.ITmath.NTMultiagent SystemsPopulations and EvolutionQuantitative MethodsRobotics

Catalog footprint

Research overview

12works
13topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

12 publications

preprint2022arXiv

Cycle lengths modulo kk in expanders

Given a constant α>0α>0, an nn-vertex graph is called an αα-expander if every set XX of at most n/2n/2 vertices in GG has an external neighborhood of size at least α∣X∣α|X|. Addressing a question posed by Friedman and Krivelevich in [Combinatorica, 41(1), (2021), pp. 53--74], we prove the following result: Let k>1k>1 be an integer with smallest prime divisor pp. Then for α>1p−1α>\frac{1}{p-1} every sufficiently large αα-expanding graph contains cycles of length congruent to any given residue modulo kk. This result is almost best possible, in the following sense: There exists an absolute constant c>0c>0 such that for every integer kk with smallest prime divisor pp and for every positive α<cp−1α<\frac{c}{p-1}, there exist arbitrarily large αα-expanding graphs with no cycles of length rr modulo kk, for some r∈{0,…,k−1}r \in \{0,\ldots,k-1\}.

Open access
preprint2022arXiv

Solving Static Permutation Mastermind using O(nlog⁡n)O(n \log n) Queries

Permutation Mastermind is a version of the classical mastermind game in which the number of positions nn is equal to the number of colors kk, and repetition of colors is not allowed, neither in the codeword nor in the queries. In this paper we solve the main open question from Glazik, Jäger, Schiemann and Srivastav (2021), who asked whether their bound of O(n1.525)O(n^{1.525}) for the static version can be improved to O(nlog⁡n)O(n \log n), which would be best possible. By using a simple probabilistic argument we show that this is indeed the case.

Open access
preprint2022arXiv

Strengthening Hadwiger's conjecture for 44- and 55-chromatic graphs

Hadwiger's famous coloring conjecture states that every tt-chromatic graph contains a KtK_t-minor. Holroyd [Bull. London Math. Soc. 29, (1997), pp. 139--144] conjectured the following strengthening of Hadwiger's conjecture: If GG is a tt-chromatic graph and S⊆V(G)S \subseteq V(G) takes all colors in every tt-coloring of GG, then GG contains a KtK_t-minor rooted at SS. We prove this conjecture in the first open case of t=4t=4. Notably, our result also directly implies a stronger version of Hadwiger's conjecture for 55-chromatic graphs as follows: Every 55-chromatic graph contains a K5K_5-minor with a singleton branch-set. In fact, in a 55-vertex-critical graph we may specify the singleton branch-set to be any vertex of the graph.

Open access
preprint2020arXiv

Long Cycles, Heavy Cycles and Cycle Decompositions in Digraphs

Hajós conjectured in 1968 that every Eulerian nn-vertex graph can be decomposed into at most ⌊(n−1)/2⌋\lfloor (n-1)/2\rfloor edge-disjoint cycles. This has been confirmed for some special graph classes, but the general case remains open. In a sequence of papers by Bienia and Meyniel (1986), Dean (1986), and Bollobás and Scott (1996) it was analogously conjectured that every \emph{directed} Eulerian graph can be decomposed into O(n)O(n) cycles. In this paper, we show that every directed Eulerian graph can be decomposed into O(nlog⁡Δ)O(n \log Δ) disjoint cycles, thus making progress towards the conjecture by Bollobás and Scott. Our approach is based on finding heavy cycles in certain edge-weightings of directed graphs. As a further consequence of our techniques, we prove that for every edge-weighted digraph in which every vertex has out-weight at least 11, there exists a cycle with weight at least Ω(log⁡log⁡n/log⁡n)Ω(\log \log n/{\log n}), thus resolving a question by Bollobás and Scott.

Open access
preprint2016arXiv

Shotgun edge assembly of random jigsaw puzzles

In recent work by Mossel and Ross, it was asked how large qq has to be for a random jigsaw puzzle with qq different shapes of "jigs" to have exactly one solution. The jigs are assumed symmetric in the sense that two jigs of the same type always fit together. They showed that for q=o(n2/3)q=o(n^{2/3}) there are a.a.s. multiple solutions, and for q=ω(n2)q=ω(n^2) there is a.a.s. exactly one. The latter bound has since been improved to q≥n1+εq\geq n^{1+\varepsilon} independently by Nenadov, Pfister and Steger, and by Bordernave, Feige and Mossel. Both groups further remark that for q=o(n)q=o(n) there are a.a.s. duplicate pieces in the puzzle. In this paper, we show that such puzzle a.a.s. has multiple solutions whenever q≤2e n−ω(log⁡2n)q\leq \frac{2}{\sqrt{e}}\,n - ω(\log_2 n), even if permuting identical pieces is not considered changing the solution. We further give some remarks about the number of solutions, and the probability of a unique solution in this regime.

Open access
preprint2015arXiv

Accessibility percolation and first-passage site percolation on the unoriented binary hypercube

Inspired by biological evolution, we consider the following so-called accessibility percolation problem: The vertices of the unoriented nn-dimensional binary hypercube are assigned independent U(0,1)U(0, 1) weights, referred to as fitnesses. A path is considered accessible if fitnesses are strictly increasing along it. We prove that the probability that the global fitness maximum is accessible from the all zeroes vertex converges to 1−12ln⁡(2+5)1-\frac{1}{2}\ln\left(2+\sqrt{5}\right) as n→∞n\rightarrow\infty. Moreover, we prove that if one conditions on the location of the fitness maximum being vv, then provided vv is not too close to the all zeroes vertex in Hamming distance, the probability that vv is accessible converges to a function of this distance divided by nn as n→∞n\rightarrow\infty. This resolves a conjecture by Berestycki, Brunet and Shi in almost full generality. As a second result we show that, for any graph, accessibility percolation can equivalently be formulated in terms of first-passage site percolation. This connection is of particular importance for the study of accessibility percolation on trees.

Open access
preprint2015arXiv

Permutations destroying arithmetic progressions in finite cyclic groups

A permutation πof an abelian group G is said to destroy arithmetic progressions (APs) if, whenever (a,b,c) is a non-trivial 3-term AP in G, that is c-b=b-a and a,b,c are not all equal, then (π(a),π(b),π(c)) is not an AP. In a paper from 2004, the first author conjectured that such a permutation exists of Z/nZ, for all n except 2,3,5 and 7. Here we prove, as a special case of a more general result, that such a permutation exists for all n >= n_0, for some explcitly constructed number n_0 \approx 1.4 x 10^{14}. We also construct such a permutation of Z/pZ for all primes p > 3 such that p = 3 (mod 8).

Open access
preprint2014arXiv

On the existence of accessible paths in various models of fitness landscapes

We present rigorous mathematical analyses of a number of well-known mathematical models for genetic mutations. In these models, the genome is represented by a vertex of the nn-dimensional binary hypercube, for some nn, a mutation involves the flipping of a single bit, and each vertex is assigned a real number, called its fitness, according to some rules. Our main concern is with the issue of existence of (selectively) accessible paths; that is, monotonic paths in the hypercube along which fitness is always increasing. Our main results resolve open questions about three such models, which in the biophysics literature are known as house of cards (HoC), constrained house of cards (CHoC) and rough Mount Fuji (RMF). We prove that the probability of there being at least one accessible path from the all-zeroes node v0\mathbf {v}^0 to the all-ones node v1\mathbf {v}^1 tends respectively to 0, 1 and 1, as nn tends to infinity. A crucial idea is the introduction of a generalization of the CHoC model, in which the fitness of v0\mathbf {v}^0 is set to some α=αn∈[0,1]α=α_n\in[0,1]. We prove that there is a very sharp threshold at αn=ln⁡nnα_n=\frac{\ln n}{n} for the existence of accessible paths from v0\mathbf {v}^0 to v1\mathbf {v}^1. As a corollary we prove significant concentration, for αα below the threshold, of the number of accessible paths about the expected value (the precise statement is technical; see Corollary 1.4). In the case of RMF, we prove that the probability of accessible paths from v0\mathbf {v}^0 to v1\mathbf {v}^1 existing tends to 11 provided the drift parameter θ=θnθ=θ_n satisfies nθn→∞nθ_n\rightarrow\infty, and for any fitness distribution which is continuous on its support and whose support is connected.

Open access
preprint2014arXiv

Unoriented first-passage percolation on the n-cube

The nn-dimensional binary hypercube is the graph whose vertices are the binary nn-tuples {0,1}n\{0, 1\}^n and where two vertices are connected by an edge if they differ at exactly one coordinate. We prove that if the edges are assigned independent mean 1 exponential costs, the minimum length TnT_n of a path from (0,0,…,0)(0, 0, \dots, 0) to (1,1,…,1)(1, 1, \dots, 1) converges in probability to ln⁡(1+2)≈0.881\ln(1+\sqrt{2}) \approx 0.881. It has previously been shown by Fill and Pemantle (1993) that this so-called first-passage time asymptotically almost surely satisfies ln⁡(1+2)−o(1)≤Tn≤1+o(1)\ln(1+\sqrt{2}) - o(1) \leq T_n \leq 1+o(1), and has been conjectured to converge in probability by Bollobás and Kohayakawa (1997). A key idea of our proof is to consider a lower bound on Richardson's model, closely related to the branching process used in the article by Fill and Pemantle to obtain the bound Tn≥ln⁡(1+2)−o(1)T_n \geq \ln\left(1+\sqrt{2}\right)-o(1). We derive an explicit lower bound on the probability that a vertex is infected at a given time. This result is formulated for a general graph and may be applicable in a more general setting.

Open access
preprint2013arXiv

A variant of the multi-agent rendezvous problem

The classical multi-agent rendezvous problem asks for a deterministic algorithm by which nn points scattered in a plane can move about at constant speed and merge at a single point, assuming each point can use only the locations of the others it sees when making decisions and that the visibility graph as a whole is connected. In time complexity analyses of such algorithms, only the number of rounds of computation required are usually considered, not the amount of computation done per round. In this paper, we consider Ω(n2log⁡n)Ω(n^2 \log n) points distributed independently and uniformly at random in a disc of radius nn and, assuming each point can not only see but also, in principle, communicate with others within unit distance, seek a randomised merging algorithm which asymptotically almost surely (a.a.s.) runs in time O(n), in other words in time linear in the radius of the disc rather than in the number of points. Under a precise set of assumptions concerning the communication capabilities of neighboring points, we describe an algorithm which a.a.s. runs in time O(n) provided the number of points is o(n3)o(n^3). Several questions are posed for future work.

Open access

Research graph

See the researcher in context

Open full explorer

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.