In 1990 Bender, Canfield, and McKay gave an asymptotic formula for the number of connected graphs on
In this paper, we consider a randomized greedy algorithm for independent sets in
- Award ID(s):
- 1800832
- NSF-PAR ID:
- 10237374
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 59
- Issue:
- 1
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- p. 79-95
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract with m edges, whenever and . We give an asymptotic formula for the number of connected r‐uniform hypergraphs on with m edges, whenever is fixed and with , that is, the average degree tends to infinity. This complements recent results of Behrisch, Coja‐Oghlan, and Kang (the case ) and the present authors (the case , ie, “nullity” or “excess” o (n )). The proof is based on probabilistic methods, and in particular on a bivariate local limit theorem for the number of vertices and edges in the largest component of a certain random hypergraph. The arguments are much simpler than in the sparse case; in particular, we can use “smoothing” techniques to directly prove the local limit theorem, without needing to first prove a central limit theorem. -
more » « less
Abstract In this paper we provide an algorithm that generates a graph with given degree sequence uniformly at random. Provided that
, where is the maximal degree and m is the number of edges, the algorithm runs in expected timeO (m ). Our algorithm significantly improves the previously most efficient uniform sampler, which runs in expected timefor the same family of degree sequences. Our method uses a novel ingredient which progressively relaxes restrictions on an object being generated uniformly at random, and we use this to give fast algorithms for uniform sampling of graphs with other degree sequences as well. Using the same method, we also obtain algorithms with expected run time which is (i) linear for power‐law degree sequences in cases where the previous best was O (n 4.081), and (ii)O (nd +d 4) ford ‐regular graphs when, where the previous best was O (nd 3). -
more » « less
Abstract We study a new geometric bootstrap percolation model,
line percolation , on thed ‐dimensional integer grid. In line percolation with infection parameter r , infection spreads from a subsetof initially infected lattice points as follows: if there exists an axis‐parallel line L withr or more infected lattice points on it, then every lattice point ofon L gets infected, and we repeat this until the infection can no longer spread. The elements of the setA are usually chosen independently, with some densityp , and the main question is to determine, the density at which percolation (infection of the entire grid) becomes likely. In this paper, we determine up to a multiplicative factor of and up to a multiplicative constant as for every fixed . We also determine the size of the minimal percolating sets in all dimensions and for all values of the infection parameter. -
more » « less
Abstract For graphs
G andF , writeif any coloring of the edges of G withcolors yields a monochromatic copy of the graph F . Supposeis obtained from a graph S withs vertices and maximum degreed by subdividing its edgesh times (that is, by replacing the edges ofS by paths of lengthh + 1). We prove that there exists a graphG with no more thanedges for which holds, provided that . We also extend this result to the case in which Q is a graph with maximum degreed onq vertices with the property that every pair of vertices of degree greater than 2 are distance at leasth + 1 apart. This complements work of Pak regarding the size Ramsey number of “long subdivisions” of bounded degree graphs. -
more » « less
Abstract The classical Hadwiger conjecture dating back to 1940s states that any graph of chromatic number at least
r has the clique of orderr as a minor. Hadwiger's conjecture is an example of a well‐studied class of problems asking how large a clique minor one can guarantee in a graph with certain restrictions. One problem of this type asks what is the largest size of a clique minor in a graph onn vertices of independence numberat most r . If true Hadwiger's conjecture would imply the existence of a clique minor of order. Results of Kühn and Osthus and Krivelevich and Sudakov imply that if one assumes in addition that G isH ‐free for some bipartite graphH then one can find a polynomially larger clique minor. This has recently been extended to triangle‐free graphs by Dvořák and Yepremyan, answering a question of Norin. We complete the picture and show that the same is true for arbitrary graphH , answering a question of Dvořák and Yepremyan. In particular, we show that any‐free graph has a clique minor of order , for some constant depending only on s . The exponent in this result is tight up to a constant factor in front of theterm.
