On embeddings of some quotient algebras of free sums of Lie algebras

Let (B _i ) _i∈I be a set of Lie algebras; let X be a free Lie algebra; let * X be their free sum; let R be an ideal of F such that R ⋂ B _i = 1 (i ∈ I); let V be a variety of Lie algebras such that V(R) is an ideal of F. Under some restrictions, we construct an embedding of F/V(R) into the verbal wreath product of a free algebra of the variety V with F/R. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 10, No. 4, pp. 235–241, 2004.     

Rooted induced trees in triangle‐free graphs

For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t₃(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceilFor a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t₃(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceil$, improving a recent result by Fox, Loh and Sudakov. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 206–209, 2010     

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     

Sharp kernel clustering algorithms and their associated Grothendieck inequalities

In the kernel clustering problem we are given a (large) n × n symmetric positive semidefinite matrix A = (a_ij) with \begin{align*}\sum_{i=1}^n\sum_{j=1}^n a_{ij}=0\end{align*} and a (small) k × k symmetric positive semidefinite matrix B = (b_ij). The goal is to find a partition {S₁,…,S_k} of {1,…n} which maximizes \begin{align*}\sum_{i=1}^k\sum_{j=1}^k \left(\sum_{(p,q)\in S_i\times S_j}a_{pq}\right)b_{ij}\end{align*}. We design a polynomial time approximation algorithm that achieves an approximation ratio of \begin{align*}\frac{R(B)^2}{C(B)}\end{align*}, where R(B) and C(B) are geometric parameters that depend only on the matrix B, defined as follows: if b_ij = 〈v_i,v_j〉 is the Gram matrix representation of B for some \begin{align*}v_1,\ldots,v_k\in \mathbb{R}^k\end{align*} then R(B) is the minimum radius of a Euclidean ball containing the points {v₁,…,v_k}. The parameter C(B) is defined as the maximum over all measurable partitions {A₁,…,A_k} of \begin{align*}\mathbb{R}^{k-1}\end{align*} of the quantity \begin{align*}\sum_{i=1}^k\sum_{j=1}^k b_{ij}\langle z_i,z_j\rangle\end{align*}, where for i∈{1,…,k} the vector \begin{align*}z_i\in \mathbb{R}^{k-1}\end{align*} is the Gaussian moment of A_i, i.e., \begin{align*}z_i=\frac{1}{(2\pi)^{(k-1)/2}}\int_{A_i}xe^{-\|x\|_2^2/2}dx\end{align*}. We also show that for every ε > 0, achieving an approximation guarantee of \begin{align*}(1-\varepsilon)\frac{R(B)^2}{C(B)}\end{align*} is Unique Games hard. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Non-microstates free entropy dimension for groups

We show that for any discrete finitely-generated group G and any self-adjoint n-tuple X₁,...,X_n of generators of the group algebra Voiculescu’s non-microstates free entropy dimension δ^*(X₁,...,X_n) is exactly equal to β₁(G) − β₀(G) + 1 where β_i are the ℓ²-Betti numbers of G.Received: January 2004 Revision: October 2004 Accepted: January 2005     

Edge‐partitions of planar graphs and their game coloring numbers

Let G be a planar graph and let g(G) and Δ(G) be its girth and maximum degree, respectively. We show that G has an edge‐partition into a forest and a subgraph H so that (i) Δ(H) ≤ 4 if g(G) ≥ 5; (ii) Δ(H) ≤ 2 if g(G) ≥ 7; (iii) Δ(H)≤ 1 if g(G) ≥ 11; (iv) Δ(H) ≤ 7 if G does not contain 4‐cycles (though it may contain 3‐cycles). These results are applied to find the following upper bounds for the game coloring number col_g(G) of a planar graph G: (i) col_g(G) ≤ 8 if g(G) ≥ 5; (ii) col_g(G)≤ 6 if g(G) ≥ 7; (iii) col_g(G) ≤ 5 if g(G) ≥ 11; (iv) col_g(G) ≤ 11 if G does not contain 4‐cycles (though it may contain 3‐cycles). © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 307–317, 2002     

Restriction De La Cohomologie D’une Variété De Shimura à Ses Sous-variétés

Let G be a connected semisimple group over . Given a maximal compact subgroup K ⊂ G() such that X = G()/K is a Hermitian symmetric domain, and a convenient arithmetic subgroup Γ ⊂ G(), one constructs a (connected) Shimura variety S = S(Γ) = Γ\X. If H ⊂ G is a connected semisimple subgroup such that H() / K is maximal compact, then Y = H()/K is a Hermitian symmetric subdomain of X. For each g ∈ G() one can construct a connected Shimura variety S(H, g) = (H() ∩ g ⁻¹Γg)\Y and a natural holomorphic map j _g : S(H, g) → S induced by the map H() → G(), h → gh. Let us assume that G is anisotropic, which implies that S and S(H, g) are compact. Then, for each positive integer k, the map j _g induces a restriction map

Existence of finitely dominatedCW-complexes withG 1(X) = π1(X) and non-vanishing finiteness obstruction

We show for a finite abelian groupG and any element in the image of the Swan homomorphism sw: that it can be realized as the finiteness obstruction of a finitely dominated connectedCW-complexX with fundamental group π₁(X) =G such that π₁(X) is equal to the subgroupG ₁(X) defined by Gottlieb. This is motivated by the observation that anyH-spaceX satisfies π₁(X) =G ₁(X) and still the problem is open whether any finitely dominatedH-space is up to homotopy finite.     

Spherical orbit closures in simple projective spaces and their normalizations

Let G be a simply connected semisimple algebraic group over an algebraically closed field k of characteristic 0 and let V be a rational simple G-module. If G/H ⊂ P(V) is a spherical orbit and if X = [`(G/H)] X = \overline {G/H} is its closure, then we describe the orbits of X and those of its normalization [(X)\tilde] \tilde{X} . If, moreover, the wonderful completion of G/H is strict, then we give necessary and sufficient combinatorial conditions so that the normalization morphism [(X)\tilde] ? X \tilde{X} \to X is a homeomorphism. Such conditions are trivially fulfilled if G is simply laced or if H is a symmetric subgroup.     

Hamilton connectivity of line graphs and claw‐free graphs

Let G be a graph and let V₀ = {ν∈ V(G): d_G(ν) = 6}. We show in this paper that: (i) if G is a 6‐connected line graph and if |V₀| ≤ 29 or G[V₀] contains at most 5 vertex disjoint K₄'s, then G is Hamilton‐connected; (ii) every 8‐connected claw‐free graph is Hamilton‐connected. Several related results known before are generalized. © 2005 Wiley Periodicals, Inc. J Graph Theory     

The phase transition in random graphs: A simple proof

The classical result of Erd?s and Rényi asserts that the random graph G(n,p) experiences sharp phase transition around \begin{align*}p=\frac{1}{n}\end{align*} – for any ε > 0 and \begin{align*}p=\frac{1-\epsilon}{n}\end{align*}, all connected components of G(n,p) are typically of size O_ε(log n), while for \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, with high probability there exists a connected component of size linear in n. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, the random graph G(n,p) contains typically a path of linear length. We also discuss applications of our technique to other random graph models and to positional games. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

On randomized greedy matchings

We analyze a randomized greedy matching algorithm (RGA) aimed at producing a matching with a large number of edges in a given weighted graph. RGA was first introduced and studied by Dyer and Frieze in [3] for unweighted graphs. In the weighted version, at each step a new edge is chosen from the remaining graph with probability proportional to its weight, and is added to the matching. The two vertices of the chosen edge are removed, and the step is repeated until there are no edges in the remaining graph. We analyze the expected size μ(G) of the number of edges in the output matching produced by RGA, when RGA is repeatedly applied to the same graph G. Let r(G)=μ(G)/m(G), where m(G) is the maximum number of edges in a matching in G. For a class 𝒢 of graphs, let ρ(𝒢) be the infimum values r(G) over all graphs G in 𝒢 (i.e., ρ is the “worst” performance ratio of RGA restricted to the class 𝒢). Our main results are bound for μ, r, and ρ. For example, the following results improve or generalize similar results obtained in [3] for the unweighted version of RGA; \begin{eqnarray*}r(G)&\ge&{1\over 2-|V|/2|E|}\quad \mbox{(if $G$ has a perfect matching)}\\ {\sqrt{26}-4\over 2}&\le&\rho(\hbox{\sf SIMPLE PLANAR GRAPHS})\le.68436349\\ \rho(\hbox{SIMPLE $\Delta$-GRAPHS})&\ge&{1\over2}+{\sqrt{(\Delta-1)^2+1}-(\Delta-1)\over2}\end{eqnarray*} (where the class is the set of graphs of maximum degree at most Δ). © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10 : 353–383, 1997     

Eigenvalues and homology of flag complexes and vector representations of graphs

The flag complex of a graph G = (V, E) is the simplicial complex X(G) on the vertex set V whose simplices are subsets of V which span complete subgraphs of G. We study relations between the first eigenvalues of successive higher Laplacians of X(G). One consequence is the following:Theorem: Let λ₂(G) denote the second smallest eigenvalue of the Laplacian of G. If \,\frac{k}{k+1}|V|$$" align="middle" border="0"> then Applications include a lower bound on the homological connectivity of the independent sets complex I(G), in terms of a new graph domination parameter Γ(G) defined via certain vector representations of G. This in turns implies Hall type theorems for systems of disjoint representatives in hypergraphs.Received: January 2004 Revised: August 2004 Accepted: August 2004     

A vanishing theorem for differential operators in positive characteristic

Let X be a smooth variety over an algebraically closed field k of characteristic p, and let F: X → X be the Frobenius morphism. We prove that if X is an incidence variety (a partial flag variety in type A _n ) or a smooth quadric (in this case p is supposed to be odd) then Hⁱ( X,End( \sfF_*O_X ) ) = 0 {H^i}\left( {X,\mathcal{E}nd\left( {{\sf{F}_*}{\mathcal{O}_X}} \right)} \right) = 0 for i > 0. Using this vanishing result and the derived localization theorem for crystalline differential operators [3], we show that the Frobenius direct image \sfF_*O_X {\sf{F}_*}{\mathcal{O}_X} is a tilting bundle on these varieties provided that p > h, the Coxeter number of the corresponding group.     

Cohomology of solvable lie algebras and solvmanifolds

The cohomology H _{\mathfrakg\mathfrak{g} ) of the tangent Lie algebra \mathfrakg\mathfrak{g} of the group G with coefficients in the one-dimensional representation \mathfrakg\mathfrak{g} \mathbbK\mathbb{K} defined by [(W)\tilde] \mathfrakg \tilde \Omega _\mathfrak{g} of H ¹(G/ \mathfrakg\mathfrak{g} .}     

Pan-H-Linked Graphs

Let H be a multigraph, possibly containing loops. An H-subdivision is any simple graph obtained by replacing the edges of H with paths of arbitrary length. Let H be an arbitrary multigraph of order k, size m, n ₀(H) isolated vertices and n ₁(H) vertices of degree one. In Gould and Whalen (Graphs Comb. 23:165–182, 2007) it was shown that if G is a simple graph of order n containing an H-subdivision H{\mathcal{H}} and d(G) 3 \fracn+m-k+n₁(H)+2n₀(H)2{\delta(G) \ge \frac{n+m-k+n_1(H)+2n_0(H)}{2}}, then G contains a spanning H-subdivision with the same ground set as H{\mathcal{H}} . As a corollary to this result, the authors were able to obtain Dirac’s famed theorem on hamiltonian graphs; namely that if G is a graph of order n ≥ 3 with d(G) 3 \fracn2{\delta(G)\ge\frac{n}{2}} , then G is hamiltonian. Bondy (J. Comb. Theory Ser. B 11:80–84, 1971) extended Dirac’s theorem by showing that if G satisfied the condition d(G) 3 \fracn2{\delta(G) \ge \frac{n}{2}} then G was either pancyclic or a complete bipartite graph. In this paper, we extend the result from Gould and Whalen (Graphs Comb. 23:165–182, 2007) in a similar manner. An H-subdivision H{\mathcal{H}} in G is 1-extendible if there exists an H-subdivision H^*{\mathcal{H}^{*}} with the same ground set as H{\mathcal{H}} and |H^*| = |H| + 1{|\mathcal{H}^{*}| = |\mathcal{H}| + 1} . If every H-subdivision in G is 1-extendible, then G is pan-H-linked. We demonstrate that if H is sufficiently dense and G is a graph of large enough order n such that d(G) 3 \fracn+m-k+n₁(H)+2n₀(H)2{\delta(G) \ge \frac{n+m-k+n_1(H)+2n_0(H)}{2}} , then G is pan-H-linked. This result is sharp.     

On super edge-magic decomposable graphs

Let G be any graph and let {H _i } _i??I be a family of graphs such that $E\left( {H_i } \right) \cap E\left( {H_j } \right) = \not 0$ when i ?? j, ?? _i??I E(H _i ) = E(G) and $E\left( {H_i } \right) \ne \not 0$ for all i ?? I. In this paper we introduce the concept of {H _i } _i??I -super edge-magic decomposable graphs and {H _i } _i??I -super edge-magic labelings. We say that G is {H _i } _i??I -super edge-magic decomposable if there is a bijection ??: V(G) ?? {1,2,..., |V(G)|} such that for each i ?? I the subgraph H _i meets the following two requirements: ??(V(H _i )) = {1,2,..., |V(H _i )|} and {??(a) +??(b): ab ?? E(H _i )} is a set of consecutive integers. Such function ?? is called an {H _i } _i??I -super edge-magic labeling of G. We characterize the set of cycles C _n which are {H ₁, H ₂}-super edge-magic decomposable when both, H ₁ and H ₂ are isomorphic to (n/2)K ₂. New lines of research are also suggested.     

Resolvability in circulant graphs

A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, v ∈ V (G) there is a vertex w ∈ W such that d(u, w) ≠ d(v, w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim(G). For a vertex u of G and a subset S of V (G), the distance between u and S is the number min s∈S d(u, s). A k-partition Π = {S 1 , S 2 , . . . , S k } of V (G) is called a resolving partition if for every two distinct vertices u, v ∈ V (G) there is a set S i in Π such that d(u, Si )≠ d(v, Si ). The minimum k for which there is a resolving k-partition of V (G) is called the partition dimension of G, denoted by pd(G). The circulant graph is a graph with vertex set Zn , an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i-j (mod n) ∈ C , where CZn has the property that C =-C and 0 ■ C. The circulant graph is denoted by Xn, Δ where Δ = |C|. In this paper, we study the metric dimension of a family of circulant graphs Xn, 3 with connection set C = {1, n/2 , n-1} and prove that dim(Xn, 3 ) is independent of choice of n by showing that dim(Xn, 3 ) ={3 for all n ≡ 0 (mod 4), 4 for all n ≡ 2 (mod 4). We also study the partition dimension of a family of circulant graphs Xn,4 with connection set C = {±1, ±2} and prove that pd(Xn, 4 ) is independent of choice of n and show that pd(X5,4 ) = 5 and pd(Xn,4 ) ={3 for all odd n ≥ 9, 4 for all even n ≥ 6 and n = 7.     

Long paths through four vertices in a 2‐connected graph

Let G be a 2‐connected graph, let u and v be distinct vertices in V(G), and let X be a set of at most four vertices lying on a common (u, v)‐path in G. If deg(x) ≥ d for all x ∈ V(G) \ {u, v}, then there is a (u, v)‐path P in G with X ⊂ V(P) and |E(P)| ≥ d. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 55–65, 2000     

On thin-complete ideals of subsets of groups

Let F ì P_G \mathcal{F} \subset {\mathcal{P}_G} be a left-invariant lower family of subsets of a group G. A subset A ⊂ G is called F \mathcal{F} -thin if xA ?yA ? F xA \cap yA \in \mathcal{F} for any distinct elements x, y ∈ G. The family of all F \mathcal{F} -thin subsets of G is denoted by t( F ) \tau \left( \mathcal{F} \right) . If t( F ) = F \tau \left( \mathcal{F} \right) = \mathcal{F} , then F \mathcal{F} is called thin-complete. The thin-completion t^*( F ) {\tau^*}\left( \mathcal{F} \right) of F \mathcal{F} is the smallest thin-complete subfamily of P_G {\mathcal{P}_G} that contains F \mathcal{F} . Answering questions of Lutsenko and Protasov, we prove that a set A ⊂ G belongs to τ*(G) if and only if, for any sequence (g _n ) _n∈ω of nonzero elements of G, there is n ∈ ω such that