The thresholds for diameter 2 in random Cayley graphs

Given a group G, the model denotes the probability space of all Cayley graphs of G where each element of the generating set is chosen independently at random with probability p. In this article we show that for any and any family of groups G_k of order n_k for which , a graph with high probability has diameter at most 2 if and with high probability has diameter greater than 2 if . We also provide examples of families of graphs which show that both of these results are best possible. Of particular interest is that for some families of groups, the corresponding random Cayley graphs achieve Diameter 2 significantly faster than the Erd?s‐Renyi random graphs. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 218–235, 2014     

Random walks on random simple graphs

This paper looks at random regular simple graphs and considers nearest neighbor random walks on such graphs. This paper considers walks where the degree d of each vertex is around (log n)^a where a is a constant which is at least 2 and where n is the number of vertices. By extending techniques of Dou, this paper shows that for most such graphs, the position of the random walk becomes close to uniformly distributed after slightly more than log n/log d steps. This paper also gets similar results for the random graph G(n, p), where p = d/(n − 1). © 1996 John Wiley & Sons, Inc.     

On the girth of random Cayley graphs

We prove that random d‐regular Cayley graphs of the symmetric group asymptotically almost surely have girth at least (log_d‐1|G|)^1/2/2 and that random d‐regular Cayley graphs of simple algebraic groups over ??_q asymptotically almost surely have girth at least log _d‐1|G|/dim(G). For the symmetric p‐groups the girth is between loglog |G| and (log |G|)^α with α < 1. Several conjectures and open questions are presented. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Equitable partitions of Latin‐square graphs

We study equitable partitions of Latin‐square graphs and give a complete classification of those whose quotient matrix does not have an eigenvalue ?3.     

Random near-regular graphs and the node packing problem

Nemhauser and Trotter [12] proposed a certain easily-solved linear program as a relaxation of the node packing problem. They showed that any variables receiving integer values in an optimal solution to this linear program also take on the same values in an optimal solution to the (integer) node packing problem. Let π be the property of graphs defined as follows: a graph G has property π if and only if there is a unique optimal solution to the linear-relaxation problem, and this solution is completely fractional. If a graph G has property π then no information about the node packing problem on G is gained by solving the linear relaxation. We calculate the asymptotic probability that a certain type of ‘sparse’ random graph has property π, as the number of its nodes tends to infinity. Let m be a fixed positive integer, and consider the following random graph on the node set {1,2 …, n}). We join each node, j say, to exactly m other nodes chosen randomly with replacement, by edges oriented away from j; we denote by G_n(m) the undirected graph obtained by deleting all orientations and allowing all parallel edges to coalesce. We show that, as n → ∞,

$\text{P(G}{}_{\mathrm{n}}\text{(m)}\text{has property}\text{π)→}\text{0}\text{if}\text{m = 1,}\text{1}\text{if}\text{m ? 3,}$

and we conjecture that $\text{P(G}{}_{\mathrm{n}}\text{(2)}\text{has property}\text{π)→ (1–2e}{}^{\mathrm{?2}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$.     

Random perfect matchings in regular graphs

We prove that in all regular robust expanders $G$, every edge is asymptotically equally likely contained in a uniformly chosen perfect matching $M$. We also show that given any fixed matching or spanning regular graph $N$ in $G$, the random variable $|M\cap E(N)|$ is approximately Poisson distributed. This in particular confirms a conjecture and a question due to Spiro and Surya, and complements results due to Kahn and Kim who proved that in a regular graph every vertex is asymptotically equally likely contained in a uniformly chosen matching. Our proofs rely on the switching method and the fact that simple random walks mix rapidly in robust expanders.     

Isomorphic Cayley graphs on nonisomorphic groups

The issue of when two Cayley digraphs on different abelian groups of prime power order can be isomorphic is examined. This had previously been determined by Anne Joseph for squares of primes; her results are extended. © 1999 John Wiley & Sons, Inc. J Graph Theory 3: 345–362, 1999     

Random coloring evolution on graphs

In this short note we study how two colors, red and blue, painted on a given graph are evolved randomly according to a transition rule which aims to simulate how people influence each other. We shall also calculate the probability that the evolution will be trapped eventually using the martingale method.     

Random walks systems on complete graphs

We study two versions of random walks systems on complete graphs. In the first one, the random walks have geometrically distributed lifetimes so we define and identify a non-trivial critical parameter related to the proportion of visited vertices before the process dies out. In the second version, the lifetimes depend on the past of the process in a non-Markovian setup. For that version, we present results obtained from computational analysis, simulations and a mean field approximation. These three approaches match.     

The Search for Pseudo Orthogonal Latin Squares of Order Six

We report on the completecomputer search for a strongly regular graph with parameters(36,15,6,6) and chromatic number six. The resultis that no such graph exists.     

The number of transversals in a Latin square

A Latin Square of order n is an n × n array of n symbols, in which each symbol occurs exactly once in each row and column. A transversal is a set of n entries, one selected from each row and each column of a Latin Square of order n such that no two entries contain the same symbol. Define T(n) to be the maximum number of transversals over all Latin squares of order n. We show that for n ≥ 5, where b ≈ 1.719 and c ≈ 0.614. A corollary of this result is an upper bound on the number of placements of n non-attacking queens on an n × n toroidal chess board. Some divisibility properties of the number of transversals in Latin squares based on finite groups are established. We also provide data from a computer enumeration of transversals in all Latin Squares of order at most 9, all groups of order at most 23 and all possible turn-squares of order 14.     

On WL-rank of Deza Cayley graphs

The WL-rank of a graph Γ is defined to be the rank of the coherent configuration of Γ. We construct a new infinite family of strictly Deza Cayley graphs for which the WL-rank is equal to the number of vertices. The graphs from this family are divisible design and integral.     

A new class of facets for the Latin square polytope

Latin squares of order n have a 1-1 correspondence with the feasible solutions of the 3-index planar assignment problem (3PAP_n). In this paper, we present a new class of facets for the associated polytope, induced by odd-hole inequalities.     

Uncountable families of vertex-transitive graphs of finite degree

We prove that the set of vertex-transitive graphs of finite degree is uncountably large.     

Divisors of the number of Latin rectangles

A k×n Latin rectangle on the symbols {1,2,…,n} is called reduced if the first row is (1,2,…,n) and the first column is T(1,2,…,k). Let Rk,n be the number of reduced k×n Latin rectangles and m=⌊n/2⌋. We prove several results giving divisors of Rk,n. For example, (k−1)! divides Rk,n when k?m and m! divides Rk,n when m<k?n. We establish a recurrence which determines the congruence class of for a range of different t. We use this to show that Rk,n≡((−1)^k−1(k−1)!)ⁿ⁻¹. In particular, this means that if n is prime, then Rk,n≡1 for 1?k?n and if n is composite then if and only if k is larger than the greatest prime divisor of n.     

Algebraic Cayley graphs over finite fields

A new algebraic Cayley graph is constructed using finite fields. It provides a more flexible source of expander graphs. Its connectedness, the number of connected components, and diameter bound are studied via Weil's estimate for character sums. Furthermore, we study the algorithmic problem of computing the number of connected components and establish a link to the integer factorization problem.