Abstract. Motivated by the Beck–Fiala conjecture, we study the discrepancy problem in two related models of random hypergraphs on [Formula: see text] vertices and [Formula: see text] edges. In the first model, each of the [Formula: see text] edges is constructed by placing each vertex into the edge independently with probability [Formula: see text], where [Formula: see text] is a parameter satisfying [Formula: see text] and [Formula: see text]. In the second model, each vertex independently chooses a subset of [Formula: see text] edge labels from [Formula: see text] uniformly at random. Edge [Formula: see text] is then defined to be exactly those vertices whose [Formula: see text]-subsets include label [Formula: see text]. In the sparse regime, i.e., when [Formula: see text], we show that with high probability a random hypergraph from either model has discrepancy at least [Formula: see text]. In the dense regime, i.e., when [Formula: see text], we show that with high probability a random hypergraph from either model has discrepancy at least [Formula: see text], where [Formula: see text]. Furthermore, we obtain nearly matching asymptotic upper bounds on the discrepancy. Specifically, we apply the partial coloring lemma of Lovett and Meka to show that, in the dense regime, with high probability the two random hypergraph models each have discrepancy [Formula: see text]. In fact, in a significant parameter range we can tighten our analysis to get an upper bound which matches our lower bound up to a constant factor. This result is algorithmic, and together with the work of Bansal and Meka [ On the discrepancy of random low degree set systems, in Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp. 2557–2564] characterizes how the discrepancy of each random hypergraph transitions from [Formula: see text] to [Formula: see text] as [Formula: see text] increases from [Formula: see text] to [Formula: see text].

We study the arboricity A and the maximum number T of edge-disjoint spanning trees of the classical random graph (n, p). For all p(n) ∊ [0,1], we show that, with high probability T is precisely the minimum between δ and ⌊m/(n – 1)⌋, where δ is the smallest degree of the graph and m denotes the number of edges. Moreover, we explicitly determine a sharp threshold value for p such that: above this threshold, T equals ⌊m/(n – 1)⌋ and A equals ⌈m/(n – 1)⌉; and below this threshold, T equals δ, and we give a two-value concentration result for the arboricity A in that range. Finally, we include a stronger version of these results in the context of the random graph process where the edges are sequentially added one by one. A direct application of our result gives a sharp threshold for the maximum load being at most k in the two-choice load balancing problem, where k → ∞.

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 present a model of the establishment and maintenance of communication between mobile agents. We assume that the agents move through a fixed environment modeled by a motion graph and are able to communicate if they are within distance at most d of each other. As the agents move randomly, we analyze the evolution in time of the connectivity between a set of w agents, asymptotically for a large number N of vertices, when w also grows large. The particular topologies of the environment we study here are the cycle and the toroidal grid.

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$.