Infinitely Many Trees Have Non-Sperner Subtree Poset

Let C(T) denote the poset of subtrees of a tree T with respect to the inclusion ordering. Jacobson, Kézdy and Seif gave a single example of a tree T for which C(T) is not Sperner, answering a question posed by Penrice. The authors then ask whether there exist an infinite family of trees T such that C(T) is not Sperner. This paper provides such a family.     

Even cycles in graphs

Let G be a 3‐connected simple graph of minimum degree 4 on at least six vertices. The author proves the existence of an even cycle C in G such that G‐V(C) is connected and G‐E(C) is 2‐connected. The result is related to previous results of Jackson, and Thomassen and Toft. Thomassen and Toft proved that G contains an induced cycle C such that both G‐V(C) and G‐E(C) is 2‐connected. G does not in general contain an even cycle such that G‐V(C) is 2‐connected. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 163–223, 2004     

Some results on spanning trees

Some structures of spanning trees with many or less leaves in a connected graph are determined.We show（1） a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and（2） a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ（G） =Δ（T） and the number of leaves of T is not greater than n D（G）＋1,where D（G） is the diameter of G.     

Prime ideals in the C*-algebra of a nilpotent group

We say that a locally compact groupG hasT ₁ primitive ideal space if the groupC ^*-algebra,C ^*(G), has the property that every primitive ideal (i.e. kernel of an irreducible representation) is closed in the hull-kernel topology on the space of primitive ideals ofC ^*(G), denoted by PrimG. This means of course that every primitive ideal inC ^*(G) is maximal. Long agoDixmier proved that every connected nilpotent Lie group hasT ₁ primitive ideal space. More recentlyPoguntke showed that discrete nilpotent groups haveT ₁ primitive ideal space and a few month agoCarey andMoran proved the same property for second countable locally compact groups having a compactly generated open normal subgroup. In this note we combine the methods used in [3] with some ideas in [9] and show that for nilpotent locally compact groupsG, having a compactly generated open normal subgroup, closed prime ideals inC ^*(G) are always maximal which implies of course that PrimG isT ₁.     

On the diameter of i‐center in a graph without long induced paths

A graph G is said to be P_t‐free if it does not contain an induced path on t vertices. The i‐center C_i(G) of a connected graph G is the set of vertices whose distance from any vertex in G is at most i. Denote by I(t) the set of natural numbers i, ⌊t/2⌋ ≤ i ≤ t − 2, with the property that, in every connected P_t‐free graph G, the i‐center C_i(G) of G induces a connected subgraph of G. In this article, the sharp upper bound on the diameter of G[C_i(G)] is established for every i ∈ I(t). The sharp lower bound on I(t) is obtained consequently. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 235–241, 1999     

The number of spanning trees in regular graphs

Let C(G) denote the number of spanning trees of a graph G. It is shown that there is a function ?(k) that tends to zero as k tends to infinity such that for every connected, k-regular simple graph G on n vertices C(G) = {k[1 ? δ(G)]}ⁿ. where 0 ≤ δ(G) ≤ ?(k).     

Colouring Arcwise Connected Sets in the Plane I

Let ? be the family of finite collections ? where ? is a collection of bounded, arcwise connected sets in ℝ² which for any S, T∈? where S∩T≠∅, it holds that S∩T is arcwise connected. We investigate the problem of bounding the chromatic number of the intersection graph G of a collection ?∈?.  Assuming G is triangle-free, suppose there exists a closed Jordan curve C⊂ℝ² such that C intersects all sets of ? and for all S∈?, the following holds: (i) S∩(C∪int (C)) is arcwise connected or S∩int (C)=∅. (ii) S∩(C∪ext (C)) is arcwise connected or S∩ext (C)=∅.  Here int(C) and ext (C) denote the regions in the interior, resp. exterior, of C. Such being the case, we shall show that χ(?) is bounded by a constant independent of ?. Revised: December 3, 1998     

On connectivities of tree graphs

Let T(G) be the tree graph of a graph G with cycle rank r. Then κ(T(G)) ? m(G) ? r, where κ(T(G)) and m(G) denote the connectivity of T(G) and the length of a minimum cycle basis for G, respectively. Moreover, the lower bound of m(G) ? r is best possible.     

Induced matching extendable graphs

We say that a simple graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The main results of this paper are as follows: (1) For every connected IM-extendable graph G with |V(G)| ≥ 4, the girth g(G) ≤ 4. (2) If G is a connected IM-extendable graph, then |E(G)| ≥ ${3\over 2}|V(G)| - 2$; the equality holds if and only if G ≅ T × K₂, where T is a tree. (3) The only 3-regular connected IM-extendable graphs are C_n × K₂, for n ≥ 3, and C_2n(1, n), for n ≥ 2, where C_2n(1, n) is the graph with 2n vertices x₀, x₁, …, x_2n−1, such that x_ix_j is an edge of C_2n(1, n) if either |i − j| ≡ 1 (mod 2n) or |i − j| ≡ n (mod 2n). © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 203–213, 1998     

Contractible subgraphs in k‐connected graphs

For a graph G we define a graph T(G) whose vertices are the triangles in G and two vertices of T(G) are adjacent if their corresponding triangles in G share an edge. Kawarabayashi showed that if G is a k‐connected graph and T(G) contains no edge, then G admits a k‐contractible clique of size at most 3, generalizing an earlier result of Thomassen. In this paper, we further generalize Kawarabayashi's result by showing that if G is k‐connected and the maximum degree of T(G) is at most 1, then G admits a k‐contractible clique of size at most 3 or there exist independent edges e and f of G such that e and f are contained in triangles sharing an edge and G/e/f is k‐connected. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 121–136, 2007     

Conrad frames

A Conrad frame is a frame which is isomorphic to the frame C(G) of all convex ?-subgroups of some lattice-ordered group G. It has long been known that Conrad frames have the disjointification property. In this paper a number of properties are considered that strengthen the disjointification property; they are referred to as the Conrad conditions. A particularly strong form of the disjointification property, the C-frame condition, is studied in detail. The class of lattice-ordered groups G for which C(G) is a C-frame is shown to coincide with the class of pairwise splitting ?-groups. The arguments are mostly frame-theoretic and Choice-free, until one tackles the question of whether C-frames are Conrad frames. They are, but the proof is decidedly not point-free. This proof actually does more: it shows that every algebraic frame with the FIP and disjointification can be coherently embedded in a C-frame. When the discussion is restricted to normal-valued lattice-ordered groups, one is able to produce examples of coherent frames having disjointification, which are not Conrad frames.     

On aschbacher’s localC(G; T) theorem

Aschbacher’s localC(G; T) theorem asserts that ifG is a finite group withF*(G)=O ₂(G), andTεSyl₂(G), thenG=C(G; T)K(G), whereC(G; T)=〈N _G (T ₀)|1≠T ₀ charT〉 andK(G) is the product of all near components ofG of typeL ₂(2 ⁿ ) orA ₂ ⁿ ₊₁. Near components are also known asχ-blocks or Aschbacher blocks. In this paper we give a proof of Aschbacher’s theorem in the case thatG is aK-group, i.e., in the case that every simple section ofG is isomorphic to one of the known simple groups. Our proof relies on a result of Meierfrankenfeld and Stroth [MS] on quadratic four-groups and on the Baumann-Glauberman-Niles theorem, for which Stellmacher [St2] has given an amalgam-theoretic proof. Apart from those results, our proof is essentially self-contained. For John Thompson Supported in part by NSF grant #DMS 89-03124, by DIMACS, an NSF Science and Technology Center, funded under contract STC-88-09648, and by NSA grant #MDA-904-91-H-0043. Prof. Gorenstein died on August 26, 1992.     

Spanning trees with leaf distance at least four

For a graph G, we denote by i(G) the number of isolated vertices of G. We prove that for a connected graph G of order at least five, if i(G–S) < |S| for all ?? ≠ S ? V(G), then G has a spanning tree T such that the distance in T between any two leaves of T is at least four. This result was conjectured by Kaneko in “Spanning trees with constrains on the leaf degree”, Discrete Applied Math, 115 (2001), 73–76. Moreover, the condition in the result is sharp in a sense that the condition i(G–S) < |S| cannot be replaced by i(G–S) ≤ |S|. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 83–90, 2007     

Primitives and central detection numbers in group cohomology

Fix a prime p. Given a finite group G, let H^∗(G) denote its mod p cohomology. In the early 1990s, Henn, Lannes, and Schwartz introduced two invariants d₀(G) and d₁(G) of H^∗(G) viewed as a module over the mod p Steenrod algebra. They showed that, in a precise sense, H^∗(G) is respectively detected and determined by Hd(CG(V)) for d?d₀(G) and d?d₁(G), with V running through the elementary abelian p-subgroups of G.The main goal of this paper is to study how to calculate these invariants. We find that a critical role is played by the image of the restriction of H^∗(G) to H^∗(C), where C is the maximal central elementary abelian p-subgroup of G. A measure of this is the top degree e(G) of the finite dimensional Hopf algebra H^∗(C)_⊗H^∗(G)Fp, a number that tends to be quite easy to calculate.Our results are complete when G has a p-Sylow subgroup P in which every element of order p is central. Using the Benson-Carlson duality, we show that in this case, d₀(G)=d₀(P)=e(P), and a similar exact formula holds for d₁. As a bonus, we learn that He(G)(P) contains nontrivial essential cohomology, reproving and sharpening a theorem of Adem and Karagueuzian.In general, we are able to show that d₀(G)?max{e(CG(V))|V<G} if certain cases of Benson's Regularity Conjecture hold. In particular, this inequality holds for all groups such that the difference between the p-rank of G and the depth of H^∗(G) is at most 2. When we look at examples with p=2, we learn that d₀(G)?14 for all groups with 2-Sylow subgroup of order up to 64, with equality realized when G=SU(3,4).En route we study two objects of independent interest. If C is any central elementary abelian p-subgroup of G, then H^∗(G) is an H^∗(C)-comodule, and we prove that the subalgebra of H^∗(C)-primitives is always Noetherian of Krull dimension equal to the p-rank of G minus the p-rank of C. If the depth of H^∗(G) equals the rank of Z(G), we show that the depth essential cohomology of G is nonzero (reproving and extending a theorem of Green), and Cohen-Macauley in a certain sense, and prove related structural results.     

Degree bounds for the circumference of 3‐connected graphs

Let C be a longest cycle in the 3‐connected graph G and let H be a component of G ? V(C) such that |V(H)| ≥ 3. We supply estimates of the form |C| ≥ 2d(u) + 2d(v) ? α(4 ≤ α ≤ 8), where u,v are suitably chosen non‐adjacent vertices in G. Also the exceptional classes for α = 6,7,8 are characterized. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Unramified cohomology of degree 3 and Noether’s problem

Let G be a finite group and W be a faithful representation of G over C. The group G acts on the field of rational functions C(W). The question whether the field of invariant functions C(W) ^G is purely transcendental over C goes back to Emmy Noether. Using the unramified cohomology group of degree 2 of this field as an invariant, Saltman gave the first examples for which C(W) ^G is not rational over C. Around 1986, Bogomolov gave a formula which expresses this cohomology group in terms of the cohomology of the group G. In this paper, we prove a formula for the prime to 2 part of the unramified cohomology group of degree 3 of C(W) ^G . Specializing to the case where G is a central extension of an F _p -vector space by another, we get a method to construct nontrivial elements in this unramified cohomology group. In this way we get an example of a group G for which the field C(W) ^G is not rational although its unramified cohomology group of degree 2 is trivial. Dedicated to Jean-Louis Colliot-Thélène.     

Actions of Borel Subgroups on Homogeneous Spaces of Reductive Complex Lie Groups and Integrability

Let G be a real reductive Lie group, K its compact subgroup. Let A be the algebra of G-invariant real-analytic functions on T ^*(G/K) (with respect to the Poisson bracket) and let C be the center of A. Denote by 2(G,K) the maximal number of functionally independent functions from A\C. We prove that (G,K) is equal to the codimension (G,K) of maximal dimension orbits of the Borel subgroup BG ^C in the complex algebraic variety G ^C/K ^C. Moreover, if (G,K)=1, then all G-invariant Hamiltonian systems on T ^*(G/K) are integrable in the class of the integrals generated by the symmetry group G. We also discuss related questions in the geometry of the Borel group action.     

Maximal K3's and Hamiltonicity of 4‐connected claw‐free graphs

Let cl(G) denote Ryjá?ek's closure of a claw‐free graph G. In this article, we prove the following result. Let G be a 4‐connected claw‐free graph. Assume that G[N_G(T)] is cyclically 3‐connected if T is a maximal K₃ in G which is also maximal in cl(G). Then G is hamiltonian. This result is a common generalization of Kaiser et al.'s theorem [J Graph Theory 48(4) (2005), 267–276] and Pfender's theorem [J Graph Theory 49(4) (2005), 262–272]. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Graphs whose critical groups have larger rank

The critical group C(G) of a graph G is a refinement of the number of spanning trees of the graph and is closely connected with the Laplacian matrix. Let r(G) be the minimum number of generators (i.e., the rank) of the group C(G) and β(G) be the number of independent cycles of G. In this paper, some forbidden induced subgraphs are given for r(G) = n − 3 and all graphs with r(G) = β(G) = n − 3 are characterized.