Graphical properties related to minimal imperfection

Say that graph G is partitionable if there exist integers α?2, ω? 2, such that |V(G)| ≡ αω + 1 and for every υ?V(G) there exist partitions of V(G)\ υ into stable sets of size α and into eliques of size ω. An immediate consequence of Lovász' characterization of perfect graphs is that every minimal imperfect graph G is partitionable with α ≡ α (G) andω ≡ ω(G).Padberg has shown that in every minimal imperfect graph G the cliques and stable sets of maximum size satisfy a series of conditions that reflect extraordinary symmetry G. Among these conditions are: the number of cliques of size ω(G) is exactly |V(G)|; the number of stable sets of size α(G) is exactly |V(G)|: every vertex of G is contained in exactly ω(G) cliques of size ω(G) and α(G) stable sets of size α(G): for every clique Q (respectively, stable set S) of maximum size there is a unique stable set S (clique O) of maximum size such that Q∩S ≡ Ø.Let C_n^k denote the graph whose vertices can be enumerated as υ₁,…,υ_n in such a way that υ₁ and υ₁ are adjacent in G if and only if i and j differ by at most k, modulo n. Chvátal has shown that Berge's Strong Perfect graph Conjecture is equivalent to the conjecture that if G is minimal imperfect with α(G) ≡ αandω(G) ≡ ω, then G has a spanning subgraph isomorphic to C_αω+1^ω. Padberg's conditions are sufficiently restrictive to suggest the possibility of establishing the Strong Perfect Graph Conjecture by proving that any graph G satisfying these conditions must contain a spanning subgraph isomorphic to C_αω+1^ω, whereα(G) ≡ αandω(G) ≡ ω. It is shown here, using only elementary linear algebra, that all partitionable graphs satisfy Padberg's conditions, as well as additional properties of the same spirit. Then examples are provided of partitionable graphs which contain no spanning subgraph isomorphic to C_αω+1^ω, whereα(G) ≡ α and ω(G) ≡ ω.     

Spectral properties of metastable Markov semigroups

It is shown that if a symmetric Markov semigroup e^?Ht on the Hilbert space L²(X) is hypercontractive, then the approximate degeneracy of the ground state has several consequences concerning other parts of the spectrum of H and concerning the unitary group e^?iHt. In particular, in the presence of a space inversion symmetry, all the eigenvalues occur in pairs with gaps comparable to the gap between the bottom two eigenvalues.     

Martin’s Maximum and tower forcing

There are several examples in the literature showing that compactness-like properties of a cardinal κ cause poor behavior of some generic ultrapowers which have critical point κ (Burke [1] when κ is a supercompact cardinal; Foreman-Magidor [6] when κ = ω ₂ in the presence of strong forcing axioms). We prove more instances of this phenomenon. First, the Reflection Principle (RP) implies that if $\overrightarrow I $ is a tower of ideals which concentrates on the class $GI{C_{{\omega _1}}}$ of ω ₁-guessing, internally club sets, then $\overrightarrow I $ is not presaturated (a set is ω ₁-guessing iff its transitive collapse has the ω ₁-approximation property as defined in Hamkins [10]). This theorem, combined with work from [16], shows that if PFA ⁺ or MM holds and there is an inaccessible cardinal, then there is a tower with critical point ω ₂ which is not presaturated; moreover, this tower is significantly different from the non-presaturated tower already known (by Foreman-Magidor [6]) to exist in all models of Martin’s Maximum. The conjunction of the Strong Reflection Principle (SRP) and the Tree Property at ω ₂ has similar implications for towers of ideals which concentrate on the wider class $GI{C_{{\omega _1}}}$ of ω ₁-guessing, internally stationary sets. Finally, we show that the word “presaturated” cannot be replaced by “precipitous” in the theorems above: Martin’s Maximum (which implies SRP and the Tree Property at ω ₂) is consistent with a precipitous tower on $GI{C_{{\omega _1}}}$ .     

Weights of the l-adic cohomology of a proper toric variety

We describe the weights of the l-adic cohomology groups of a toric variety over a finite field k in terms of the Ishida complexes of Z-modules. As a consequence, we conclude that, for an r-dimensional proper toric variety X, the m-th cohomology group H^m (X?_k[kbar],Q_l) is of pure weight if m = 0,1,2,3,2r - 3,2r - 2,2r - 1,2r.Furthermore, we show that, for any m such that 3 < m < 2r - 3,there exists an r-dimensional proper toric variety whose m-th cohomology group H^m (X?_k[kbar],Q _l ) is not pure.     

On completely nonmeasurable unions

Assume that there is no quasi-measurable cardinal not greater than 2^ω . We show that for a c. c. c. σ -ideal 𝕀 with a Borel base of subsets of an uncountable Polish space, if 𝒜 is a point-finite family of subsets from 𝕀, then there is a subfamily of 𝒜 whose union is completely nonmeasurable, i.e. its intersection with every non-small Borel set does not belong to the σ -field generated by Borel sets and the ideal 𝕀. This result is a generalization of the Four Poles Theorem (see [1]) and a result from [3]. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

HFD groups in the Solovay model

Hajnal and Juhász proved that under CH there is a hereditarily separable, hereditarily normal topological group without non-trivial convergent sequences that is countably compact and not Lindelöf. The example constructed is a topological subgroup H⊆ω₁² that is an HFD with the following property

(P)

the projection of H onto every partial product I² for I∈ω[ω₁] is onto.

Any such group has the necessary properties. We prove that if κ is a cardinal of uncountable cofinality, then in the model obtained by forcing over a model of CH with the measure algebra on κ², there is an HFD topological group in ω₁² which has property (P).     

Transposing a matrix by similarity operations

A matrix T is said to co-transpose a square matrix A if T^?1AT=A′ and T^?1A′T=A. For every n?3 there exists a real n×n matrix which cannot be co-transposed by any matrix. However, it is shown that the following classes of real matrices can be co-transposed by a symmetric matrix of order two: 2×2 matrices, normal matrices, and matrices whose square is symmetric.     

<Emphasis Type="Italic">M</Emphasis>-slenderness

Analogues of Nunke’s theorem are proved which characterize variants of slenderness. For a bounded monotone subgroup M of ? ^ω , a torsion-free reduced abelian group G is M-slender if, and only if, there is no monomorphism from M into G. It is consistent relative to ordinary set theory (ZFC) that if M ≠ ? ^ω is an unbounded monotone subgroup of ? ^ω , then a torsion-free reduced abelian group G is M-slender if, and only if, there is no monomorphism from M into G.     

Die Klassengruppen quadratischer und kubischer Zahlkörper und die Selmergruppen gewisser elliptischer Kurven

For k∈?\0 we define the elliptic curve A_k, by the equation: Y²=X³+k. Let C(k) be the class group of \(K_o = Q(\sqrt[6]{k})\) . If k is a square we find a close connection between the elements of order 2 of the Selmer group of A_k and C(k); there is a corresponding connection between the elements of order 3 if k is a cube and satisfies some additional conditions. The main tool to prove the statements is the global and local Galois cohomology of elliptic curves; it seems remarkable that nearly no “explicit” number theory has to be used.     

A coherent family of partial functions on

We prove that there is a family of partial functions is a tower in such that every surjection is associated to a cohomologically different Hausdorff gap (see Talayco). This improves a result of Talayco.

     

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.     

The quasi order of graphs on an ordinal

For α an ordinal, a graph with vertex set α may be represented by its characteristic function, f:[α]²→2, where f({γ,δ})=1 if and only if the pair {γ,δ} is joined in the graph. We call these functions α-colorings.We introduce a quasi order on the α-colorings (graphs) by setting f≤g if and only if there is an order-preserving mapping t:α→α such that f({γ,δ})=g({t(γ),t(δ)}) for all {γ,δ}∈[α]². An α-coloring f is an atom if g≤f implies f≤g.We show that for α=ω^ω below every coloring there is an atom and there are continuum many atoms. For α<ω^ω below every coloring there is an atom and there are finitely many atoms.     

ON THE STRUCTURE OF COHOMOLOGY RINGS OF p-NILPOTENT LIE ALGEBRAS

In this paper the authors investigate the structure of the restricted Lie algebra cohomology of p-nilpotent Lie algebras with trivial p-power operation. Our study is facilitated by a spectral sequence whose E ₂-term is the tensor product of the symmetric algebra on the dual of the Lie algebra with the ordinary Lie algebra cohomology and converges to the restricted cohomology ring. In many cases this spectral sequence collapses, and thus, the restricted Lie algebra cohomology is Cohen–Macaulay. A stronger result involves the collapsing of the spectral sequence and the cohomology ring identifying as a ring with the E ₂-term. We present criteria for the collapsing of this spectral sequence and provide some examples where the ring isomorphism fails. Furthermore, we show that there are instances when the spectral sequence does not collapse and yields cohomology rings which are not Cohen-Macaulay.     

Correlative sparsity structures and semidefinite relaxations for concave cost transportation problems with change of variables

We present a hierarchy of semidefinite programming (SDP) relaxations for solving the concave cost transportation problem (CCTP), which is known to be NP-hard, with p suppliers and q demanders. In particular, we study cases in which the cost function is quadratic or square-root concave. The key idea of our relaxation methods is in the change of variables to CCTPs, and due to this, we can construct SDP relaxations whose matrix variables are of size O((min {p, q}) ^ω ) in the relaxation order ω. The sequence of optimal values of SDP relaxations converges to the global minimum of the CCTP as the relaxation order ω goes to infinity. Furthermore, the size of the matrix variables can be reduced to O((min {p, q}) ^ω-1 ), ω ≥  2 by using Reznick’s theorem. Numerical experiments were conducted to assess the performance of the relaxation methods.     

The spectral sequence relating algebraic K-theory to motivic cohomology

Beginning with the Bloch-Lichtenbaum exact couple relating the motivic cohomology of a field F to the algebraic K-theory of F, the authors construct a spectral sequence for any smooth scheme X over F whose E₂ term is the motivic cohomology of X and whose abutment is the Quillen K-theory of X. A multiplicative structure is exhibited on this spectral sequence. The spectral sequence is that associated to a tower of spectra determined by consideration of the filtration of coherent sheaves on X by codimension of support.     

Realcompact subspaces

We show that every compact space of large enough size has a realcompact subspace of size κ, for κ?c. We also show that an uncountable realcompact space whose pseudocharacter is at most ω₁, has a realcompact subspaces of size ω₁, thus, by continuum hypothesis, every uncountable realcompact space has realcompact subspace of size ω₁.     

Bounded cohomology of lattices in higher rank Lie groups

We prove that the natural map H_b ²(Γ)?H²(Γ) from bounded to usual cohomology is injective if Γ is an irreducible cocompact lattice in a higher rank Lie group. This result holds also for nontrivial unitary coefficients, and implies finiteness results for Γ: the stable commutator length vanishes and any C¹–action on the circle is almost trivial. We introduce the continuous bounded cohomology of a locally compact group and prove our statements by relating H_b ^•(Γ) to the continuous bounded cohomology of the ambient group with coefficients in some induction module. Received July 14, 1998 / final version received January 7, 1999     

Genericity for Mathias forcing over general Turing ideals

We construct a homogeneous subspace of 2^ω whose complement is dense in 2^ω and rigid. Using the same method, assuming Martin’s Axiom, we also construct a countable dense homogeneous subspace of 2^ω whose complement is dense in 2^ω and rigid.     

Relative Group Cohomology and The Orbit Category

Let G be a finite group and ? be a family of subgroups of G closed under conjugation and taking subgroups. We consider the question whether there exists a periodic relative ?-projective resolution for ? when ? is the family of all subgroups H ≤ G with rk H ≤ rkG ? 1. We answer this question negatively by calculating the relative group cohomology ?H*(G, 𝔽₂) where G = ?/2 × ?/2 and ? is the family of cyclic subgroups of G. To do this calculation we first observe that the relative group cohomology ?H*(G, M) can be calculated using the ext-groups over the orbit category of G restricted to the family ?. In second part of the paper, we discuss the construction of a spectral sequence that converges to the cohomology of a group G and whose horizontal line at E ₂ page is isomorphic to the relative group cohomology of G.     

Continuous Linear Extension of Ultradifferentiable Functions of Beurling Type

For a weight function ω and a closed set A ? ?^N let ?_(ω)(A) denote the space of all ω-Whitney jets of Beurling type on A. It is shown that for each closed set A ? ?^N there exists an ω-extension operator EA: ?_(ω)(A) → ?_(ω)(?^N) if and only if ω is a (DN)-function (see MEISE and TAYLOR [18], 3.3). Moreover for a fixed compact set K ? ?^N there exists an ω-extension operator E_K: ?_(ω)(K) → ?_(ω)(?^N) if and only if the Fréchet space ?_(ω)(K) satisfies the property (DN) (see Vogt [29], 1.1.).