Explore the vast range of titles available.

This paper analyzes a variation on the well-known \"power of two choices\" allocation algorithms. Classically, the smallest of \\(d\\) randomly-chosen options is selected. We investigate what happens when the largest of \\(d\\) randomly-chosen options is selected. This process generates a power-law-like distribution: the \\(i^{th}\\)-smallest value scales with \\(i^{d-1}\\), where \\(d\\) is the number of randomly-chosen options, with high probability. We give a formula for the expectation and show the distribution is concentrated around the expectation

We introduce a new game played on graphs, ``Agents and Adversary\". This game is reminiscent of ``Cops and Robbers\" but has some fundamental differences. We classify infinite families of graphs as Agents-win and Adversary-win. We then define a new type of graph symmetry and use it to define a winning strategy for Adversary. Finally, we give tight upper and lower bounds for Agents' time-to-win on several infinite families of graphs.

For a rooted graph $G$, let $EV(G;p)$ be the expected number of vertices reachable from the root when each edge has an independent probability $p$ of operating successfully. We examine combinatorial properties of this polynomial, proving that $G$ is $k$-edge connected if and only if $EV'(G;1)=\\cdots=EV^{k-1}(G;1)=0$. We find bounds on the first and second derivatives of $EV(G;p)$; applications yield characterizations of rooted paths and cycles in terms of the polynomial. We prove reconstruction results for rooted trees and a negative result concerning reconstruction of more complicated rooted graphs. We also prove that the norm of the largest root of $EV(G;p)$ in $\\mathbb{Q}[i]$ gives a sharp lower bound on the number of vertices of $G$.

In this paper, we look at and expand the problems of dispersion and Byzantine dispersion of mobile robots on a graph, introduced by Augustine and Moses~Jr.~[ICDCN~2018] and by Molla, Mondal, and Moses~Jr.~[ALGOSENSORS~2020], respectively, to graphs where nodes have variable capacities. We use the idea of a single shepherd, a more powerful robot that will never act in a Byzantine manner, to achieve fast Byzantine dispersion, even when other robots may be strong Byzantine in nature. We also show the benefit of a shepherd for dispersion on capacitated graphs when no Byzantine robots are present.

In this paper, we revisit the problem of \\textsc{Broadcast}, introduced by Das, Giachoudis, Luccio, and Markou [OPODIS, 2020], where \\(k+1\\) agents are initially placed on an \\(n\\) node dynamic graph, where \\(1\\) agent has a message that must be broadcast to the remaining \\(k\\) ignorant agents. The original paper studied the relationship between the number of agents needed to solve the problem and the edge density of the graph. The paper presented strong evidence that edge density of a graph, or the number of redundant edges within the graph, may be the correct graph property to accurately differentiate whether \\(k= o(n)\\) agents (low edge density) or \\(k = \\Omega(n)\\) agents (high edge density) are needed to solve the problem. In this paper, we show that surprisingly, edge density may not in fact be the correct differentiating property. The original paper presents graphs with edge density \\(1.1\\overline{6}\\) that require \\(\\Omega(n)\\) agents, however, we construct graphs with edge density \\(> 1.1\\overline{6}\\) and develop an algorithm to solve the problem on those graphs using only \\(o(n)\\) agents. We subsequently show that the relationship between edge density and number of agents is fairly weak by first constructing graphs with edge density tending to \\(1\\) from above that require \\(\\Omega(n/f(n))\\) agents to solve, for any function \\(f(n) \\to \\infty\\) as \\(n \\to \\infty\\). We then construct an infinite family of graphs with edge density \\(< \\rho\\) requiring exactly \\(k\\) ignorant agents to solve \\textsc{Broadcast}, for any \\(k>0\\) and \\(\\rho>1\\).

Given a graph \\(G\\) and a target graph \\(H\\), an \\(H\\)-coloring of \\(G\\) is an adjacency-preserving vertex map from \\(G\\) to \\(H\\). By appropriate choice of \\(H\\), these colorings can express, for instance, the independent sets or proper vertex colorings of \\(G\\). Sidorenko proved that for any \\(H\\), the \\(n\\)-vertex star admits at least as many \\(H\\)-colorings as any other \\(n\\)-vertex tree, but the minimization question remains open in general. For many graphs \\(H\\), path graphs are among the trees with the fewest \\(H\\)-colorings, but work of Leontovich and subsequently Csikvári and Lin shows that there is a graph \\(E_7\\) on seven vertices and a target graph \\(H\\) for which there are strictly fewer \\(H\\)-colorings of \\(E_7\\) than of the path on seven vertices. We introduce a new strategy for enumerating homomorphisms from path-like trees to highly symmetric target graphs that allows us to make the previous observations completely explicit and extend them to infinitely many \\(n\\) beyond \\(n=7\\). In particular, we exhibit a target graph \\(H\\) with the property that for each sufficiently large \\(n\\), there is a tree \\(E_n\\) on \\(n\\) vertices that admits strictly fewer \\(H\\)-colorings than the path on \\(n\\) vertices.

Given a graph \\(G\\) and a target graph \\(H\\), an \\(H\\)-coloring of \\(G\\) is an adjacency-preserving vertex map from \\(G\\) to \\(H\\). The number of \\(H\\)-colorings of \\(G\\), \\(\\hom(G,H)\\), has been studied for many classes of \\(G\\) and \\(H\\). In particular, extremal questions of maximizing and minimizing \\(\\hom(G,H)\\) have been considered when \\(H\\) is a clique or \\(G\\) is a tree. In this paper, we develop a new technique using automorphisms of \\(H\\) to show that \\(\\hom(T,H)\\) is minimized by paths as \\(T\\) varies over trees on a fixed number of vertices. We introduce the term Hoffman-London to refer to graphs that are minimal in this sense. In particular, we define an automorphic similarity matrix which is used to compute \\(\\hom(T,H)\\) and give matrix conditions under which \\(H\\) is Hoffman-London. We then apply this technique to identify several families of graphs that are Hoffman-London, including loop threshold graphs and some with applications in statistical physics (e.g. the Widom-Rowlinson model). By combining our approach with a few other observations, we fully characterize the minimizing trees for all graphs \\(H\\) on three or fewer vertices.

Let \\(t(H;G)\\) be the homomorphism density of a graph \\(H\\) into a graph \\(G\\). Sidorenko's conjecture states that for any bipartite graph \\(H\\), \\(t(H;G)\\geq t(K_2;G)^{|E(H)|}\\) for all graphs \\(G\\). It is already known that such inequalities cannot be certified through the sums of squares method when \\(H\\) is a so-called trivial square. In this paper, we investigate recent results about Sidorenko's conjecture and classify those involving trivial versus non-trivial squares. We then present some computational results. In particular, we categorize the bipartite graphs \\(H\\) on at most 7 edges for which \\(t(H;G)\\geq t(K_2;G)^{|E(H)|}\\) has a sum of squares certificate. We then discuss other limitations for sums of squares proofs beyond trivial squares.

Graphs that are squares under the gluing algebra arise in the study of homomorphism density inequalities such as Sidorenko's conjecture. Recent work has focused on these homomorphism density applications. This paper takes a new perspective and focuses on the graph properties of arbitrary square graphs, not only those relevant to homomorphism conjectures and theorems. We develop a set of necessary and/or sufficient conditions for a graph to be square. We apply these conditions to categorize several classical families of graphs as square or not. In addition, we create infinite families of square graphs by proving that joins and Cartesian, direct, strong, and lexicographic products of square graphs with arbitrary graphs are square.