A substitution theorem for graceful trees and its applications

A graceful labeling of a graph G=(V,E) assigns |V| distinct integers from the set {0,…,|E|} to the vertices of G so that the absolute values of their differences on the |E| edges of G constitute the set {1,…,|E|}. A graph is graceful if it admits a graceful labeling. The forty-year old Graceful Tree Conjecture, due to Ringel and Kotzig, states that every tree is graceful.We prove a Substitution Theorem for graceful trees, which enables the construction of a larger graceful tree through combining smaller and not necessarily identical graceful trees. We present applications of the Substitution Theorem, which generalize earlier constructions combining smaller trees.     

On complete intersection toric ideals of graphs

We study the graphs G for which their toric ideals I _G are complete intersections. In particular, we prove that for a connected graph G such that I _G is a complete intersection all of its blocks are bipartite except for at most two. We prove that toric ideals of graphs which are complete intersections are circuit ideals. In this case, the generators of the toric ideal correspond to even cycles of G except of at most one generator, which corresponds to two edge disjoint odd cycles joint at a vertex or with a path. We prove that the blocks of these graphs satisfy the odd cycle condition. Finally, we characterize all complete intersection toric ideals of graphs which are normal.     

Characterization of G 2(q), where 2 < q ≡ −1(mod 3), by order components

We prove that the simple group G ₂(q), where 2 < q ≡ ?1(mod 3), is recognizable by the set of its order components. In other words, we prove that if G is a finite group with OC(G) = OC(G ₂(q)), then G ≌ G ₂(q).     

On finite groups with a certain number of centralizers

LetG be a finite group and #Cent(G) denote the number of centralizers of its elements.G is calledn-centralizer if #Cent(G)=n, and primitiven-centralizer if #Cent(G)=#Cent(G/Z(G))=n. In this paper we investigate the structure of finite groups with at most 21 element centralizers. We prove that such a group is solvable and ifG is a finite group such thatG/Z(G)?A₅, then #Cent(G)=22 or 32. Moroever, we prove that A₅ is the only finite simple group with 22 centralizers. Therefore we obtain a characterization of A₅ in terms of the number of centralizers     

On minimally circular-imperfect graphs

A circular-perfect graph is a graph of which each induced subgraph has the same circular chromatic number as its circular clique number. In this paper, (1) we prove a lower bound on the order of minimally circular-imperfect graphs, and characterize those that attain the bound; (2) we prove that if G is a claw-free minimally circular-imperfect graph such that ω_c(G-x)>ω(G-x) for some x∈V(G), then G=K_(2k+1)/2+x for an integer k; and (3) we also characterize all minimally circular-imperfect line graphs.     

A criterion for the strongly semistable principal bundles over a curve in positive characteristic

Let X be an irreducible smooth projective curve over an algebraically closed field k of positive characteristic and G a simple linear algebraic group over k. Fix a proper parabolic subgroup P of G and a nontrivial anti-dominant character λ of P. Given a principal G-bundle E_G over X, let E_G(λ) be the line bundle over E_G/P associated to the principal P-bundle E_G→E_G/P for the character λ. We prove that E_G is strongly semistable if and only if the line bundle E_G(λ) is numerically effective. For any connected reductive algebraic group H over k, a similar criterion is proved for strongly semistable H-bundles.     

The basis monomial ring of a matroid

We define the basis monomial ring M_G of a matroid G and prove that it is Cohen-Macaulay for finite G. We then compute the Krull dimension of M_G, which is the rank over Q of the basis-point incidence matrix of G, and prove that dim B_G ≥ dim M_G under a certain hypothesis on coordinatizability of G, where B_G is the bracket ring of G.     

Operator norm localization property of relative hyperbolic group and graph of groups

In this article we study the spaces which have operator norm localization property. We prove that a finitely generated group Γ which is strongly hyperbolic with respect to a collection of finitely generated subgroups {H₁,…,Hn} has operator norm localization property if and only if each Hi, i=1,2,…,n, has operator norm localization property. Furthermore we prove the following result. Let π be the fundamental group of a connected finite graph of groups with finitely generated vertex groups GP. If GP has operator norm localization property for all vertices P then π has operator norm localization property.     

On embeddings of snarks in the torus

A condition on cubic graphs G₁ and G₂ is presented, which implies that a dot product G₁·G₂ exists, which has an embedding in the torus. Using this condition we prove that for every positive integer n a dot product of n copies of the Petersen graph exists, which can be embedded in the torus. This disproves a conjecture of Watkins and Tinsley and answers a question by Mohar.     

Φ-Harmonic functions on discrete groups and the first ℓΦ-cohomology

We study the first cohomology groups of a countable discrete group G with coefficients in a G-module ?^Φ(G), where Φ is an N-function of class Δ₂(0) ∩ ?₂(0). Developing the ideas of Puls and Martin-Valette for a finitely generated group G, we introduce the discrete Φ-Laplacian and prove a theorem on the decomposition of the space of Φ-Dirichlet finite functions into the direct sum of the spaces of Φ-harmonic functions and ?^Φ(G) (with an appropriate factorization). We prove also that if a finitely generated group G has a finitely generated infinite amenable subgroup with infinite centralizer then \(\bar H^1\) (G, ?^Φ(G)) = 0. In conclusion, we show the triviality of the first cohomology group for the wreath product of two groups one of which is nonamenable.     

Hamiltonicity of 4-connected graphs

Let σk（G） denote the minimum degree sum of k independent vertices in G and α（G） denote the number of the vertices of a maximum independent set of G. In this paper we prove that if G is a 4-connected graph of order n and σ5（G） 〉 n ＋ 3σ（G） ＋ 11, then G is Hamiltonian.     

List coloring of graphs having cycles of length divisible by a given number

Let G be a graph and χ_l(G) denote the list chromatic number of G. In this paper we prove that for every graph G for which the length of each cycle is divisible by l (l≥3), χ_l(G)≤3.     

Finite groups whose maximal subgroups have the hall property

We study the structure of finite groups whosemaximal subgroups have the Hall property. We prove that such a group G has at most one non-Abelian composition factor, the solvable radical S(G) admits a Sylow series, the action of G on sections of this series is irreducible, the series is invariant with respect to this action, and the quotient group G/S(G) is either trivial or isomorphic to PSL₂(7), PSL₂(11), or PSL₅(2). As a corollary, we show that every maximal subgroup of G is complemented.     

Fundamental solution for the Q-Laplacian and sharp Moser-Trudinger inequality in Carnot groups

For a general Carnot group G with homogeneous dimension Q we prove the existence of a fundamental solution of the Q-Laplacian u_Q and a constant a_Q>0 such that exp(−a_Qu_Q) is a homogeneous norm on G. This implies a representation formula for smooth functions on G which is used to prove the sharp Carnot group version of the celebrated Moser-Trudinger inequality.     

On 3-regular 4-ordered graphs

A simple graph G is k-ordered (respectively, k-ordered hamiltonian), if for any sequence of k distinct vertices v₁,…,v_kof G there exists a cycle (respectively, hamiltonian cycle) in G containing these k vertices in the specified order. In 1997 Ng and Schultz introduced these concepts of cycle orderability and posed the question of the existence of 3-regular 4-ordered (hamiltonian) graphs other than K₄ and K_3,3. Ng and Schultz observed that a 3-regular 4-ordered graph on more than 4 vertices is triangle free. We prove that a 3-regular 4-ordered graph G on more than 6 vertices is square free,and we show that the smallest graph that is triangle and square free, namely the Petersen graph, is 4-ordered. Furthermore, we prove that the smallest graph after K₄ and K_3,3 that is 3-regular 4-ordered hamiltonianis the Heawood graph. Finally, we construct an infinite family of 3-regular 4-ordered graphs.     

On finite groups with given maximal subgroups

We prove that a finite group whose every maximal subgroup is simple or nilpotent is a Schmidt group. A group whose every maximal subgroup is simple or supersoluble can be nonsoluble, and in this case we prove that its chief series has the form 1 ? K ? G, K }~ PSL ₂(p) for a suitable prime p, |G: K| ≤ 2.     

Semisimple strata for p-adic classical groups

Let F₀ be a non-archimedean local field, of residual characteristic different from 2, and let G be a unitary, symplectic or orthogonal group defined over F₀. In this paper, we prove some fundamental results towards the classification of the representations of G via types [8]. In particular, we show that any positive level supercuspidal representation of G contains a semisimple skew stratum, that is, a special character of a certain compact open subgroup of G. The intertwining of such a stratum has been calculated in [19].     

Thompson’s conjecture for Lie type groups E 7(q)

In this article, we prove a conjecture of Thompson for an infinite class of simple groups of Lie type E ₇(q). More precisely, we show that every finite group G with the properties Z(G) = 1 and cs(G) = cs(E ₇(q)) is necessarily isomorphic to E ₇(q), where cs(G) and Z(G) are the set of lengths of conjugacy classes of G and the center of G respectively.     

Hamiltonian cycles and dominating cycles passing through a linear forest

Let G be an (m+2)-graph on n vertices, and F be a linear forest in G with |E(F)|=m and ω₁(F)=s, where ω₁(F) is the number of components of order one in F. We denote by σ₃(G) the minimum value of the degree sum of three vertices which are pairwise non-adjacent. In this paper, we give several σ₃ conditions for a dominating cycle or a hamiltonian cycle passing through a linear forest. We first prove that if σ₃(G)≥n+2m+2+max{s−3,0}, then every longest cycle passing through F is dominating. Using this result, we prove that if σ₃(G)≥n+κ(G)+2m−1 then G contains a hamiltonian cycle passing through F. As a corollary, we obtain a result that if G is a 3-connected graph and σ₃(G)≥n+κ(G)+2, then G is hamiltonian-connected.     

Discrete Morse theory for totally non-negative flag varieties

In a seminal 1994 paper Lusztig (1994) [26], Lusztig extended the theory of total positivity by introducing the totally non-negative part (G/P)_?0 of an arbitrary (generalized, partial) flag variety G/P. He referred to this space as a “remarkable polyhedral subspace”, and conjectured a decomposition into cells, which was subsequently proven by the first author Rietsch (1998) [33]. In Williams (2007) [40] the second author made the concrete conjecture that this cell decomposed space is the next best thing to a polyhedron, by conjecturing it to be a regular CW complex that is homeomorphic to a closed ball. In this article we use discrete Morse theory to prove this conjecture up to homotopy-equivalence. Explicitly, we prove that the boundaries of the cells are homotopic to spheres, and the closures of cells are contractible. The latter part generalizes a result of Lusztig's (1998) [28], that (G/P)_?0 - the closure of the top-dimensional cell - is contractible. Concerning our result on the boundaries of cells, even the special case that the boundary of the top-dimensional cell (G/P)_>0 is homotopic to a sphere, is new for all G/P other than projective space.