BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Tobias Muller

Tobias Muller appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.PRComputational Geometrymath.LOmath.MG

Catalog footprint

What is connected

6works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

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.

Published work

6 published item(s)

preprint2016arXiv

The critical probability for confetti percolation equals $1/2$

In the confetti percolation model, or two-coloured dead leaves model, radius one disks arrive on the plane according to a space-time Poisson process. Each disk is coloured black with probability $p$ and white with probability $1-p$. In this paper we show that the critical probability for confetti percolation equals $1/2$. That is, if $p>1/2$ then a.s.~there is an unbounded curve in the plane all of whose points are black; while if $p \leq 1/2$ then a.s.~all connected components of the set of black points are bounded. This answers a question of Benjamini and Schramm. The proof builds on earlier work by Hirsch and makes use of an adaptation of a sharp thresholds result of Bourgain.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Maker-Breaker games on random geometric graphs

In a Maker-Breaker game on a graph $G$, Breaker and Maker alternately claim edges of $G$. Maker wins if, after all edges have been claimed, the graph induced by his edges has some desired property. We consider four Maker-Breaker games played on random geometric graphs. For each of our four games we show that if we add edges between $n$ points chosen uniformly at random in the unit square by order of increasing edge-length then, with probability tending to one as $n\to\infty$, the graph becomes Maker-win the very moment it satisfies a simple necessary condition. In particular, with high probability, Maker wins the connectivity game as soon as the minimum degree is at least two; Maker wins the Hamilton cycle game as soon as the minimum degree is at least four; Maker wins the perfect matching game as soon as the minimum degree is at least two and every edge has at least three neighbouring vertices; and Maker wins the $H$-game as soon as there is a subgraph from a finite list of "minimal graphs". These results also allow us to give precise expressions for the limiting probability that $G(n,r)$ is Maker-win in each case, where $G(n,r)$ is the graph on $n$ points chosen uniformly at random on the unit square with an edge between two points if and only if their distance is at most $r$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The acquaintance time of (percolated) random geometric graphs

In this paper, we study the acquaintance time $\AC(G)$ defined for a connected graph $G$. We focus on $\G(n,r,p)$, a random subgraph of a random geometric graph in which $n$ vertices are chosen uniformly at random and independently from $[0,1]^2$, and two vertices are adjacent with probability $p$ if the Euclidean distance between them is at most $r$. We present asymptotic results for the acquaintance time of $\G(n,r,p)$ for a wide range of $p=p(n)$ and $r=r(n)$. In particular, we show that with high probability $\AC(G) = Θ(r^{-2})$ for $G \in \G(n,r,1)$, the "ordinary" random geometric graph, provided that $πn r^2 - \ln n \to \infty$ (that is, above the connectivity threshold). For the percolated random geometric graph $G \in \G(n,r,p)$, we show that with high probability $\AC(G) = Θ(r^{-2} p^{-1} \ln n)$, provided that $p n r^2 \geq n^{1/2+\eps}$ and $p < 1-\eps$ for some $\eps>0$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A counterexample to conjecture 18.5 in "Geometric Etudes in Combinatorial Mathematics", second edition

A collection of sets $\Fscr$ has the $(p,q)$-property if out of every $p$ elements of $\Fscr$ there are $q$ that have a point in common. A transversal of a collection of sets $\Fscr$ is a set $A$ that intersects every member of $\Fscr$. Grünbaum conjectured that every family $\Fscr$ of closed, convex sets in the plane with the $(4,3)$-property and at least two elements that are compact has a transversal of bounded cardinality. Here we construct a counterexample to his conjecture. On the positive side, we also show that if such a collection $\Fscr$ contains two {\em disjoint} compacta then there is a transveral of cardinality at most 13.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Integer realizations of disk and segment graphs

A disk graph is the intersection graph of disks in the plane, a unit disk graph is the intersection graph of same radius disks in the plane, and a segment graph is an intersection graph of line segments in the plane. It can be seen that every disk graph can be realized by disks with centers on the integer grid and with integer radii; and similarly every unit disk graph can be realized by disks with centers on the integer grid and equal (integer) radius; and every segment graph can be realized by segments whose endpoints lie on the integer grid. Here we show that there exist disk graphs on $n$ vertices such that in every realization by integer disks at least one coordinate or radius is $2^{2^{Ω(n)}}$ and on the other hand every disk graph can be realized by disks with integer coordinates and radii that are at most $2^{2^{O(n)}}$; and we show the analogous results for unit disk graphs and segment graphs. For (unit) disk graphs this answers a question of Spinrad, and for segment graphs this improves over a previous result by Kratochv\'ıl and Matou{š}ek.

0 citations0 reviewsNo code linkedOpen access