Abstract. A celebrated conjecture of Tuza states that in any finite graph the minimum size of a cover of triangles by edges is at most twice the maximum size of a set of edge-disjoint triangles. For an [Formula: see text]-uniform hypergraph ([Formula: see text]-graph) [Formula: see text], let [Formula: see text] be the minimum size of a cover of edges by [Formula: see text]-sets of vertices, and let [Formula: see text] be the maximum size of a set of edges pairwise intersecting in fewer than [Formula: see text] vertices. Aharoni and Zerbib proposed the following generalization of Tuza’s conjecture: For any [Formula: see text]-graph [Formula: see text], [Formula: see text]. Let [Formula: see text] be the uniformly random [Formula: see text]-graph on [Formula: see text] vertices. We show that for [Formula: see text] and any [Formula: see text], [Formula: see text] satisfies the Aharoni–Zerbib conjecture with high probability (w.h.p.), i.e., with probability approaching 1 as [Formula: see text]. We also show that there is a [Formula: see text] such that for any [Formula: see text] and any [Formula: see text], [Formula: see text] w.h.p. Furthermore, we may take [Formula: see text], for any [Formula: see text], by restricting to sufficiently large [Formula: see text] (depending on [Formula: see text]).

We show that for all sufficiently large $d$, the uniform proper 3-coloring model (in physics called the 3-state antiferromagnetic Potts model at zero temperature) on ${\mathbb Z}^d$ admits multiple maximal-entropy Gibbs measures. This is a consequence of the following combinatorial result: if a proper 3-coloring is chosen uniformly from a box in ${\mathbb Z}^d$, conditioned on color 0 being given to all the vertices on the boundary of the box which are at an odd distance from a fixed vertex $v$ in the box, then the probability that $v$ gets color 0 is exponentially small in $d$. The proof proceeds through an analysis of a certain type of cutset separating $v$ from the boundary of the box and builds on techniques developed by Galvin and Kahn in their proof of phase transition in the hard-core model on ${\mathbb Z}^d$. Building further on these techniques, we study local Markov chains for sampling proper 3-colorings of the discrete torus ${\mathbb Z}^d_n$. We show that there is a constant $\rho \approx 0.22$ such that for all even $n \geq 4$ and $d$ sufficiently large, if ${\mathcal M}$ is a Markov chain on the set of proper 3-colorings of ${\mathbb Z}^d_n$ that updates the color of at most $\rho n^d$ vertices at each step and whose stationary distribution is uniform, then the mixing time of ${\mathcal M}$ (the time taken for ${\mathcal M}$ to reach a distribution that is close to uniform, starting from an arbitrary coloring) is essentially exponential in $n^{d-1}$.

The classical hard core model from statistical physics, with activity [Formula: see text] and capacity [Formula: see text], on a graph [Formula: see text], concerns a probability measure on the set [Formula: see text] of independent sets of [Formula: see text], with the measure of each independent set [Formula: see text] being proportional to [Formula: see text]. Ramanan et al. [K. Ramanan, A. Sengupta, I. Ziedins and P. Mitra, Adv. Appl. Probab., 34 (2002), pp. 1–27] proposed a generalization of the hard core model as an idealized model of multicasting in communication networks. In this generalization, the multistate hard core model, the capacity [Formula: see text] is allowed to be a positive integer, and a configuration in the model is an assignment of states from [Formula: see text] to [Formula: see text] (the set of nodes of [Formula: see text]) subject to the constraint that the states of adjacent nodes may not sum to more than [Formula: see text]. The activity associated to state [Formula: see text] is [Formula: see text], so that the probability of a configuration [Formula: see text] is proportional to [Formula: see text]. In this work, we consider this generalization when [Formula: see text] is an infinite rooted [Formula: see text]-ary tree and prove rigorously some of the conjectures made by Ramanan et al. In particular, we show that the [Formula: see text] model exhibits a (first-order) phase transition at a larger value of [Formula: see text] than the [Formula: see text] model exhibits its (second-order) phase transition. In addition, for large [Formula: see text] we identify a short interval of values for [Formula: see text] above which the model exhibits phase coexistence and below which there is phase uniqueness. For odd [Formula: see text], this transition occurs in the region of [Formula: see text], while for even [Formula: see text], it occurs around [Formula: see text]. In the latter case, the transition is first-order.

Adaptive power topology control (APTC) is a local algorithm for constructing a one-parameter family of θ-graphs, where each node increases power until it has a neighbor in every θ sector around it.We show it is possible to use such a local geometric θ-constraint to ensure full network connectivity, and consider tradeoffs between assumptions about the wireless footprint and constraints on the boundary nodes. In particular, we show that if the boundary nodes can communicate with neighboring boundary nodes and all interior nodes satisfy a θI π constraint, we can guarantee connectivity for any arbitrary wireless footprint. If we relax the boundary assumption and instead impose a θB < 3π/2 constraint on the boundary nodes, together with the θI < π constraint on interior nodes, we can guarantee full network connectivity using only a "weak-monotonicity" footprint assumption. The weak-monotonicity model, introduced herein, is much less restrictive than the disk model of coverage and captures aspects of the spatial correlations inherent in signal propagation and noise. We show that under the idealized disk model of coverage, APTC constructs graphs that are sparse. Finally, we show that if the wireless footprint has sufficiently small "eccentricity", then there is some θ for which greedy geometric routing always succeeds.