Let $\mathcal F$ be an antichain of finite subsets of $\mathbb N$. How quickly can the quantities $|\mathcal{F}\cap 2^{[n]}|$ grow as $n\to\infty$? We show that for any sequence $(f_n)_{n\ge n_0}$ of positive integers satisfying $\sum_{n=n_0}^\infty f_n/2^n \le 1/4$ and $f_n\le f_{n+1}\le 2f_n$, there exists an infinite antichain $\mathcal{F}$ of finite subsets of $\mathbb{N}$ such that $|\F\cap 2^{[n]}| \geq f_n$ for all $n\ge n_0$. It follows that for any $\varepsilon>0$ there exists an antichain $\mathcal{F}\subseteq 2^{\mathbb{N}}$ such that $\liminf_{n \to \infty} |\mathcal{F}\cap 2^{[n]}| \cdot \big(\frac{2^n}{n\log^{1+\varepsilon} n}\big)^{-1} > 0.$ This resolves a problem of Sudakov, Tomon, and Wagner in a strong form and is essentially tight.

A hypergraph is $k$-irregular if there is no set of $k$ vertices all of which have the same degree. We asymptotically determine the probability that a random uniform hypergraph is $k$-irregular.

We prove that in a random $3$-uniform or $4$-uniform hypergraph of order $n$ the probability that some two vertices have the same degree tends to one as $n\to\infty$.

The problem of designing policies for in-network function computation with minimum energy consumption subject to a latency constraint is considered. The scaling behavior of the energy consumption under the latency constraint is analyzed for random networks, where the nodes are uniformly placed in growing regions and the number of nodes goes to infinity. The special case of sum function computation and its delivery to a designated root node is considered first. A policy which achieves order-optimal average energy consumption in random networks subject to the given latency constraint is proposed. The scaling behavior of the optimal energy consumption depends on the path-loss exponent of wireless transmissions and the dimension of the Euclidean region where the nodes are placed. The policy is then extended to computation of a general class of functions which decompose according to maximal cliques of a proximity graph such as the k-nearest neighbor graph or the geometric random graph. The modified policy achieves order-optimal energy consumption albeit for a limited range of latency constraints.

Although random deployment is widely used in theoretical analysis of coverage and connectivity, and evaluation of various algorithms (e.g., sleep-wakeup), it has often been considered too expensive as compared to optimal deterministic deployment patterns when deploying sensors in real-life. Roughly speaking, a factor of log n additional sensors are needed in random deployment as compared to optimal deterministic deployment if n sensors are needed in a random deployment. This may be an illusion however, since all real-life large-scale deployments strategies result in some randomness, two prime sources being placement errors and sensor failures, either at the time of deployment or afterwards. In this paper, we consider the effects of placement errors and random failures on the density needed to achieve full coverage when sensors are deployed randomly versus deterministically. We compare three popular strategies for deployment. In the first strategy, sensors are deployed in an optimal lattice but enough sensors are colocated at each lattice point to compensate for failure and placement errors. In the second, only one sensor is deployed at each lattice point but lattice spacing is sufficiently shrunk to achieve a desired quality of coverage in the presence of failure and placement errors. In the third, a random deployment is used with appropriate density. We derive explicit expressions for the density needed for each of the three strategies to achieve a given quality of coverage, which are of independent interest. In comparing the three deployments, we find that if errors in placement are half the sensing range and failure probability is 50%, random deployment needs only around 10% higher density to provide a similar quality of coverage as the other two. We provide a comprehensive comparison to help a practitioner decide the lowest cost deployment strategy in real-life.

Tracking of movements such as that of people, animals, vehicles, or of phenomena such as fire, can be achieved by deploying a wireless sensor network. So far only prototype systems have been deployed and hence the issue of scale has not become critical. Real-life deployments, however, will be at large scale and achieving this scale will become prohibitively expensive if we require every point in the region to be covered (i.e., full coverage), as has been the case in prototype deployments. In this paper we therefore propose a new model of coverage, called trap coverage, that scales well with large deployment regions. A sensor network providing trap coverage guarantees that any moving object or phenomena can move at most a (known) displacement before it is guaranteed to be detected by the network, for any trajectory and speed. Applications aside, trap coverage generalizes the de-facto model of full coverage by allowing holes of a given maximum diameter. From a probabilistic analysis perspective, the trap coverage model explains the continuum between percolation (when coverage holes become finite) and full coverage (when coverage holes cease to exist). We take first steps toward establishing a strong foundation for this new model of coverage. We derive reliable, explicit estimates for the density needed to achieve trap coverage with a given diameter when sensors are deployed randomly. Our density estimates are more accurate than those obtained using asymptotic critical conditions. We show by simulation that our analytical predictions of density are quite accurate even for small networks. We then propose polynomial-time algorithms to determine the level of trap coverage achieved once sensors are deployed on the ground. Finally, we point out several new research problems that arise by the introduction of the trap coverage model.

Consider words over an alphabet with n letters. Fisher [Amer. Math. Monthly, 96 (1989), pp. 610–614] calculated the number of distinct words of length $\ell$ assuming certain pairs of letters commute. In this paper we are interested in a more general setting where the pairs of letters that commute at a certain position of a word depend on the initial segment of the word. In particular, we show that if for each word at each position any letter fails to commute with at most a constant number of other letters, then the number of distinct words of length $\ell$ is at most $C^{n+\ell}$ for some constant C. We use this result to obtain a lower bound on the number of diagonal flips required in the worst case to transform one n-vertex labeled triangulated planar graph into some other one. This has previously been proved in [D. D. Sleator, R. E. Tarjan, and W. P. Thurston, SIAM J. Discrete Math., 5 (1992), pp. 428–450] by different methods.

Deriving the critical density (which is equivalent to deriving the critical radius or power) to achieve coverage and/or connectivity for random deployments is a fundamental problem in the area of wireless networks. The probabilistic conditions normally derived, however, have limited appeal among practitioners because they areoften asymptotic, i.e., they only make high probability guarantees in the limit of large system sizes. Such conditions are not very useful in practice since deployment regions are always finite. Another major limitation of most existing work on coverage and connectivity is their focus on thick deployment regions (such as a square or a disk). There is no existing work (including traditional percolation theory) that derives critical densities for thin strips (or annuli).

An adjacent vertex distinguishing edge‐coloring of a simple graph G is a proper edge‐coloring of G such that no pair of adjacent vertices meets the same set of colors. The minimum number of colors $\chi^\prime_a(G)$ required to give G an adjacent vertex distinguishing coloring is studied for graphs with no isolated edge. We prove $\chi^\prime_a(G)\le5$ for such graphs with maximum degree $\Delta(G)=3$ and prove $\chi^\prime_a(G)\le\Delta(G)+2$ for bipartite graphs. These bounds are tight. For k‐chromatic graphs G without isolated edges we prove a weaker result of the form $\chi^\prime_a(G)=\Delta(G)+O(\log k)$.

In this paper, various fast transmission strategies for sending information from a source s over a large distance to a target t in ad hoc wireless networks where the nodes are distributed as a Poisson process of intensity is presented. The existence of an infinite component, i.e., percolation, is not sufficient for our problem since the proportion of vertices in the infinite component may be very low. To achieve connectivity the power must increase with the number of vertices, since there is some positive chance that a vertex is isolated. Result shows that with directional transmissions, even with very low power there exist points at arbitrarily large distance that can communicate.