Source author record

Robert B. Ellis

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

ResearcherUnclaimed source record

math.CO math.PR

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2010arXiv

The Renyi-Ulam pathological liar game with a fixed number of lies

The $q$ -round Renyi-Ulam pathological liar game with $k$ lies on the set $[n]:=\{1,...,n\}$ is a 2-player perfect information zero sum game. In each round Paul chooses a subset $A\subseteq [n]$ and Carole either assigns 1 lie to each element of $A$ or to each element of $[n]\setminus A$ . Paul wins if after $q$ rounds there is at least one element with $k$ or fewer lies. The game is dual to the original Renyi-Ulam liar game for which the winning condition is that at most one element has $k$ or fewer lies. We prove the existence of a winning strategy for Paul to the existence of a covering of the discrete hypercube with certain relaxed Hamming balls. Defining $F^*_k(q)$ to be the minimum $n$ such that Paul can win the $q$ -round pathological liar game with $k$ lies and initial set $[n]$ , we find $F^*_1(q)$ and $F^*_2(q)$ exactly. For fixed $k$ we prove that $F_k^*(q)$ is within an absolute constant (depending only on $k$ ) of the sphere bound, $2^q/\binom{q}{\leq k}$ ; this is already known to hold for the original Renyi-Ulam liar game due to a result of J. Spencer.

preprint2005arXiv

Random Geometric Graph Diameter in the Unit Ball

The unit ball random geometric graph $G=G^d_p(λ,n)$ has as its vertices $n$ points distributed independently and uniformly in the $d$ -dimensional unit ball, with two vertices adjacent if and only if their $l_p$ -distance is at most $λ$ . Like its cousin the Erdos-Renyi random graph, $G$ has a connectivity threshold: an asymptotic value for $λ$ in terms of $n$ , above which $G$ is connected and below which $G$ is disconnected (and in fact has isolated vertices in most cases). In the connected zone, we determine upper and lower bounds for the graph diameter of $G$ . Specifically, almost always, $\diam_p(\mathbf{B})(1-o(1))/λ\leq \diam(G) \leq \diam_p(\mathbf{B})(1+O((\ln \ln n/\ln n)^{1/d}))/λ$, where $\diam_p(\mathbf{B})$ is the $\ell_p$ -diameter of the unit ball $\mathbf{B}$ . We employ a combination of methods from probabilistic combinatorics and stochastic geometry.

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.