Probability of diameter two for Steinhaus graphs (Q1208476): Difference between revisions

A Steinhaus graph with adjacency matrix \((a_{ij})_{i,j=1, \dots, n}\) is defined inductively by taking \(a_{ij}\) as independent Bernoulli \((p_ j)\) for \(j=2, \dots, n\) and \(a_{ij} = a_{i-1,j-1} + a_{i- 1,j} \pmod 2\) for \(j=i+1,\dots,n\) and \(i=2,\dots,n-1\). It is shown under some conditions on the \(p_ j\) that the diameter of the graph is 2 with a probability tending to 1 as \(n\) tends to infinity.