In this paper we consider a variant of the well-known Achlioptas process for graphs adapted to monotone Boolean functions. Fix a number of choices $r\in \mathbb N$ and a sequence of increasing functions $(f_n)_{n\ge 1}$ such that, for every $n\ge 1$, $f_n:\{0,1\}^n\mapsto \{0,1\}$. Given $n$ bits which are all initially equal to 0, at each step $r$ 0-bits are sampled uniformly at random and are proposed to an agent. Then, the agent selects one of the proposed bits and turns it from 0 to 1 with the goal to reach $f_n^{-1}(1)$ as quickly as possible. We nearly characterize the conditions on $(f_n)_{n\ge 1}$ under which an acceleration by a factor of $r(1+o(1))$ is possible and underline the wide applicability of our results by giving examples from the fields of Boolean functions and graph theory.

We show that in the random hyperbolic graph model as formalized by Gugelmann, Panagiotou, and Peter (2012) in the most interesting range of $\frac12 < \alpha < 1$ the size of the second largest component is $\Theta((\log n)^{1/(1-\alpha)})$. Our research is motivated by the question raised by Bode, Fountoulakis, and Müller (2013) regarding the uniqueness of linear size components in random hyperbolic graphs, which naturally leads to the question regarding the size of the second largest component. We also show that for $\alpha=\frac12$ with constant probability the corresponding size is $\Theta(\log n)$, whereas for $\alpha=1$ it is $\Omega(n^{\delta})$ for some $\delta > 0$.

We give asymptotically exact values for the treewidth ${tw}(G)$ of a random geometric graph $G\in{\mathcal G(n,r)}$ in $[0,\sqrt{n}]^2$. More precisely, let $r_c$ denote the threshold radius for the appearance of the giant component in ${\mathcal G(n,r)}$. We then show that for any constant $0 < r < r_c$, ${tw}(G)=\Theta(\frac{\log n}{\log \log n})$, and for $c$ being sufficiently large, and $r=r(n) \geq c$, ${tw}(G)=\Theta(r \sqrt{n})$. Our proofs show that for the corresponding values of $r$ the same asymptotic bounds also hold for the pathwidth and the treedepth of a random geometric graph.

In this paper, we tackle the problem of designing a random mobility model generating a target node spatial distribution. More specifically, we solve a long standing open problem by presenting two versions of the well-known random waypoint (RWP) mobility model in bounded regions generating a uniform steady-state node spatial distribution. In the first version, named temporal-RWP , we exploit the temporal dimension of node mobility and achieve uniformity by continuously changing the speed of a mobile node as a function of its location and of the density function of trajectories in the movement region R . In the second version, named spatial-RWP , we instead exploit the spatial dimension and achieve uniformity by selecting waypoints according to a suitably defined mix of probability density functions. Both proposed models can be easily incorporated in wireless network simulators, and are thus of practical use. The RWP models presented in this paper allow for the first time completely removing the well-known border effect causing possible inaccuracies in mobile network simulation, thus completing the picture of a “perfect” simulation methodology drawn in existing literature.

We examine a dynamic model for the disruption of information flow in hierarchical social networks by considering the vertex-pursuit game Seepage played in directed acyclic graphs (DAGs). In Seepage, agents attempt to block the movement of an intruder who moves downward from the source node to a sink. The minimum number of such agents required to block the intruder is called the green number. We propose a generalized stochastic model for DAGs with given expected total degree sequence. Seepage and the green number are analyzed in stochastic DAGs in both the cases of a regular and power law degree sequence. For each such sequence, we give asymptotic bounds (and in certain instances, precise values) for the green number.

A unique-path labeling of a simple, finite graph is a labeling of its edges with real numbers such that for every ordered pair of vertices $(u,v)$, there is at most one nondecreasing path from $u$ to $v$. In this paper we prove that any graph on $n$ vertices that admits a unique-path labeling has at most $n \log_2(n)/2$ edges and that this bound is tight for infinitely many values of $n$. Thus we significantly improve on the previously best known bounds. The main tool of the proof is a combinatorial lemma which might be of independent interest. For every $n$ we also construct an $n$-vertex graph that admits a unique-path labeling and has $n\log_2(n)/2 - O(n)$ edges.

We provide the first rigorous analytical results for the connectivity of dynamic random geometric graphs—a model for mobile wireless networks in which vertices move in random directions in the unit torus. The model presented here follows the one described in [11]. We provide precise asymptotic results for the expected length of the connectivity and disconnectivity periods of the network. We believe that the formal tools developed in this work could be extended to be used in more concrete settings and in more realistic models, in the same manner as the development of the connectivity threshold for static random geometric graphs has affected a lot of research done on ad hoc networks.

We show that a randomly chosen $3$-CNF formula over $n$ variables with clauses-to-variables ratio at least $4.4898$ is asymptotically almost surely unsatisfiable. The previous best such bound, due to Dubois in 1999, was $4.506$. The first such bound, independently discovered by many groups of researchers since 1983, was $5.19$. Several decreasing values between $5.19$ and $4.506$ were published in the years between. The probabilistic techniques we use for the proof are, we believe, of independent interest.

We show for an arbitrary $\ell_p$ norm that the property that a random geometric graph $\mathcal G(n,r)$ contains a Hamiltonian cycle exhibits a sharp threshold at $r=r(n)=\sqrt{\frac{\log n}{\alpha_p n}}$, where $\alpha_p$ is the area of the unit disk in the $\ell_p$ norm. The proof is constructive and yields a linear time algorithm for finding a Hamiltonian cycle of $\mathcal{G}(n,r)$ asymptotically almost surely, provided $r=r(n)\ge\sqrt{\frac{\log n}{(\alpha_p -\epsilon)n}}$ for some fixed $\epsilon>0$.