On the VC-dimension of uniform hypergraphs

Let be a k-uniform hypergraph on [n] where k−1 is a power of some prime p and n≥ n ₀(k). Our main result says that if , then there exists E ₀∊ such that {E∩ E ₀: E∊ } contains all subsets of E ₀. This improves a longstanding bound of due to Frankl and Pach [7].Research supported in part by NSF grants DMS-0400812 and an Alfred P. Sloan Research Fellowship.Research supported in part by NSA grant H98230-05-1-0079. Part of this research was done while working at University of Illinois at Chicago.     

Finite lattices as relative congruence lattices of finite algebras

Let A be a finite algebra and a quasivariety. By A is meant the lattice of congruences θ on A with . For any positive integer n, we give conditions on a finite algebra A under which for any n-element lattice L there is a quasivariety such that . The author was supported by INTAS grant 03-51-4110.     

The Unbalance of Set Systems

The unbalance of an intersecting family is defined as , where is the maximum degree of i.e. the maximum of over all vertices x. We show that the unbalance of a k-uniform intersecting family is at most when n ≥ 6k ³ and we determine all families achieving this bound.     

Base subsets of symplectic Grassmannians

Let V and V′ be 2n-dimensional vector spaces over fields F and F′. Let also Ω: V× V→ F and Ω′: V′× V′→ F′ be non-degenerate symplectic forms. Denote by Π and Π′ the associated (2n−1)-dimensional projective spaces. The sets of k-dimensional totally isotropic subspaces of Π and Π′ will be denoted by and ${\mathcal G}'_{k}$, respectively. Apartments of the associated buildings intersect and by so-called base subsets. We show that every mapping of to sending base subsets to base subsets is induced by a symplectic embedding of Π to Π′.     

New bounds on the unconstrained quadratic integer programming problem

We consider the maximization for a given symmetric . It was shown recently, using properties of zonotopes and hyperplane arrangements, that in the special case that A has a small rank, so that A = VV ^T where with m < n, then there exists a polynomial time algorithm (polynomial in n for a given m) to solve the problem . In this paper, we use this result, as well as a spectral decomposition of A to obtain a sequence of non-increasing upper bounds on γ with no constraints on the rank of A. We also give easily computable necessary and sufficient conditions for the absence of a gap between the solution and its upper bound. Finally, we incorporate the semidefinite relaxation upper bound into our scheme and give an illustrative example.     

Association schemes from the action of PGL(2, q) fixing a nonsingular conic in PG(2, q)

The group PGL(2,q) has an embedding into PGL(3,q) such that it acts as the group fixing a nonsingular conic in PG(2,q). This action affords a coherent configuration (q) on the set (q) of non-tangent lines of the conic. We show that the relations can be described by using the cross-ratio. Our results imply that the restrictions ₊(q) and ₋(q) of (q) to the set ₊(q) of secant (hyperbolic) lines and to the set ₋(q) of exterior (elliptic) lines, respectively, are both association schemes; moreover, we show that the elliptic scheme ₋(q) is pseudocyclic.We further show that the coherent configurations (q ²) with q even allow certain fusions. These provide a 4-class fusion of the hyperbolic scheme ₊(q ²), and 3-class fusions and 2-class fusions (strongly regular graphs) of both schemes ₊(q ²) and ₋(q ²). The fusion results for the hyperbolic case are known, but our approach here as well as our results in the elliptic case are new.     

Even dimensional higher class groups of orders

Let F be a number field, and let denote the ring of integers in F. Let A be a finite-dimensional central simple F-algebra, and let Λ be an -order in A. In this paper it is shown that the p-torsion of the even dimensional higher class group Cl _2n (Λ) can only occur for primes p, which lie under prime ideals , at which is not maximal, or which divide the dimension of A. Supported by NSFC 10401014, and partially funded by Irish Research Council for Science, Engineering and Technology Basic Research Grant SC/02/265.     

Dy namic of Abelia n Subgroups of GL( n, $$\mathbb{C}$$): A Structure Theorem

In this paper, we characterize the dynamic of every Abelian subgroups of , or . We show that there exists a -invariant, dense open set U in saturated by minimal orbits with a union of at most n -invariant vector subspaces of of dimension n−1 or n−2 over . As a consequence, has height at most n and in particular it admits a minimal set in . This work is supported by the research unit: systèmes dynamiques et combinatoire: 99UR15-15     

Lines of Minima and Teichmüller Geodesics

For two measured laminations ν⁺ and ν⁻ that fill up a hyperbolizable surface S and for , let be the unique hyperbolic surface that minimizes the length function e ^t l(ν⁺) + e ^-t l(ν⁻) on Teichmüller space. We characterize the curves that are short in and estimate their lengths. We find that the short curves coincide with the curves that are short in the surface on the Teichmüller geodesic whose horizontal and vertical foliations are respectively, e ^t ν⁺ and e ^t ν⁻. By deriving additional information about the twists of ν⁺ and ν⁻ around the short curves, we estimate the Teichmüller distance between and . We deduce that this distance can be arbitrarily large, but that if S is a once-punctured torus or four-times-punctured sphere, the distance is bounded independently of t. Received: May 2006, Revision: November 2006, Accepted: February 2007     

Some constructions on the Hermitian surface

In the geometric setting of commuting orthogonal and unitary polarities we construct an infinite family of complete (q + 1)²–spans of the Hermitian surface , q odd. A construction of an infinite family of minimal blocking sets of , q odd, admitting PSL ₂(q), is also provided.      

On equivariant embedding of Hilbert <Emphasis Type="Italic">C</Emphasis>* modules

We prove that an arbitrary (not necessarily countably generated) Hilbert G - module on a G - C ^* algebra admits an equivariant embedding into a trivial G - module, provided G is a compact Lie group and its action on is ergodic.     

Orbits of the hyperoctahedral group as Euclidean designs

The hyperoctahedral group H in n dimensions (the Weyl group of Lie type B _n ) is the subgroup of the orthogonal group generated by all transpositions of coordinates and reflections with respect to coordinate hyperplanes.With e ₁ , ..., e _n denoting the standard basis vectors of ⁿ and letting x _k = e ₁ + ··· + e _k (k = 1, 2, ..., n), the set

Blocking sets in PG(2, q n ) from cones of PG(2n, q)

Let Ω and be a subset of Σ = PG(2n−1,q) and a subset of PG(2n,q) respectively, with Σ ⊂ PG(2n,q) and . Denote by K the cone of vertex Ω and base and consider the point set B defined by

Coloured peak algebras and Hopf algebras

For G a finite abelian group, we study the properties of general equivalence relations on G _n = G ⁿ ⋊ _n , the wreath product of G with the symmetric group _n , also known as the G-coloured symmetric group. We show that under certain conditions, some equivalence relations give rise to subalgebras of G _n as well as graded connected Hopf subalgebras of ⨁ _{n≥ o} G _n . In particular we construct a G-coloured peak subalgebra of the Mantaci-Reutenauer algebra (or G-coloured descent algebra). We show that the direct sum of the G-coloured peak algebras is a Hopf algebra. We also have similar results for a G-colouring of the Loday-Ronco Hopf algebras of planar binary trees. For many of the equivalence relations under study, we obtain a functor from the category of finite abelian groups to the category of graded connected Hopf algebras. We end our investigation by describing a Hopf endomorphism of the G-coloured descent Hopf algebra whose image is the G-coloured peak Hopf algebra. We outline a theory of combinatorial G-coloured Hopf algebra for which the G-coloured quasi-symmetric Hopf algebra and the graded dual to the G-coloured peak Hopf algebra are central objects. 2000 Mathematics Subject Classification Primary: 16S99; Secondary: 05E05, 05E10, 16S34, 16W30, 20B30, 20E22Bergeron is partially supported by NSERC and CRC, CanadaHohlweg is partially supported by CRC     

Partial geometries pg (s, t, 2) with an abelian Singer group and a characterization of the van Lint-Schrijver partial geometry

Let be a proper partial geometry pg(s,t,2), and let G be an abelian group of automorphisms of acting regularly on the points of . Then either t≡2±od s+1 or is a pg(5,5,2) isomorphic to the partial geometry of van Lint and Schrijver (Combinatorica 1 (1981), 63–73). This result is a new step towards the classification of partial geometries with an abelian Singer group and further provides an interesting characterization of the geometry of van Lint and Schrijver.The author is Postdoctoral Fellow of the Fund for Scientific Research Flanders (FWO-Vlaanderen).     

Linear connections of a framed distribution of hyperplane elements in conformal space

We study the geometry of affine and normal connections induced by a complete normalization of mutually orthogonal distributions $ \mathcal{M} We study the geometry of affine and normal connections induced by a complete normalization of mutually orthogonal distributions and in conformal space C _n , where is a distribution of hyperplane elements, and is a distribution of line elements. We consider invariant fields of pencils that are parallel with respect to the normal connection along any curve belonging to the distribution . Original Russian Text ? A.M. Matveeva, 2008, published in Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2008, No. 7, pp. 79–84.     

Large Deviations for Quantum Markov Semigroups on the 2 × 2-Matrix Algebra

Let be a predual quantum Markov semigroup acting on the full 2 × 2-matrix algebra and having an absorbing pure state. We prove that for any initial state ω, the net of orthogonal measures representing the net of states satisfies a large deviation principle in the pure state space, with a rate function given in terms of the generator, and which does not depend on ω. This implies that is faithful for all t large enough. Examples arising in weak coupling limit are studied. Submitted: January 9, 2008. Accepted: April 15, 2008.     

On the negative cyclic homology of <Emphasis Type="Italic">shc</Emphasis>-algebras

Let be a field of characteristic and S ¹ the unit circle. We prove that the shc-structure on a cochain algebra (A,d _A ) induces an associative product on the negative cyclic homology HC _*⁻ A. When the cochain algebra (A,d _A ) is the algebra of normalized cochains of the simply connected topological space X with coefficients in , then HC _*⁻ A is isomorphic as a graded algebra to the S ¹-equivariant cohomology algebra of LX, the free loop space of X. We use the notion of shc-formality introduced in Topology 41, 85–106 (2002) to compute the S ¹-equivariant cohomology algebras of the free loop space of the complex projective space when n + 1 = 0 [p] and of the even spheres S ²ⁿ when p = 2.      

Quelques Résultats sur les Algèbres Flexibles Préhilbertiennes sans Diviseurs de Zéro Vérifiant ∥a 2∥ = ∥a∥2

Résumé. Soit A une algèbre réelle. On suppose que l’espace vectoriel A est muni d’une norme ∥.∥ préhilbertienne vérifiant ∥a ²∥ = ∥a∥² pour tout . Si A est flexible, sans diviseurs de zéro et de dimension ≤ 4, alors A est isomorphe à ou , ce qui généralise un théorème d’El-Mallah [1]. Si A est flexible, sans diviseurs de zéro, contenant un idempotent central et vérifiant la propriété d’Osborn, alors A est de dimension finie et isomorphe à , ou . Enfin nous montrons qu’une algèbre normée préhilbertienne unitaire d’unité e telle que ∥e∥ = 1 est flexible et vérifie ∥a ²∥ = ∥ a∥².

---

Let A be a real algebra. Assuming that a vector space A is endowed with a pre-Hilbert norm ∥.∥ satisfying ∥a ²∥ = ∥a∥² for all . If A is flexible, without divisor of zero and of a dimension ≤ 4, then A is isomorphic to or , which generalize El-Mallah’s theorem [1]. If A is flexible, without divisor of zero, containing a central idempotent and satisfying Osborn’s properties, then A is finite dimensional and isomorphic to , or . Finally we prove that a normed pre-Hilbert algebra with unit e such that ∥e∥ = 1 is flexible and satisfies ∥a ²∥ = ∥a∥².