As COVID-19 hounds the world, the common cause of finding a swift solution to manage the pandemic has brought together researchers, institutions, governments, and society at large. The Internet of Things (IoT), artificial intelligence (AI)-including machine learning (ML) and Big Data analytics-as well as Robotics and Blockchain, are the four decisive areas of technological innovation that have been ingenuity harnessed to fight this pandemic and future ones. While these highly interrelated smart and connected health technologies cannot resolve the pandemic overnight and may not be the only answer to the crisis, they can provide greater insight into the disease and support frontline efforts to prevent and control the pandemic. This article provides a blend of discussions on the contribution of these digital technologies, propose several complementary and multidisciplinary techniques to combat COVID-19, offer opportunities for more holistic studies, and accelerate knowledge acquisition and scientific discoveries in pandemic research. First, four areas, where IoT can contribute are discussed, namely: 1) tracking and tracing; 2) remote patient monitoring (RPM) by wearable IoT (WIoT); 3) personal digital twins (PDTs); and 4) real-life use case: ICT/IoT solution in South Korea. Second, the role and novel applications of AI are explained, namely: 1) diagnosis and prognosis; 2) risk prediction; 3) vaccine and drug development; 4) research data set; 5) early warnings and alerts; 6) social control and fake news detection; and 7) communication and chatbot. Third, the main uses of robotics and drone technology are analyzed, including: 1) crowd surveillance; 2) public announcements; 3) screening and diagnosis; and 4) essential supply delivery. Finally, we discuss how distributed ledger technologies (DLTs), of which blockchain is a common example, can be combined with other technologies for tackling COVID-19.

We systematically study a natural problem in extremal graph theory, to minimize the number of edges in a graph with a fixed number of vertices, subject to a certain local condition: each vertex must be in a copy of a fixed graph $H$. We completely solve this problem when $H$ is a clique, as well as more generally when $H$ is any regular graph with degree at least about half its number of vertices. We also characterize the extremal graphs when $H$ is an Erdös--Rényi random graph. The extremal structures turn out to have the similar form as the conjectured extremal structures for a well-studied but elusive problem of similar flavor with local constraints: to maximize the number of copies of a fixed clique in graphs in which all degrees have a fixed upper bound.

An $\epsilon$-distance-uniform graph is one with a critical distance $d$ such that from every vertex, all but at most an $\epsilon$-fraction of the remaining vertices are at distance exactly $d$. Motivated by the theory of network creation games, Alon, Demaine, Hajiaghayi, and Leighton made the following conjecture of independent interest: that every $\epsilon$-distance-uniform graph (and, in fact, a broader class of $\epsilon$-distance-almost-uniform graphs) has critical distance at most logarithmic in the number of vertices $n$. We disprove this conjecture and characterize the asymptotics of this extremal problem. Specifically, for $\frac1n \le \epsilon \le \frac1{\log n}$, we construct $\epsilon$-distance-uniform graphs with critical distance $2^{\Omega(\frac{\log n}{\log \epsilon^{-1}})}$. We also prove an upper bound on the critical distance of the form $2^{O(\frac{\log n}{\log \epsilon^{-1}})}$ for all $\epsilon$ and $n$. Our lower bound construction introduces a novel method inspired by the Tower of Hanoi puzzle and may itself be of independent interest.

The Internet has emerged as perhaps the most important network in modern computing, but rather miraculously, it was created through the individual actions of a multitude of agents rather than by a central planning authority. This motivates the game-theoretic study of network formation, and our article considers one of the most well-studied models, originally proposed by Fabrikant et al. In the model, each of n agents corresponds to a vertex, which can create edges to other vertices at a cost of α each, for some parameter α. Every edge can be freely used by every vertex, regardless of who paid the creation cost. To reflect the desire to be close to other vertices, each agent’s cost function is further augmented by the sum total of all (graph-theoretic) distances to all other vertices. Previous research proved that for many regimes of the (α, n ) parameter space, the total social cost (sum of all agents’ costs) of every Nash equilibrium is bounded by at most a constant multiple of the optimal social cost. In algorithmic game-theoretic nomenclature, this approximation ratio is called the price of anarchy. In our article, we significantly sharpen some of those results, proving that for all constant nonintegral α > 2, the price of anarchy is in fact 1 + o (1); that is, not only is it bounded by a constant, but also it tends to 1 as n → ∞. For constant integral α ⩾ 2, we show that the price of anarchy is bounded away from 1. We provide quantitative estimates on the rates of convergence for both results.

A central challenge in social choice theory arises from the fact that there is no fair way to deterministically select a winner in an election among more than two candidates; the only definite collective preferences are between individual pairs of candidates. Combinatorially, one may summarize this information with a graph-theoretic tournament on $n$ vertices (one per candidate), placing an edge from $u$ to $v$ if $u$ would beat $v$ in an election between only those two candidates (no ties are permitted). One well-studied procedure for selecting a winner is to specify a binary tree whose leaves are labeled by the candidates and evaluate it by running pairwise elections between the pairs of leaves, sending the winners to successive rounds of pairwise elections which ultimately terminate with a single winner. This structure is called a voting tree. Much research has investigated which functions on tournaments are computable in this way. Fischer, Procaccia, and Samorodnitsky quantitatively studied the computability of the Copeland rule, which returns a vertex of maximum out-degree in the given tournament. Perhaps surprisingly, the best previously known voting tree could only guarantee a returned out-degree of at least $\log_2 n$, despite the fact that every tournament has a vertex of degree at least $\frac{n-1}{2}$. In this paper, we present three constructions, the first of which substantially improves this guarantee to $\Theta(\sqrt{n})$. The other two demonstrate the richness of the voting tree universe with a tree that resists manipulation and a tree which implements arithmetic modulo three.

An old problem raised independently by Jacobson and Schönheim seeks to determine the maximum $s$ for which every graph with $m$ edges contains a pair of edge-disjoint isomorphic subgraphs with $s$ edges. In this paper we determine this maximum up to a constant factor. We show that every $m$-edge graph contains a pair of edge-disjoint isomorphic subgraphs with at least $c (m\log m)^{2/3}$ edges for some absolute constant $c$, and find graphs where this estimate is off only by a multiplicative constant. Our results improve bounds of Erdös, Pach, and Pyber from 1987.

The following distributed coalescence protocol was introduced by Dahlia Malkhi in 2006 motivated by applications in social networking. Initially there are n agents wishing to coalesce into one cluster via a decentralized stochastic process, where each round is as follows: Every cluster flips a fair coin to dictate whether it is to issue or accept requests in this round. Issuing a request amounts to contacting a cluster randomly chosen proportionally to its size. A cluster accepting requests is to select an incoming one uniformly (if there are such) and merge with that cluster. Empirical results by Fernandess and Malkhi suggested the protocol concludes in O(log n) rounds with high probability, whereas numerical estimates by Oded Schramm, based on an ingenious analytic approximation, suggested that the coalescence time should be super-logarithmic. Our contribution is a rigorous study of the stochastic coalescence process with two consequences. First, we confirm that the above process indeed requires super-logarithmic time w.h.p., where the inefficient rounds are due to oversized clusters that occasionally develop. Second, we remedy this by showing that a simple modification produces an essentially optimal distributed protocol: If clusters favor their smallest incoming merge request then the process does terminate in O(log n) rounds w.h.p., and simulations show that the new protocol readily outperforms the original one. Our upper bound hinges on a potential function involving the logarithm of the number of clusters and the cluster-susceptibility, carefully chosen to form a supermartingale. The analysis of the lower bound builds upon the novel approach of Schramm which may find additional applications: Rather than seeking a single parameter that controls the system behavior, instead one approximates the system by the Laplace transform of the entire cluster-size distribution.

Consider a 3-uniform hypergraph H with n vertices. A tight Hamilton cycle C ⊂ H is a collection of n edges for which there is an ordering of the vertices v1, …, vn where every triple of consecutive vertices {vi, vi+1, vi+2} is an edge of C (indices considered modulo n). We develop new techniques which show that under certain natural pseudo-random conditions, almost all edges of H can be covered by edge-disjoint tight Hamilton cycles, for n divisible by 4. Consequently, random 3-uniform hypergraphs can be almost completely packed with tight Hamilton cycles whp, for n divisible by 4 and p not too small. Along the way, we develop a similar result for packing Hamilton cycles in pseudo-random digraphs with even numbers of vertices.