BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Tobias Muller contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We provide a hand-checkable proof for Lemma 4.9 in the paper "Logical limit laws for minor-closed classes of graphs" by Heinig, Muller, Noy and Taraz.
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$.
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$.
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.