Nested set complexes of Dowling lattices and complexes of Dowling trees

Given a finite group G and a natural number n, we study the structure of the complex of nested sets of the associated Dowling lattice (Proc. Internat. Sympos., 1971, pp. 101–115) and of its subposet of the G-symmetric partitions which was recently introduced by Hultman (, 2006), together with the complex of G-symmetric phylogenetic trees . Hultman shows that the complexes and are homotopy equivalent and Cohen–Macaulay, and determines the rank of their top homology. An application of the theory of building sets and nested set complexes by Feichtner and Kozlov (Selecta Math. (N.S.) 10, 37–60, 2004) shows that in fact is subdivided by the order complex of . We introduce the complex of Dowling trees and prove that it is subdivided by the order complex of . Application of a theorem of Feichtner and Sturmfels (Port. Math. (N.S.) 62, 437–468, 2005) shows that, as a simplicial complex, is in fact isomorphic to the Bergman complex of the associated Dowling geometry. Topologically, we prove that is obtained from by successive coning over certain subcomplexes. It is well known that is shellable, and of the same dimension as . We explicitly and independently calculate how many homology spheres are added in passing from to . Comparison with work of Gottlieb and Wachs (Adv. Appl. Math. 24(4), 301–336, 2000) shows that is intimely related to the representation theory of the top homology of . Research partially supported by the Swiss National Science Foundation, project PP002-106403/1.     

Approach Theory in a Category: A Study of Compactness and Hausdorff Separation

In a topological construct endowed with a proper -factorization system and a concrete functor , we study -compactness and -Hausdorff separation, where is a class of “closed morphisms” in the sense of Clementino et al. (A functional approach to general topology. In: Categorical Foundations. Encyclopedia of Mathematics and Its Applications, vol. 97, pp. 103–163. Cambridge University Press, Cambridge, 2004), determined by Λ. In particular, we point out under which conditions on Λ, the notion of -compactness of an object of coincides with 0-compactness of the image in Prap. Our results will be illustrated by some examples: except for some well-known ones, like b-compactness of a topological space, we also capture some compactness notions that were not considered before in the literature. In particular, we obtain a generalization of b-compactness to the setting of approach spaces. This notion is shown to play an important role in the study of uniformizability. The author is research assistant at the Fund of Scientific Research Vlaanderen (FWO).     

Range of the Fractional Weak Discrepancy Function

In this paper we describe the range of values that can be taken by the fractional weak discrepancy of a poset and characterize semiorders in terms of these values. In [6], we defined the fractional weak discrepancy of a poset to be the minimum nonnegative for which there exists a function satisfying (1) if then and (2) if then . This notion builds on previous work on weak discrepancy in [3, 7, 8]. We prove here that the range of values of the function is the set of rational numbers that are either at least one or equal to for some nonnegative integer . Moreover, is a semiorder if and only if , and the range taken over all semiorders is the set of such fractions .The third author's work was supported in part by a Wellesley College Brachman Hoffman Fellowship.     

On pairs of commuting nilpotent matrices

Let B be a nilpotent matrix and suppose that its Jordan canonical form is determined by a partition λ. Then it is known that its nilpotent commutator is an irreducible variety and that there is a unique partition μ such that the intersection of the orbit of nilpotent matrices corresponding to μ with is dense in . We prove that map given by is an idempotent map. This answers a question of Basili and Iarrobino [9] and gives a partial answer to a question of Panyushev [18]. In the proof, we use the fact that for a generic matrix the algebra generated by A and B is a Gorenstein algebra. Thus, a generic pair of commuting nilpotent matrices generates a Gorenstein algebra. We also describe in terms of λ if has at most two parts.     

Upward Three-Dimensional Grid Drawings of Graphs

A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line segments representing the edges do not cross. Our aim is to produce three-dimensional grid drawings with small bounding box volume. Our first main result is that every -vertex graph with bounded degeneracy has a three-dimensional grid drawing with volume. This is the largest known class of graphs that have such drawings. A three-dimensional grid drawing of a directed acyclic graph (dag) is upward if every arc points up in the -direction. We prove that every dag has an upward three-dimensional grid drawing with volume, which is tight for the complete dag. The previous best upper bound was . Our main result concerning upward drawings is that every -colourable dag ( constant) has an upward three-dimensional grid drawing with volume. This result matches the bound in the undirected case, and improves the best known bound from for many classes of dags, including planar, series parallel, and outerplanar. Improved bounds are also obtained for tree dags. We prove a strong relationship between upward three-dimensional grid drawings, upward track layouts, and upward queue layouts. Finally, we study upward three-dimensional grid drawings with bends in the edges.Research of Vida Dujmovi is supported by NSERC. Research of David Wood is supported by the Government of Spain grant MEC SB2003-0270 and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.     

Point Counting in Families of Hyperelliptic Curves

Let E _Γ be a family of hyperelliptic curves defined by , where is defined over a small finite field of odd characteristic. Then with in an extension degree n field over this small field, we present a deterministic algorithm for computing the zeta function of the curve by using Dwork deformation in rigid cohomology. The time complexity of the algorithm is and it needs bits of memory. A slight adaptation requires only space, but costs time . An implementation of this last result turns out to be quite efficient for n big enough. H. Hubrechts is a Research Assistant of the Research Foundation–Flanders (FWO–Vlaanderen).     

Richardson Elements for Parabolic Subgroups of Classical Groups in Positive Characteristic

Let G be a simple algebraic group of classical type over an algebraically closed field k. Let P be a parabolic subgroup of G and let be the Lie algebra of P with Levi decomposition , where is the Lie algebra of the unipotent radical of P and ł is a Levi complement. Thanks to a fundamental theorem of Richardson (Bull. London Math. Soc. 6:21–24, 1974), P acts on with an open dense orbit; this orbit is called the Richardson orbit and its elements are called Richardson elements. Recently Baur (J. Algebra 297(1):168–185, 2006), the first author gave constructions of Richardson elements in the case for many parabolic subgroups P of G. In this note, we observe that these constructions remain valid for any algebraically closed field k of characteristic not equal to 2 and we give constructions of Richardson elements for the remaining parabolic subgroups. Presented by Peter Littelmann.     

Relations between different types of spectra and spectral characterizations

In the study of the asymptotic behaviour of solutions of differential-difference equations the -spectrum has been useful, where and implies Fourier transform , with given , φ∈L ^∞(ℝ,X), X a Banach space, (half)line. Here we study and related concepts, give relations between them, especially weak Laplace half-line spectrum of φ, and thus ⊂ classical Beurling spectrum = Carleman spectrum =  ; also  = Beurling spectrum of “φ modulo ” (Chill-Fasangova). If satisfies a Loomis type condition (L _U ), then countable and uniformly continuous ∈U are shown to imply ; here (L _U ) usually means , indefinite integral Pf of f in U imply Pf in (the Bohl-Bohr theorem for = almost periodic functions, U=bounded functions). This spectral characterization and other results are extended to unbounded functions via mean classes , ℳ ^m U ((2.1) below) and even to distributions, generalizing various recent results for uniformly continuous bounded φ. Furthermore for solutions of convolution systems S*φ=b with in some we show . With these above results, one gets generalizations of earlier results on the asymptotic behaviour of solutions of neutral integro-differential-difference systems. Also many examples and special cases are discussed.     

On Rank Functions of Lattices

Let be a lattice of finite height. The correspondence between closure operators and ∧-subsemilattices is well known. Here we investigate what type of number-valued function is induces a ∧-subsemilattice ; and if so, what kind of . Conversely, what type of function is induced by what type of (or cl). Several results known for matroids, greedoids, or semimodular lattices are generalized.     

Selections of lattice-ordered Groups

It is well known that the quasitorsion class of archimedean -groups is the class of -groups G such that every closed convex -subgroup is a polar, and it is also well known that the class of -groups G such that every convex -subgroup is a polar is a torsion class. By defining a selection on -groups, these two results are generalized to show, whenever and are selections on -groups, the class of -groups G such that is a radical class. Three selections in particular — all convex -subgroups, all polars, and all closed convex -subgroups — and the radical classes determined by them are studied in some detail. Received March 7, 2006; accepted in final form August 29, 2006.     

Symmetric groups and expander graphs

We construct explicit generating sets S _n and of the alternating and the symmetric groups, which turn the Cayley graphs and into a family of bounded degree expanders for all n.     

Periodic automorphisms of takiff algebras, contractions, and θ-groups

Let be an algebraic Lie algebra and a (generalised) Takiff algebra. Any finite-order automorphism θ of induces an automorphism of of the same order, denoted . We study invariant-theoretic properties of representations of the fixed point subalgebra of on other eigenspaces of in . We use the observation that, for special values of m, the fixed point subalgebra, , turns out to be a contraction of a certain Lie algebra associated with and θ. To my teacher Supported in part by R.F.B.R. grant 06-01-72550.     

Inequalities of the Brunn–Minkowski type for Gaussian measures

Let be an integer, let γ be the standard Gaussian measure on , and let . Given this paper gives a necessary and sufficient condition such that the inequality is true for all Borel sets A ₁,...,A _m in of strictly positive γ-measure or all convex Borel sets A ₁,...,A _m in of strictly positive γ-measure, respectively. In particular, the paper exhibits inequalities of the Brunn–Minkowski type for γ which are true for all convex sets but not for all measurable sets.      

On the Circumference of 2-Connected $$\mathcal{P}_{3}$$-Dominated Graphs

Let G be a connected graph. For at distance 2, we define , and , if then . G is quasi-claw-free if it satisfies , and G is P ₃-dominated() if it satisfies , for every pair (x, y) of vertices at distance 2. Certainly contains as a subclass. In this paper, we prove that the circumference of a 2-connected P ₃-dominated graph G on n vertices is at least min or , moreover if then G is hamiltonian or , where is a class of 2-connected nonhamiltonian graphs.     

Dedekind–MacNeille Completion of n-ordered Sets

A completion of an n-ordered set is defined, by analogy with the case of posets (2-ordered sets), as a pair , where Q is a complete n-lattice and is an n-order embedding. The Basic Theorem of Polyadic Concept Analysis is exploited to construct a completion of an arbitrary n-ordered set. The completion reduces to the Dedekind–MacNeille completion in the dyadic case, the case of posets. A characterization theorem is provided, analogous to the well-known dyadic one, for the case of joined n-ordered sets. The condition of joinedness is trivial in the dyadic case and, therefore, this characterization theorem generalizes the uniqueness theorem for the Dedekind–MacNeille completion of an arbitrary poset.      

Computing Minimum-Volume Enclosing Axis-Aligned Ellipsoids

Given a set of points and ε>0, we propose and analyze an algorithm for the problem of computing a (1+ε)-approximation to the minimum-volume axis-aligned ellipsoid enclosing . We establish that our algorithm is polynomial for fixed ε. In addition, the algorithm returns a small core set , whose size is independent of the number of points m, with the property that the minimum-volume axis-aligned ellipsoid enclosing is a good approximation of the minimum-volume axis-aligned ellipsoid enclosing . Our computational results indicate that the algorithm exhibits significantly better performance than the theoretical worst-case complexity estimate. This work was supported in part by the National Science Foundation through CAREER Grants CCF-0643593 and DMI-0237415.     

Constructions of p-ary Quadratic Bent Functions

Bent functions have many applications in the fields of coding theory, communications and cryptography. This paper studies the constructions of bent functions having the form for odd n and for even n, over the finite field of odd characteristic p, where . Based on the irreducibility of some polynomials on , we focus on characterizing the bent functions for n=p ^v q ^r and n=2p ^v q ^r , where is an odd prime and p a primitive root modulo q ². Moreover, the enumerations of those functions are also considered. Partially supported by the NSF of China under Grants No. 60603012 and No. 60573053.     

Nilpotent Bicone and Characteristic Submodule of a Reductive Lie Algebra

Let be a finite-dimensional complex reductive Lie algebra and S() its symmetric algebra. The nilpotent bicone of is the subset of elements (x, y) of whose subspace generated by x and y is contained in the nilpotent cone. The nilpotent bicone is naturally endowed with a scheme structure, as nullvariety of the augmentation ideal of the subalgebra of generated by the 2-order polarizations of invariants of . The main result of this paper is that the nilpotent bicone is a complete intersection of dimension , where and are the dimensions of Borel subalgebras and the rank of , respectively. This affirmatively answers a conjecture of Kraft and Wallach concerning the nullcone [KrW2]. In addition, we introduce and study in this paper the characteristic submodule of . The properties of the nilpotent bicone and the characteristic submodule are known to be very important for the understanding of the commuting variety and its ideal of definition. The main difficulty encountered for this work is that the nilpotent bicone is not reduced. To deal with this problem, we introduce an auxiliary reduced variety, the principal bicone. The nilpotent bicone, as well as the principal bicone, are linked to jet schemes. We study their dimensions using arguments from motivic integration. Namely, we follow methods developed by Mustaţǎ in [Mu]. Finally, we give applications of our results to invariant theory.     

Riesz and Poisson-Jensen Representation Formulas for a Class of Ultraparabolic Operators on Lie Groups

The aim of this paper is to give some representation formulas of Riesz and Poisson-Jensen type for super-solutions to a class of hypoelliptic ultraparabolic operators on a homogeneous Lie group . Our results complete the ones obtained in Cinti (Math Scand 100:1–21, 2007). We also provide a suitable theory for -Green functions and for -Green potentials of Radon measures. The proofs mostly rely on the use of appropriate techniques relevant to the Potential Theory for . Investigation supported by University of Bologna. Funds for selected research topics.     

Every Finite Topology is Generated by a Partial Pseudometric

Given any preorder on a finite set , we present an algorithm to construct a partial pseudometric on which generates in the sense that if and only if . The specialization topology generated by agrees with the topology generated by the partial pseudometric -balls, and consequently any topology on is generated by a partial pseudometric.