Random @math -intersection graphs have recently received much interest in a wide range of application areas. Broadly speaking, a random @math -intersection graph is constructed by first assigning each vertex a set of items in some random manner, and then putting an undirected edge between all pairs of vertices that share at least @math items (the graph is called a random intersection graph when @math ). A special case of particular interest is a uniform random @math -intersection graph, where each vertex independently selects the same number of items uniformly at random from a common item pool. Another important case is a binomial random @math -intersection graph, where each item from a pool is independently assigned to each vertex with the same probability. Both models have found numerous applications thus far including cryptanalysis, and the modeling of recommender systems, secure sensor networks, online social networks, trust networks and small-world networks (uniform random @math -intersection graphs), as well as clustering analysis, classification, and the design of integrated circuits (binomial random @math -intersection graphs). In this paper, for binomial uniform random @math -intersection graphs, we present results related to @math -connectivity and minimum vertex degree. Specifically, we derive the asymptotically exact probabilities and zero-one laws for the following three properties: (i) @math -vertex-connectivity, (ii) @math -edge-connectivity and (iii) the property of minimum vertex degree being at least @math .
For graph @math , Bloznelis and uczak @cite_17 recently consider the following three properties: (i) the graph has a minimum vertex degree at least @math ; (ii) the graph has a perfect matching; (iii) the graph is connected. They present that when @math is even, for each of these three properties, its probability converges to @math as @math , under conditions @math ( @math is the edge probability), @math and @math for some @math .
@cite_17
2020272293
A graph @math is called @math -full if @math contains a subgraph @math of @math edges such that, for any non-empty @math , @math holds. Here, @math denotes the set of vertices incident to @math . It is known that the family of edge sets of @math -full graphs forms a family of matroid, known as the sparsity matroid of @math . In this paper, we give a constant-time approximation algorithm for the rank of the sparsity matroid of a degree-bounded undirected graph. This leads to a constant-time tester for @math -fullness in the bounded-degree model, (i.e., we can decide with high probability whether an input graph satisfies a property @math or far from @math ). Depending on the values of @math and @math , it can test various properties of a graph such as connectivity, rigidity, and how many spanning trees can be packed. Based on this result, we also propose a constant-time tester for @math -edge-connected-orientability in the bounded-degree model, where an undirected graph @math is called @math -edge-connected-orientable if there exists an orientation @math of @math with a vertex @math such that @math contains @math arc-disjoint dipaths from @math to each vertex @math and @math arc-disjoint dipaths from each vertex @math to @math . A tester is called a one-sided error tester for @math if it always accepts a graph satisfying @math . We show, for @math and (proper) @math , any one-sided error tester for @math -fullness and @math -edge-connected-orientability requires @math queries. We consider the problem of clustering a graph @math into two communities by observing a subset of the vertex correlations. Specifically, we consider the inverse problem with observed variables @math , where @math is the incidence matrix of a graph @math , @math is the vector of unknown vertex variables (with a uniform prior), and @math is a noise vector with Bernoulli @math i.i.d. entries. All variables and operations are Boolean. This model is motivated by coding, synchronization, and community detection problems. In particular, it corresponds to a stochastic block model or a correlation clustering problem with two communities and censored edges. Without noise, exact recovery (up to global flip) of @math is possible if and only the graph @math is connected, with a sharp threshold at the edge probability @math for Erdős-Renyi random graphs. The first goal of this paper is to determine how the edge probability @math needs to scale to allow exact recovery in the presence of noise. Defining the degree rate of the graph by @math , it is shown that exact recovery is possible if and only if @math . In other words, @math is the information theoretic threshold for exact recovery at low-SNR. In addition, an efficient recovery algorithm based on semidefinite programming is proposed and shown to succeed in the threshold regime up to twice the optimal rate. For a deterministic graph @math , defining the degree rate as @math , where @math is the minimum degree of the graph, it is shown that the proposed method achieves the rate @math , where @math is the spectral gap of the graph @math . A problem arising in the design of vacuum systems and having applications to some natural problems of interconnection design is described as follows. (1) Given a set X and subsets @math of @math , satisfying @math , find a graph G with vertex set X and the minimum number of edges such that for any i, the subgraph induced by @math has a connected component containing @math .Two other problems related to this one are the following ones. (2) Given a set X and subsets @math such that @math , find a graph G with vertex set X and the minimum number of edges such that for any i the subgraph @math induced by @math in G is connected. (3) Given a set X and subsets @math such that @math , find a graph G with vertex set X, find a graph G with vertex set X and the minimum number of edges such that for any subset I of @math , the subgraph induced by @math is co... We study constant-time approximation algorithms for bounded-degree graphs, which run in time independent of the number of vertices @math . We present an algorithm that decides whether a vertex is contained in a some fixed maximal independent set with expected query complexity @math , where @math is the degree bound. Using this algorithm, we show constant-time approximation algorithms with certain multiplicative error and additive error @math for many other problems, e.g., the maximum matching problem, the minimum vertex cover problem, and the minimum set cover problem, that run exponentially faster than existing algorithms with respect to @math and @math . Our approximation algorithm for the maximum matching problem can be transformed to a two-sided error tester for the property of having a perfect matching. On the contrary, we show that every one-sided error tester for the property requires at least @math queries. Let @math be a 3-uniform hypergraph of order @math and size @math , and let @math be a subset of vertices of @math . The set @math is a strong transversal in @math if @math contains at least two vertices from every edge of @math . The strong transversal number @math of @math is the minimum size of a strong transversal in @math . We show that @math , and we characterize the hypergraphs that achieve equality in this bound. In particular, we show that the Fano plane is the only connected 3-uniform hypergraph @math of order @math and size @math that achieves equality in this bound. A set @math of vertices in a graph @math is a double total dominating set of @math if every vertex of @math is adjacent to at least two vertices in @math . The minimum cardinality of a double total dominating set of @math is the double total domination number @math of @math . Let @math be a connected graph of order @math with minimum degree at least three. As an application of our hypergraph results, we show that @math with equality if and only if @math is the Heawood graph (equivalently, the incidence bipartite graph of the Fano plane). Further if @math is not the Heawood graph, we show that @math , while if @math is a cubic graph different from the Heawood graph, we show that @math , and this bound is sharp. We present an algorithm for testing the k-vertex-connectivity of graphs with the given maximum degree. The time complexity of the algorithm is independent of the number of vertices and edges of graphs. Fixed degree bound d, a graph G with n vertices and a maximum degree at most d is called e-far from k-vertex-connectivity when at least @math edges must be added to or removed from G to obtain a k-vertex-connected graph with a maximum degree at most d. The algorithm always accepts every graph that is k-vertex-connected and rejects every graph that is e-far from k-vertex-connectivity with a probability of at least 2 3. The algorithm runs in @math time (c>1 is a constant) for (k−1)-vertex-connected graphs, and in @math time (c>1 is a constant) for general graphs. It is the first constant-time k-vertex-connectivity testing algorithm for general k≥4. We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property @math is called a @math -graph . If @math satisfies certain properties, then an n-node m-edge @math -graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2) X has at most @math bits for any continuous superadditive function @math so that there are at most @math distinct @math -node @math -graphs. The methodology is applicable to general classes of graphs; this paper focuses on planar graphs. Examples of such @math include all conjunctions over the following groups of properties: (1) G is a planar graph or a plane graph; (2) @math is directed or undirected; (3) @math is triangulated, triconnected, biconnected, merely connected, or not required to be connected; (4) the nodes of G are labeled with labels from @math for @math ; (5) the edges of G are labeled with labels from @math for @math ; and (6) each node (respectively, edge) of G has at most @math self-loops (respectively, @math multiple edges). Moreover, @math and @math are not required to be O(1) for the cases of @math being a plane triangulation. These examples are novel applications of small cycle separators of planar graphs and are the only nontrivial classes of graphs, other than rooted trees, with known polynomial-time information-theoretically optimal coding schemes. We consider properties of edge-colored vertex-ordered graphs, i.e., graphs with a totally ordered vertex set and a finite set of possible edge colors. We show that any hereditary property of such graphs is strongly testable, i.e., testable with a constant number of queries. We also explain how the proof can be adapted to show that any hereditary property of @math -dimensional matrices over a finite alphabet (where row and column order is not ignored) is strongly testable. The first result generalizes the result of Alon and Shapira [FOCS'05, SICOMP'08], who showed that any hereditary graph property (without vertex order) is strongly testable. The second result answers and generalizes a conjecture of Alon, Fischer and Newman [SICOMP'07] concerning testing of matrix properties. The testability is proved by establishing a removal lemma for vertex-ordered graphs. It states that for any finite or infinite family @math of forbidden vertex-ordered graphs, and any @math , there exist @math and @math so that any vertex-ordered graph which is @math -far from being @math -free contains at least @math copies of some @math (with the correct vertex order) where @math . The proof bridges the gap between techniques related to the regularity lemma, used in the long chain of papers investigating graph testing, and string testing techniques. Along the way we develop a Ramsey-type lemma for @math -partite graphs with "undesirable" edges, stating that one can find a Ramsey-type structure in such a graph, in which the density of the undesirable edges is not much higher than the density of those edges in the graph. Distributed voting is a fundamental topic in distributed computing. In the standard model of pull voting, at each step every vertex chooses a neighbour uniformly at random and adopts its opinion. The voting is completed when all vertices hold the same opinion. In the simplest case, each vertex initially holds one of two different opinions. This partitions the vertices into arbitrary sets A and B. For many graphs, including regular graphs and irrespective of their expansion properties, if both A and B are sufficiently large sets, then pull voting requires @math expected steps, where n is the number of vertices of the graph. In this paper we consider a related class of voting processes based on sampling two opinions. In the simplest case, every vertex v chooses two random neighbours at each step. If both these neighbours have the same opinion, then v adopts this opinion. Otherwise, v keeps its own opinion. Let G be a connected graph with n vertices and m edges. Let P be the transition matrix of a simple random walk on G with second largest eigenvalue @math . We show that if the initial imbalance in degree between the two opinions satisfies @math , then with high probability voting completes in @math steps, and the opinion with the larger initial degree wins. The condition that @math , or only a bound on the conductance of the graph is known, the sampling process can be modified so that voting still provably completes in @math steps with high probability. The modification uses two sampling based on probing to a fixed depth @math from any vertex. In its most general form our voting process allows vertices to bias their sampling of opinions among their neighbours to achieve a desired outcome. This is done by allocating weights to edges. Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of undirected graphs, surprisingly not much has been investigated for directed graphs. In this paper we study @math -edge connectivity problems in directed graphs and, in particular, we consider the computation of the following natural relation: We say that two vertices @math and @math are @math -edge-connected if there are two edge-disjoint paths from @math to @math and two edge-disjoint paths from @math to @math . This relation partitions the vertices into blocks such that all vertices in the same block are @math -edge-connected. Differently from the undirected case, those blocks do not correspond to the @math -edge-connected components of the graph. We show how to compute this relation in linear time so that we can report in constant time if two vertices are @math -edge-connected. We also show how to compute in linear time a sparse certificate for this relation, i.e., a subgraph of the input graph that has @math edges and maintains the same @math -edge-connected blocks as the input graph. We consider secure and reliable connectivity in wireless sensor networks that utilize the heterogeneous random key predistribution scheme. We model the unreliability of wireless links by an on off channel model that induces an Erdős-Renyi graph, while the heterogeneous scheme induces an inhomogeneous random key graph. The overall network can thus be modeled by the intersection of both graphs. We present conditions (in the form of zero-one laws) on how to scale the parameters of the intersection model, so that with high probability: i) all of its nodes are connected to at least @math other nodes, i.e., the minimum node degree of the graph is no less than @math , and ii) the graph is @math -connected, i.e., the graph remains connected even if any @math nodes leave the network. These results are shown to complement and generalize several previous results in the literature. We also present numerical results to support our findings in the finite-node regime. Finally, we demonstrate via simulations that our results are also useful when the on off channel model is replaced with the more realistic disk communication model . When graph Ramsey theory is viewed as a game, "Painter" 2-colors the edges of a graph presented by "Builder". Builder wins if every coloring has a monochromatic copy of a fixed graph @math . In the on-line version, iteratively, Builder presents one edge and Painter must color it. Builder must keep the presented graph in a class @math . Builder wins the game @math if a monochromatic copy of @math can be forced. The on-line degree Ramsey number @math is the least @math such that Builder wins @math when @math is the class of graphs with maximum degree at most @math . Our results include: 1) @math if and only if @math is a linear forest or each component lies inside @math . 2) @math , where @math . 3) @math for a tree @math , where @math and @math are two largest vertex degrees. 4) @math , with @math except for finitely many odd values of @math . 5) @math when @math . The lower bounds come from strategies for Painter that color edges red whenever the red graph remains in a specified class. The upper bounds use a result showing that Builder may assume that Painter plays "consistently". Let G=(V,E) be an n-vertex graph and Md a d-vertex graph, for some constant d. Is Md a subgraph of G? We consider this problem in a model where all n processes are connected to all other processes, and each message contains up to @math bits. A simple deterministic algorithm that requires @math communication rounds is presented. For the special case that Md is a triangle, we present a probabilistic algorithm that requires an expected @math rounds of communication, where t is the number of triangles in the graph, and @math with high probability. We also present deterministic algorithms that are specially suited for sparse graphs. In graphs of maximum degree Δ, we can test for arbitrary subgraphs of diameter D in @math rounds. For triangles, we devise an algorithm featuring a round complexity of @math , where A denotes the arboricity of G. We consider a system of @math servers inter-connected by some underlying graph topology @math . Tasks arrive at the various servers as independent Poisson processes of rate @math . Each incoming task is irrevocably assigned to whichever server has the smallest number of tasks among the one where it appears and its neighbors in @math . Tasks have unit-mean exponential service times and leave the system upon service completion. The above model has been extensively investigated in the case @math is a clique. Since the servers are exchangeable in that case, the queue length process is quite tractable, and it has been proved that for any @math , the fraction of servers with two or more tasks vanishes in the limit as @math . For an arbitrary graph @math , the lack of exchangeability severely complicates the analysis, and the queue length process tends to be worse than for a clique. Accordingly, a graph @math is said to be @math -optimal or @math -optimal when the occupancy process on @math is equivalent to that on a clique on an @math -scale or @math -scale, respectively. We prove that if @math is an Erd o s-R 'enyi random graph with average degree @math , then it is with high probability @math -optimal and @math -optimal if @math and @math as @math , respectively. This demonstrates that optimality can be maintained at @math -scale and @math -scale while reducing the number of connections by nearly a factor @math and @math compared to a clique, provided the topology is suitably random. It is further shown that if @math contains @math bounded-degree nodes, then it cannot be @math -optimal. In addition, we establish that an arbitrary graph @math is @math -optimal when its minimum degree is @math , and may not be @math -optimal even when its minimum degree is @math for any @math . We present the best known algorithms for approximating the minimum-size undirected @math -edge connected spanning subgraph. For simple graphs our approximation ratio is @math . The more precise version of this bound requires @math , and for all such @math it improves the long-standing performance ratio of Cheriyan and Thurimella [SIAM J. Comput., 30 (2000), pp. 528-560], @math . The improvement comes in two steps. First we show that for simple @math -edge connected graphs, any laminar family of degree @math sets is smaller than the general bound ( @math versus @math ). This immediately implies that iterated rounding improves the performance ratio of Cheriyan and Thurimella. The second step carefully chooses good edges for rounding. For multigraphs our approximation ratio is @math . This improves the previous ratio @math [H. N. Gabow, M. X. Goemans, E. Tardos, and D. P. Williamson, Networks, 53 (2009), pp. 345-357]. It is of interest since it is known that for some constant @math , an approximation ratio @math implies @math . Our approximation ratio extends to the minimum-size Steiner network problem, where @math denotes the average vertex demand. The algorithm exploits rounding properties of the first two linear programs in iterated rounding. Suppose that @math is a sequence of finite connected planar graphs, and in each @math a special vertex, called the root, is chosen randomly-uniformly. We introduce the notion of a distributional limit @math of such graphs. Assume that the vertex degrees of the vertices in @math are bounded, and the bound does not depend on @math . Then after passing to a subsequence, the limit exists, and is a random rooted graph @math . We prove that with probability one @math is recurrent. The proof involves the Circle Packing Theorem. The motivation for this work comes from the theory of random spherical triangulations. For an undirected graph and an optimal cyclic list of all its vertices, the cyclic cover time is the expected time it takes a simple random walk to travel from vertex to vertex along the list until it completes a full cycle. The main result of this paper is a characterization of the cyclic cover time in terms of simple and easy-to-compute graph properties. Namely, for any connected graph, the cyclic cover time is @math , where @math is the number of vertices in the graph, @math is the average degree of its vertices, and @math is the average of the inverse of the degree of its vertices. Other results obtained in the processes of proving the main theorem are a similar characterization of minimum resistance spanning trees of graphs, improved bounds on the cover time of graphs, and a simplified proof that the maximum commute time in any connected graph is at most @math . We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in both theory and practice, but all existing algorithms read the entire graph. In this work we design a sublinear-time algorithm for approximating the number of triangles in a graph, where the algorithm is given query access to the graph. The allowed queries are degree queries, vertex-pair queries, and neighbor queries. We show that for any given approximation parameter @math , the algorithm provides an estimate @math such that, with high constant probability, @math , where @math is the number of triangles in the graph @math . The expected query complexity of the algorithm is @math , where @math is the number of vertices in the graph and @math is the number of edges. The expected running time of the algorithm is $( n t^ 1 3 + m^ 3 2 t )... In a coalescing random walk, a set of particles make independent discrete-time random walks on a graph. Whenever one or more particles meet at a vertex, they unite to form a single particle, which then continues a random walk through the graph. Let @math be an undirected and connected graph with @math vertices and @math edges. The coalescence time, @math , is the expected time for all particles to coalesce, when initially one particle is located at each vertex. We study the problem of bounding the coalescence time for general connected graphs and prove that @math . Here @math is the second eigenvalue of the transition matrix of the random walk. To avoid problems arising from, e.g., lack of coalescence on bipartite graphs, we assume the random walk can be made lazy if required. The value of @math is given by @math , where @math is the degree of vertex @math , and @math is the average degree. The parame... We consider the problem of finding a minimum edge cost subgraph of a graph satisfying both given node-connectivity requirements and degree upper bounds on nodes. We present an iterative rounding algorithm of the biset linear programming relaxation for this problem. For directed graphs and @math -out-connectivity requirements from a root, our algorithm computes a solution that is a 2-approximation on the cost, and the degree of each node @math in the solution is at most @math , where @math is the degree upper bound on @math . For undirected graphs and element-connectivity requirements with maximum connectivity requirement @math , our algorithm computes a solution that is a @math -approximation on the cost, and the degree of each node @math in the solution is at most @math . These ratios improve the previous @math -approximation on the cost and @math -approximation on the degrees. Our algorithms can be used to improve approximation ratios for other node-connectivity problems such as undirected $k...