A strong uniform time for random transpositions

A random permutation ofN items generated by a sequence ofK random transpositions is considered. The method of strong uniform times is used to give an upper bound on the variation distance between the distributions of the random permutation generated and a uniformly distributed permutation. The strong uniform time is also used to find the asymptotic distribution of the number of fixed points of the generated permutation. This is used to give a lower bound on the same variation distance. Together these bounds give a striking demonstration of the threshold phenomenon in the convergence of rapidly mixing Markov chains to stationarity.     

A functional limit theorem for random graphs with applications to subgraph count statistics

We consider a random graph that evolves in time by adding new edges at random times (different edges being added at independent and identically distributed times). A functional limit theorem is proved for a class of statistics of the random graph, considered as stochastic processes. the proof is based on a martingale convergence theorem. the evolving random graph allows us to study both the random graph model K_{n, p}, by fixing attention to a fixed time, and the model K_{n, N}, by studying it at the random time it contains exactly N edges. in particular, we obtain the asymptotic distribution as n → ∞ of the number of subgraphs isomorphic to a given graph G, both for K_{n, p} (p fixed) and K_{n, N} (N/(ⁿ₂)→ p). the results are strikingly different; both models yield asymptotically normal distributions, but the variances grow as different powers of n (the variance grows slower for K_n, N; the powers of n usually differ by 1, but sometimes by 3). We also study the number of induced subgraphs of a given type and obtain similar, but more complicated, results. in some exceptional cases, the limit distribution is not normal.     

Extremal subgraphs of random graphs

We prove that there is a constant c > 0, such that whenever p ≥ n^‐c, with probability tending to 1 when n goes to infinity, every maximum triangle‐free subgraph of the random graph G_n,p is bipartite. This answers a question of Babai, Simonovits and Spencer (Babai et al., J Graph Theory 14 (1990) 599–622). The proof is based on a tool of independent interest: we show, for instance, that the maximum cut of almost all graphs with M edges, where M ? n and M ≤ /2, is “nearly unique”. More precisely, given a maximum cut C of G_n,M, we can obtain all maximum cuts by moving at most \begin{align*}\mathcal{O}(\sqrt{n^3/M})\end{align*} vertices between the parts of C. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Triangle‐free subgraphs in the triangle‐free process

Consider the triangle‐free process, which is defined as follows. Start with G(0), an empty graph on n vertices. Given G(i ‐ 1), let G(i) = G(i ‐ 1) ∪{g(i)}, where g(i) is an edge that is chosen uniformly at random from the set of edges that are not in G(i ? 1) and can be added to G(i ‐ 1) without creating a triangle. The process ends once a maximal triangle‐free graph has been created. Let H be a fixed triangle‐free graph and let X_H(i) count the number of copies of H in G(i). We give an asymptotically sharp estimate for ??(X_H(i)), for every \begin{align*}1 \ll i \le 2^{-5} n^{3/2} \sqrt{\ln n}\end{align*}, at the limit as n →∞. Moreover, we provide conditions that guarantee that a.a.s. X_H(i) = 0, and that X_H(i) is concentrated around its mean.© 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Stability for large forbidden subgraphs

In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:

• (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:
  • (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/3+c^1/(3r+3))n² edges.
  Letting µ(G) be the spectral radius of G, we prove also a spectral stability theorem: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with µ(G)>(1?1/r?ε)n satisfies one of the conditions:
  • (a) G contains a $K_{r+1}(\lfloor c\,\mbox{ln}\,n\rfloor,\ldots,\lfloor c\,\mbox{ln}\,n\rfloor,\lceil n^{1-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/4+c^1/(8r+8))n² edges.
  © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 362–368, 2009     

On Π-Supplemented Subgroups of a Finite Group

A subgroup H of a finite group G is said to satisfy Π-property in G if for every chief factor L/K of G, |G/K: N_G/K(HK/K ∩ L/K)| is a π(HK/K ∩ L/K)-number. A subgroup H of G is called Π-supplemented in G if there exists a subgroup T of G such that G = HT and H ∩ T ≤ I ≤ H, where I satisfies Π-property in G. In this article, we investigate the structure of a finite group G under the assumption that some primary subgroups of G are Π-supplemented in G. The main result we proved improves a large number of earlier results.     

Quasi‐randomness of graph balanced cut properties

Quasi‐random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, Shapira and Yuster proved the following result on quasi‐randomness of graphs. Let k ≥ 2 be a fixed integer, α₁,…,α_k be positive reals satisfying \begin{align*}\sum_{i} \alpha_i = 1\end{align*} and (α₁,…,α_k)≠(1/k,…,1/k), and G be a graph on n vertices. If for every partition of the vertices of G into sets V ₁,…,V _k of size α₁n,…,α_kn, the number of complete graphs on k vertices which have exactly one vertex in each of these sets is similar to what we would expect in a random graph, then the graph is quasi‐random. However, the method of quasi‐random hypergraphs they used did not provide enough information to resolve the case (1/k,…,1/k) for graphs. In their work, Shapira and Yuster asked whether this case also forces the graph to be quasi‐random. Janson also posed the same question in his study of quasi‐randomness under the framework of graph limits. In this paper, we positively answer their question. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Turánnical hypergraphs

This paper is motivated by the question of how global and dense restriction sets in results from extremal combinatorics can be replaced by less global and sparser ones. The result we consider here as an example is Turán's theorem, which deals with graphs G = ([n],E) such that no member of the restriction set \begin{align*}\mathcal {R}\end{align*} = \begin{align*}\left( {\begin{array}{*{20}c} {[n]} \\ r \\ \end{array} } \right)\end{align*} induces a copy of K_r. Firstly, we examine what happens when this restriction set is replaced by \begin{align*}\mathcal {R}\end{align*} = {X∈ \begin{align*}\left( {\begin{array}{*{20}c} {[n]} \\ r \\ \end{array} } \right)\end{align*}: X ∩ [m]≠??}. That is, we determine the maximal number of edges in an n ‐vertex such that no K_r hits a given vertex set. Secondly, we consider sparse random restriction sets. An r ‐uniform hypergraph \begin{align*}\mathcal R\end{align*} on vertex set [n] is called Turánnical (respectively ε ‐Turánnical), if for any graph G on [n] with more edges than the Turán number t_r(n) (respectively (1 + ε)t_r(n) ), no hyperedge of \begin{align*}\mathcal {R}\end{align*} induces a copy of K_r in G. We determine the thresholds for random r ‐uniform hypergraphs to be Turánnical and to be ε ‐Turánnical. Thirdly, we transfer this result to sparse random graphs, using techniques recently developed by Schacht [Extremal results for random discrete structures] to prove the Kohayakawa‐?uczak‐Rödl Conjecture on Turán's theorem in random graphs.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Hedetniemi’s Conjecture and Dense Boolean Lattices

The category D{\mathcal{D}} of finite directed graphs is Cartesian closed, hence it has a product and exponential objects. For a fixed K, let K^DK^{\mathcal{D}} be the class of all directed graphs of the form K ^G , preordered by the existence of homomorphisms, and factored by homomorphic equivalence. It has long been known that K^DK^{\mathcal{D}} is always a Boolean lattice. In this paper we prove that for any complete graph K _n with n ≥ 3, K_n^DK_n^{\mathcal{D}} is dense, hence up to isomorphism it is the unique countable dense Boolean lattice. In graph theory, the structure of K_n^DK_n^{\mathcal{D}} is connected to the conjecture of Hedetniemi on the chromatic number of a categorical product of graphs.     

Cube factorizations of complete graphs

A cube factorization of the complete graph on n vertices, K_n, is a 3‐factorization of K_n in which the components of each factor are cubes. We show that there exists a cube factorization of K_n if and only if n ≡ 16 (mod 24), thus providing a new family of uniform 3‐factorizations as well as a partial solution to an open problem posed by Kotzig in 1979. © 2004 Wiley Periodicals, Inc.     

Large Kr‐free subgraphs in Ks‐free graphs and some other Ramsey‐type problems

In this paper we present three Ramsey‐type results, which we derive from a simple and yet powerful lemma, proved using probabilistic arguments. Let 3 ≤ r < s be fixed integers and let G be a graph on n vertices not containing a complete graph K_s on s vertices. More than 40 years ago Erd?s and Rogers posed the problem of estimating the maximum size of a subset of G without a copy of the complete graph K_r. Our first result provides a new lower bound for this problem, which improves previous results of various researchers. It also allows us to solve some special cases of a closely related question posed by Erd?s. For two graphs G and H, the Ramsey number R(G, H) is the minimum integer N such that any red‐blue coloring of the edges of the complete graph K_N, contains either a red copy of G or a blue copy of H. The book with n pages is the graph B_n consisting of n triangles sharing one edge. Here we study the book‐complete graph Ramsey numbers and show that R(B_n, K_n) ≤ O(n³/log^3/2n), improving the bound of Li and Rousseau. Finally, motivated by a question of Erd?s, Hajnal, Simonovits, Sós, and Szemerédi, we obtain for all 0 < δ < 2/3 an estimate on the number of edges in a K₄‐free graph of order n which has no independent set of size n^1‐δ. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

The diameter of sparse random graphs

We derive an expression of the form c ln n + o(ln n) for the diameter of a sparse random graph with a specified degree sequence. The result holds asymptotically almost surely, assuming that certain convergence and supercriticality conditions are met, and is applicable to the classical random graph G_n,p with np = Θ(1) + 1, as well as certain random power law graphs. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

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     

Poincaré inequality in mean value for Gaussian polytopes

Let K _N = [±G ₁, . . . , ±G _N ] be the absolute convex hull of N independent standard Gaussian random points in ${\mathbb R^n}$ with N ≥ n. We prove that, for any 1-Lipschitz function ${f:\mathbb R^n\rightarrow\mathbb R}$ , the polytope K _N satisfies the following Poincaré inequality in mean value: $$\mathbb {E}_{\omega} \int\limits_{K_N(\omega)} \left( f(x) - \frac{1}{\textup{vol}_n\left(K_N(\omega)\right)} \int\limits_{K_n(\omega)}f(y)dy \right)^2 dx \leq \frac{C}{n} \mathbb E_{\omega} \int\limits_{K_N(\omega)}|x|^2dx$$ where C?>?0 is an absolute constant. This Poincaré inequality is the one suggested by a conjecture of Kannan, Lovász and Simonovits for general convex bodies. Moreover, we prove in mean value that the volume of the polytope K _N is concentrated in a subexponential way within a thin Euclidean shell with the optimal dependence of the dimension n. An important tool of the proofs is a representation of the law of (G ₁, . . . , G _n ) conditioned by the event that “the convex hull of G ₁, . . . , G _n is a (n ? 1)-face of K _N ”. As an application, we also get an estimate of the number of (n ? 1)-faces of the polytope K _N , valid for every N ≥ n.     

On two Hamilton cycle problems in random graphs

We study two problems related to the existence of Hamilton cycles in random graphs. The first question relates to the number of edge disjoint Hamilton cycles that the random graph G _n,p contains. δ(G)/2 is an upper bound and we show that if p ≤ (1 + o(1)) ln n/n then this upper bound is tight whp. The second question relates to how many edges can be adversarially removed from G _n,p without destroying Hamiltonicity. We show that if p ≥ K ln n/n then there exists a constant α > 0 such that whp G − H is Hamiltonian for all choices of H as an n-vertex graph with maximum degree Δ(H) ≤ αK ln n. Research supported in part by NSF grant CCR-0200945. Research supported in part by USA-Israel BSF Grant 2002-133 and by grant 526/05 from the Israel Science Foundation.     

On the almost sure central limit theorem for randomly indexed sums

Let {S_n, n ≥ 1} be partial sums of independent identically distributed random variables. The almost sure version of CLT is generalized on the case of randomly indexed sums {S_Nn, n ≥ 1}, where {N_n, n ≥ 1} is a sequence of positive integer‐valued random variables independent of {S_n, n ≥ 1}. The affects of nonrandom centering and norming are considered too (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Normalizers and self-normalizing subgroups II

Let \mathbbK\mathbb{K} be a field, G a reductive algebraic \mathbbK\mathbb{K}-group, and G ₁ ≤ G a reductive subgroup. For G ₁ ≤ G, the corresponding groups of \mathbbK\mathbb{K}-points, we study the normalizer N = N _G (G ₁). In particular, for a standard embedding of the odd orthogonal group G ₁ = SO(m, \mathbbK\mathbb{K}) in G = SL(m, \mathbbK\mathbb{K}) we have N ≅ G ₁ ⋊ μ _m ( \mathbbK\mathbb{K}), the semidirect product of G ₁ by the group of m-th roots of unity in \mathbbK\mathbb{K}. The normalizers of the even orthogonal and symplectic subgroup of SL(2n, \mathbbK\mathbb{K}) were computed in [Širola B., Normalizers and self-normalizing subgroups, Glas. Mat. Ser. III (in press)], leaving the proof in the odd orthogonal case to be completed here. Also, for G = GL(m, \mathbbK\mathbb{K}) and G ₁ = O(m, \mathbbK\mathbb{K}) we have N ≅ G ₁ ⋊ \mathbbK\mathbb{K} ^×. In both of these cases, N is a self-normalizing subgroup of G.     

The phase transition in the cluster‐scaled model of a random graph

For 0 < p < 1 and q > 0 let G_q(n,p) denote the random graph with vertex set [n]={1,…,n} such that, for each graph G on [n] with e(G) edges and c(G) components, the probability that G_q(n,p)=G is proportional to . The first systematic study of G_q(n,p) was undertaken by 6 , who analyzed the phase transition phenomenon corresponding to the emergence of the giant component. In this paper we describe the structure of G_q(n,p) very close the critical threshold. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

On <Emphasis Type="Italic">p</Emphasis>-nilpotency and minimal subgroups of finite groups

We call a subgroup H of a finite group G c-supplemented in G if there exists a subgroup K of G such that G = HK and H ∩ K ⩽ core(H). In this paper it is proved that a finite group G is p-nilpotent if G is S ₄-free and every minimal subgroup of P ∩ G ^N is c-supplemented in N _G (P), and when p = 2 P is quaternion-free, where p is the smallest prime number dividing the order of G, P a Sylow p-subgroup of G. As some applications of this result, some known results are generalized.     

Random Lazy Random Walks on Arbitrary Finite Groups

This paper considers lazy random walks supported on a random subset of k elements of a finite group G with order n. If k=a log₂ n where a>1 is constant, then most such walks take no more than a multiple of log₂ n steps to get close to uniformly distributed on G. If k=log₂ n+f(n) where f(n) and f(n)/log₂ n0 as n, then most such walks take no more than a multiple of (log₂ n) ln(log₂ n) steps to get close to uniformly distributed. To get these results, this paper extends techniques of Erdös and Rényi and of Pak.