Weak quasi‐randomness for uniform hypergraphs

We study quasi‐random properties of k‐uniform hypergraphs. Our central notion is uniform edge distribution with respect to large vertex sets. We will find several equivalent characterisations of this property and our work can be viewed as an extension of the well known Chung‐Graham‐Wilson theorem for quasi‐random graphs. Moreover, let K_k be the complete graph on k vertices and M(k) the line graph of the graph of the k‐dimensional hypercube. We will show that the pair of graphs (K_k,M(k)) has the property that if the number of copies of both K_k and M(k) in another graph G are as expected in the random graph of density d, then G is quasi‐random (in the sense of the Chung‐Graham‐Wilson theorem) with density close to d. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

1‐Factorizations of pseudorandom graphs

A 1‐factorization of a graph G is a collection of edge‐disjoint perfect matchings whose union is E(G). In this paper, we prove that for any ?>0, an (n,d,λ)‐graph G admits a 1‐factorization provided that n is even, C₀ ≤ d ≤ n?1 (where C₀=C₀(?) is a constant depending only on ?), and λ ≤ d^1??. In particular, since (as is well known) a typical random d‐regular graph G_n,d is such a graph, we obtain the existence of a 1‐factorization in a typical G_n,d for all C₀ ≤ d ≤ n?1, thereby extending to all possible values of d results obtained by Janson, and independently by Molloy, Robalewska, Robinson, and Wormald for fixed d. Moreover, we also obtain a lower bound for the number of distinct 1‐factorizations of such graphs G, which is better by a factor of 2^nd/2 than the previously best known lower bounds, even in the simplest case where G is the complete graph.     

Multiple Phase Transitions in Long‐Range First‐Passage Percolation on Square Lattices

We consider a model of long‐range first‐passage percolation on the d‐dimensional square lattice ?d in which any two distinct vertices x,y ? ?^d are connected by an edge having exponentially distributed passage time with mean ‖ x – y ‖^α+o(1), where α > 0 is a fixed parameter and ‖·‖ is the l¹–norm on ?^d. We analyze the asymptotic growth rate of the set ß_t, which consists of all x ? ?^d such that the first‐passage time between the origin 0 and x is at most t as t → ∞. We show that depending on the values of α there are four growth regimes: (i) instantaneous growth for α < ^d, (ii) stretched exponential growth for α ? d,2d), (iii) superlinear growth for α ? (2d,2d + 1), and finally (iv) linear growth for α > 2d + 1 like the nearest‐neighbor first‐passage percolation model corresponding to α=∞. © 2015 Wiley Periodicals, Inc.     

Spread‐out percolation in ℝd

Fix d ≥ 2, and let X be either ℤ^d or the points of a Poisson process in ℝ^d of intensity 1. Given parameters r and p, join each pair of points of X within distance r independently with probability p. This is the simplest case of a “spread‐out” percolation model studied by Penrose [Ann Appl Probab 3 (1993) 253–276], who showed that, as r → ∞, the average degree of the corresponding random graph at the percolation threshold tends to 1, i.e., the percolation threshold and the threshold for criticality of the naturally associated branching process approach one another. Here we show that this result follows immediately from of a general result of [3] on inhomogeneous random graphs. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Quasi‐random hypergraphs revisited

The quasi‐random theory for graphs mainly focuses on a large equivalent class of graph properties each of which can be used as a certificate for randomness. For k ‐graphs (i.e., k ‐uniform hypergraphs), an analogous quasi‐random class contains various equivalent graph properties including the k ‐discrepancy property (bounding the number of edges in the generalized induced subgraph determined by any given (k ‐ 1) ‐graph on the same vertex set) as well as the k ‐deviation property (bounding the occurrences of “octahedron”, a generalization of 4 ‐cycle). In a 1990 paper (Chung, Random Struct Algorithms 1 (1990) 363‐382), a weaker notion of l ‐discrepancy properties for k ‐graphs was introduced for forming a nested chain of quasi‐random classes, but the proof for showing the equivalence of l ‐discrepancy and l ‐deviation, for 2 ≤ l < k, contains an error. An additional parameter is needed in the definition of discrepancy, because of the rich and complex structure in hypergraphs. In this note, we introduce the notion of (l,s) ‐discrepancy for k ‐graphs and prove that the equivalence of the (k,s) ‐discrepancy and the s ‐deviation for 1 ≤ s ≤ k. We remark that this refined notion of discrepancy seems to point to a lattice structure in relating various quasi‐random classes for hypergraphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Structure of random 312‐avoiding permutations

We evaluate the probabilities of various events under the uniform distribution on the set of 312‐avoiding permutations of . We derive exact formulas for the probability that the i^th element of a random permutation is a specific value less than i, and for joint probabilities of two such events. In addition, we obtain asymptotic approximations to these probabilities for large N when the elements are not close to the boundaries or to each other. We also evaluate the probability that the graph of a random 312‐avoiding permutation has k specified decreasing points, and we show that for large N the points below the diagonal look like trajectories of a random walk. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 599–631, 2016     

Graph diameter in long‐range percolation

We study the asymptotic growth of the diameter of a graph obtained by adding sparse “long” edges to a square box in ${\mathbb Z}^dWe study the asymptotic growth of the diameter of a graph obtained by adding sparse “long” edges to a square box in ${\mathbb Z}^d$. We focus on the cases when an edge between x and y is added with probability decaying with the Euclidean distance as |x ? y|^?s+o(1) when |x ? y| → ∞. For s ∈ (d, 2d) we show that the graph diameter for the graph reduced to a box of side L scales like (log L)^Δ+o(1) where Δ^?1 := log₂(2d/s). In particular, the diameter grows about as fast as the typical graph distance between two vertices at distance L. We also show that a ball of radius r in the intrinsic metric on the (infinite) graph will roughly coincide with a ball of radius exp{r^1/Δ+o(1)} in the Euclidean metric. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 210‐227, 2011     

The n‐ordered graphs: A new graph class

For a positive integer n, we introduce the new graph class of n‐ordered graphs, which generalize partial n‐trees. Several characterizations are given for the finite n‐ordered graphs, including one via a combinatorial game. We introduce new countably infinite graphs R⁽ⁿ⁾, which we name the infinite random n‐ordered graphs. The graphs R⁽ⁿ⁾ play a crucial role in the theory of n‐ordered graphs, and are inspired by recent research on the web graph and the infinite random graph. We characterize R⁽ⁿ⁾ as a limit of a random process, and via an adjacency property and a certain folding operation. We prove that the induced subgraphs of R⁽ⁿ⁾ are exactly the countable n‐ordered graphs. We show that all countable groups embed in the automorphism group of R⁽ⁿ⁾. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 204–218, 2009     

The Marčenko‐Pastur law for sparse random bipartite biregular graphs

We prove that the empirical spectral distribution of a (d_L, d_R)‐biregular, bipartite random graph, under certain conditions, converges to a symmetrization of the Mar?enko‐Pastur distribution of random matrix theory. This convergence is not only global (on fixed‐length intervals) but also local (on intervals of increasingly smaller length). Our method parallels the one used previously by Dumitriu and Pal (2012). © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 313–340, 2016     

The Law of the Iterated Logarithm for the Total Length of the Nearest Neighbor Graph

Let be the Poisson point process with intensity 1 in [–n,n] ^d . We prove the law of the iterated logarithm for the total length of the nearest neighbor graph on .     

Sparse pseudo‐random graphs are Hamiltonian

In this article we study Hamilton cycles in sparse pseudo‐random graphs. We prove that if the second largest absolute value λ of an eigenvalue of a d‐regular graph G on n vertices satisfies and n is large enough, then G is Hamiltonian. We also show how our main result can be used to prove that for every c >0 and large enough n a Cayley graph X (G,S), formed by choosing a set S of c log⁵ n random generators in a group G of order n, is almost surely Hamiltonian. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 17–33, 2003     

Meyniel's conjecture holds for random d‐regular graphs

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant C, the cop number of every connected graph G is at most . In a separate paper, we showed that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph. The result was obtained by showing that the conjecture holds for a general class of graphs with some specific expansion‐type properties. In this paper, this deterministic result is used to show that the conjecture holds asymptotically almost surely for random d‐regular graphs when d = d(n) ≥ 3.     

The 2‐dimensional rigidity of certain families of graphs

Laman's characterization of minimally rigid 2‐dimensional generic frameworks gives a matroid structure on the edge set of the underlying graph, as was first pointed out and exploited by L. Lovász and Y. Yemini. Global rigidity has only recently been characterized by a combination of two results due to T. Jordán and the first named author, and R. Connelly, respectively. We use these characterizations to investigate how graph theoretic properties such as transitivity, connectivity and regularity influence (2‐dimensional generic) rigidity and global rigidity and apply some of these results to reveal rigidity properties of random graphs. In particular, we characterize the globally rigid vertex transitive graphs, and show that a random d‐regular graph is asymptotically almost surely globally rigid for all d ≥ 4. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 154–166, 2007     

Inexpensive d‐dimensional matchings

Suppose that independent U(0, 1) weights are assigned to the ${d\choose 2}n^{2}$ edges of the complete d‐partite graph with n vertices in each of the d maximal independent sets. Then the expected weight of the minimum‐weight perfect d‐dimensional matching is at least $\frac{3}{16}n^{1-(2/d)}$. We describe a randomized algorithm that finds a perfect d‐dimensional matching whose expected weight is at most 5d³n^1?(2/d)+d¹⁵ for all d≥3 and n≥1. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 50–58, 2002     

Preordering saddle‐point systems for sparse LDLT factorization without pivoting

This paper focuses on efficiently solving large sparse symmetric indefinite systems of linear equations in saddle‐point form using a fill‐reducing ordering technique with a direct solver. Row and column permutations partition the saddle‐point matrix into a block structure constituting a priori pivots of order 1 and 2. The partitioned matrix is compressed by treating each nonzero block as a single entry, and a fill‐reducing ordering is applied to the corresponding compressed graph. It is shown that, provided the saddle‐point matrix satisfies certain criteria, a block LDL^T factorization can be computed using the resulting pivot sequence without modification. Numerical results for a range of problems from practical applications using a modern sparse direct solver are presented to illustrate the effectiveness of the approach.     

The geometry of t‐spreads in k‐walk‐regular graphs

A graph is walk‐regular if the number of closed walks of length ? rooted at a given vertex is a constant through all the vertices for all ?. For a walk‐regular graph G with d+1 different eigenvalues and spectrally maximum diameter D=d, we study the geometry of its d‐spreads, that is, the sets of vertices which are mutually at distance d. When these vertices are projected onto an eigenspace of its adjacency matrix, we show that they form a simplex (or tetrahedron in a three‐dimensional case) and we compute its parameters. Moreover, the results are generalized to the case of k‐walk‐regular graphs, a family which includes both walk‐regular and distance‐regular graphs, and their t‐spreads or vertices at distance t from each other. © 2009 Wiley Periodicals, Inc. J Graph Theory 64:312–322, 2010     

On the cut‐off phenomenon for the transitivity of randomly generated subgroups

Consider K ≥ 2 independent copies of the random walk on the symmetric group S_N starting from the identity and generated by the products of either independent uniform transpositions or independent uniform neighbor transpositions. At any time $n\in \mathbb{N}$, let G_n be the subgroup of S_N generated by the K positions of the chains. In the uniform transposition model, we prove that there is a cut‐off phenomenon at time N ln(N)/(2K) for the non‐existence of fixed point of G_n and for the transitivity of G_n, thus showing that these properties occur before the chains have reached equilibrium. In the uniform neighbor transposition model, a transition for the non‐existence of a fixed point of G_n appears at time of order $N^{1+\frac{2}{K}}$ (at least for K ≥ 3), but there is no cut‐off phenomenon. In the latter model, we recover a cut‐off phenomenon for the non‐existence of a fixed point at a time proportional to N by allowing the number K to be proportional to ln(N). The main tools of the proofs are spectral analysis and coupling techniques. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

A Characterization of b‐Perfect Graphs

A b‐coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b‐chromatic number of a graph G is the largest integer k such that G admits a b‐coloring with k colors. A graph is b‐perfect if the b‐chromatic number is equal to the chromatic number for every induced subgraph of G. We prove that a graph is b‐perfect if and only if it does not contain as an induced subgraph a member of a certain list of 22 graphs. This entails the existence of a polynomial‐time recognition algorithm and of a polynomial‐time algorithm for coloring exactly the vertices of every b‐perfect graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:95–122, 2012     

On a question of Sós about 3‐uniform friendship hypergraphs

The well‐known Friendship Theorem states that if G is a graph in which every pair of vertices has exactly one common neighbor, then G has a single vertex joined to all others (a “universal friend”). V. Sós defined an analogous friendship property for 3‐uniform hypergraphs, and gave a construction satisfying the friendship property that has a universal friend. We present new 3‐uniform hypergraphs on 8, 16, and 32 vertices that satisfy the friendship property without containing a universal friend. We also prove that if n ≤ 10 and n ≠ 8, then there are no friendship hypergraphs on n vertices without a universal friend. These results were obtained by computer search using integer programming. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 253–261, 2008