Assouad-Nagata dimension of locally finite groups and asymptotic cones

In this paper we study two problems concerning Assouad-Nagata dimension:

(1)

Is there a metric space of positive asymptotic Assouad-Nagata dimension such that all of its asymptotic cones are of Assouad-Nagata dimension zero? (Dydak and Higes, 2008 [11, Question 4.5]).

(2)

Suppose G is a locally finite group with a proper left invariant metric dG. If dimAN(G,dG)>0, is dimAN(G,dG) infinite? (Brodskiy et al., preprint [6, Problem 5.3]).

The first question is answered positively. We provide examples of metric spaces of positive (even infinite) Assouad-Nagata dimension such that all of its asymptotic cones are ultrametric. The metric spaces can be groups with proper left invariant metrics.The second question has a negative solution. We show that for each n there exists a locally finite group of Assouad-Nagata dimension n. As a consequence this solves for non-finitely generated countable groups the question about the existence of metric spaces of finite asymptotic dimension whose asymptotic Assouad-Nagata dimension is larger but finite.     

A canonical form for nonderogatory matrices under unitary similarity

A square matrix is nonderogatory if its Jordan blocks have distinct eigenvalues. We give canonical forms for

•

nonderogatory complex matrices up to unitary similarity, and

•

pairs of complex matrices up to similarity, in which one matrix has distinct eigenvalues.

The types of these canonical forms are given by undirected and, respectively, directed graphs with no undirected cycles.     

Graph operations that are good for greedoids

S is a local maximum stable set of a graph G, and we write S∈Ψ(G), if the set S is a maximum stable set of the subgraph induced by S∪N(S), where N(S) is the neighborhood of S. In Levit and Mandrescu (2002) [5] we have proved that Ψ(G) is a greedoid for every forest G. The cases of bipartite graphs and triangle-free graphs were analyzed in Levit and Mandrescu (2003) [6] and Levit and Mandrescu (2007) [7] respectively.In this paper we give necessary and sufficient conditions for Ψ(G) to form a greedoid, where G is:

(a)

the disjoint union of a family of graphs;

(b)

the Zykov sum of a family of graphs;

(c)

the corona X°{H₁,H₂,…,H_n} obtained by joining each vertex x of a graph X to all the vertices of a graph H_x.

     

On some contributions of John Horváth to the theory of distributions

Our main task is a presentation of J. Horváth's results concerning

•

singular and hypersingular integral operators,

•

the analytic continuation of distribution-valued meromorphic functions, and

•

a general definition of the convolution of distributions.

At some instances minor supplements to his results are given.     

Norm continuity of weakly continuous mappings into Banach spaces

Let T be the class of Banach spaces E for which every weakly continuous mapping from an α-favorable space to E is norm continuous at the points of a dense subset. We show that:

•

T contains all weakly Lindelöf Banach spaces;

•

l^∞∉T, which brings clarity to a concern expressed by Haydon ([R. Haydon, Baire trees, bad norms and the Namioka property, Mathematika 42 (1995) 30-42], pp. 30-31) about the need of additional set-theoretical assumptions for this conclusion. Also, (l^∞/c₀)∉T.

•

T is stable under weak homeomorphisms;

•

E∈T iff every quasi-continuous mapping from a complete metric space to (E,weak) is densely norm continuous;

•

E∈T iff every quasi-continuous mapping from a complete metric space to (E,weak) is weakly continuous at some point.

     

Maximum weight edge-constrained matchings

Practical questions arising from (for instance) biological applications can often be expressed as classical optimization problems with specific, new features. We are interested here in the version of the maximum weight matching problem (on a graph G) obtained by (1) defining a set F of pairs of incompatible edges of G and (2) asking that the matching contains at most one edge in each given pair. Such a matching is called an odd matching. The graph T(F)=(V_F,F), where V_F is the set of edges of G occurring in at least one pair of F, is called the trace-graph of G and F.We motivate the introduction of the maximum weight odd-matching (abbreviated as Odd-MWM) problem and study its complexity with respect to two parameters: the type of graph G and the graph class T to which T(F) belongs.Our contribution includes:

•

A proof that Odd-MWM is NP-complete for 3-degree bipartite graphs when T(F) is a matching (i.e. when T is the class of 1-regular graphs), even if the weight function is constant.

•

A proof that Odd-MWM is NP-complete (for 3-degree bipartite graphs as well as for any larger class) if and only if T is a class of graphs with unbounded induced matching. Otherwise, Odd-MWM is polynomial.

•

A (Δ(T(F))+1)-approximate algorithm for Odd-MWM on general graphs. This algorithm becomes a χ(T(F))-approximate algorithm when the graph class T admits a polynomial algorithm for minimum vertex coloring.

     

Intersection cohomology of the circle actions

A classical result says that a free action of the circle S¹ on a topological space X is geometrically classified by the orbit space B and by a cohomological class e∈H²(B,Z), the Euler class. When the action is not free we have a difficult open question:

(Π)

“Is the space X determined by the orbit space B and the Euler class?”

The main result of this work is a step towards the understanding of the above question in the category of unfolded pseudomanifolds. We prove that the orbit space B and the Euler class determine:

•

the intersection cohomology of X,

•

the real homotopy type of X.

     

The signature operator at 2

It is well known that the signature operator on a manifold defines a K-homology class which is an orientation after inverting 2. Here we address the following puzzle: What is this class localized at 2, and what special properties does it have? Our answers include the following:

•

the K-homology class Δ_M of the signature operator is a bordism invariant;

•

the reduction mod 8 of the K-homology class of the signature operator is an oriented homotopy invariant;

•

the reduction mod 16 of the K-homology class of the signature operator is not an oriented homotopy invariant.

     

A Lagrangian heuristic algorithm for a real-world train timetabling problem

The train timetabling problem (TTP) aims at determining an optimal timetable for a set of trains which does not violate track capacities and satisfies some operational constraints.In this paper, we describe the design of a train timetabling system that takes into account several additional constraints that arise in real-world applications. In particular, we address the following issues:

•

Manual block signaling for managing a train on a track segment between two consecutive stations.

•

Station capacities, i.e., maximum number of trains that can be present in a station at the same time.

•

Prescribed timetable for a subset of the trains, which is imposed when some of the trains are already scheduled on the railway line and additional trains are to be inserted.

•

Maintenance operations that keep a track segment occupied for a given period.

We show how to incorporate these additional constraints into a mathematical model for a basic version of the problem, and into the resulting Lagrangian heuristic. Computational results on real-world instances from Rete Ferroviaria Italiana (RFI), the Italian railway infrastructure management company, are presented.     

Bounds on sets with few distances

We derive a new estimate of the size of finite sets of points in metric spaces with few distances. The following applications are considered:

•

we improve the Ray-Chaudhuri-Wilson bound of the size of uniform intersecting families of subsets;

•

we refine the bound of Delsarte-Goethals-Seidel on the maximum size of spherical sets with few distances;

•

we prove a new bound on codes with few distances in the Hamming space, improving an earlier result of Delsarte.

We also find the size of maximal binary codes and maximal constant-weight codes of small length with 2 and 3 distances.     

Galois representations modulo p and cohomology of Hilbert modular varieties

The aim of this paper is to extend some arithmetic results on elliptic modular forms to the case of Hilbert modular forms. Among these results let us mention:

•

control of the image of Galois representations modulo p,

•

Hida's congruence criterion outside an explicit set of primes,

•

freeness of the integral cohomology of a Hilbert modular variety over certain local components of the Hecke algebra and Gorenstein property of these local algebras.

We study the arithmetic properties of Hilbert modular forms by studying their modulo p Galois representations and our main tool is the action of inertia groups at primes above p. In order to determine this action, we compute the Hodge-Tate (resp. Fontaine-Laffaille) weights of the p-adic (resp. modulo p) étale cohomology of the Hilbert modular variety. The cohomological part of our paper is inspired by the work of Mokrane, Polo and Tilouine on the cohomology of Siegel modular varieties and builds upon geometric constructions of Tilouine and the author.     

On the OBDD size for graphs of bounded tree- and clique-width

We study the size of OBDDs (ordered binary decision diagrams) for representing the adjacency function f_G of a graph G on n vertices. Our results are as follows:

-

for graphs of bounded tree-width there is an OBDD of size O(logn) for f_G that uses encodings of size O(logn) for the vertices;

-

for graphs of bounded clique-width there is an OBDD of size O(n) for f_G that uses encodings of size O(n) for the vertices;

-

for graphs of bounded clique-width such that there is a clique-width expression for G whose associated binary tree is of depth O(logn) there is an OBDD of size O(n) for f_G that uses encodings of size O(logn) for the vertices;

-

for cographs, i.e. graphs of clique-width at most 2, there is an OBDD of size O(n) for f_G that uses encodings of size O(logn) for the vertices. This last result complements a recent result by Nunkesser and Woelfel [R. Nunkesser, P. Woelfel, Representation of graphs by OBDDs, in: X. Deng, D. Du (Eds.), Proceedings of ISAAC 2005, in: Lecture Notes in Computer Science, vol. 3827, Springer, 2005, pp. 1132-1142] as it reduces the size of the OBDD by an O(logn) factor using encodings whose size is increased by an O(1) factor.

     

Symbols of truncated Toeplitz operators

We consider three topics connected with coinvariant subspaces of the backward shift operator in Hardy spaces Hp:

-

properties of truncated Toeplitz operators;

-

Carleson-type embedding theorems for the coinvariant subspaces;

-

factorizations of pseudocontinuable functions from H¹.

These problems turn out to be closely connected and even, in a sense, equivalent. The new approach based on the factorizations allows us to answer a number of challenging questions about truncated Toeplitz operators posed by D. Sarason.     

Tournament immersion and cutwidth

A (loopless) digraph H is strongly immersed in a digraph G if the vertices of H are mapped to distinct vertices of G, and the edges of H are mapped to directed paths joining the corresponding pairs of vertices of G, in such a way that the paths used are pairwise edge-disjoint, and do not pass through vertices of G that are images of vertices of H. A digraph has cutwidth at most k if its vertices can be ordered {v₁,…,vn} in such a way that for each j, there are at most k edges uv such that u∈{v₁,…,vj−1} and v∈{vj,…,vn}.We prove that for every set S of tournaments, the following are equivalent:

•

there is a digraph H such that H cannot be strongly immersed in any member of S,

•

there exists k such that every member of S has cutwidth at most k,

•

there exists k such that every vertex of every member of S belongs to at most k edge-disjoint directed cycles.

This is a key lemma towards two results that will be presented in later papers: first, that strong immersion is a well-quasi-order for tournaments, and second, that there is a polynomial time algorithm for the k edge-disjoint directed paths problem (for fixed k) in a tournament.     

Finite Eulerian posets which are binomial, Sheffer or triangular

In this paper we study finite Eulerian posets which are binomial, Sheffer or triangular. These important classes of posets are related to the theory of generating functions and to geometry. The results of this paper are organized as follows:

•

We completely determine the structure of Eulerian binomial posets and, as a conclusion, we are able to classify factorial functions of Eulerian binomial posets.

•

We give an almost complete classification of factorial functions of Eulerian Sheffer posets by dividing the original question into several cases.

•

In most cases above, we completely determine the structure of Eulerian Sheffer posets, a result stronger than just classifying factorial functions of these Eulerian Sheffer posets.

We also study Eulerian triangular posets. This paper answers questions posed by R. Ehrenborg and M. Readdy. This research is also motivated by the work of R. Stanley about recognizing the boolean lattice by looking at smaller intervals.     

A new generation of applied probability textbooks

This article reviews the following books:

•

S. Asmussen, Applied Probability and Queues, second ed., Springer, Berlin, 2003, ISBN 0-387-00211-1, xii+438pp., EUR 85.55.

•

H. Chen, D. Yao, Fundamentals of Queueing Networks, Springer, Berlin, 2003, ISBN 0-387-95166-0, xviii+405pp., EUR 74,95.

•

W. Whitt, Stochastic-Process Limits, Springer, Berlin, 2002, ISBN 0-387-95358-2, xxiv+602pp., EUR 106,95.

     

The Mukai pairing—II: the Hochschild-Kostant-Rosenberg isomorphism

We continue the study of the Hochschild structure of a smooth space that we began in our previous paper, examining implications of the Hochschild-Kostant-Rosenberg theorem. The main contributions of the present paper are:

•

we introduce a generalization of the usual notions of Mukai vector and Mukai pairing on differential forms that applies to arbitrary manifolds;

•

we give a proof of the fact that the natural Chern character map K₀(X)→HH₀(X) becomes, after the HKR isomorphism, the usual one ; and

•

we present a conjecture that relates the Hochschild and harmonic structures of a smooth space, similar in spirit to the Tsygan formality conjecture.

     

Properties of four partial orders on standard Young tableaux

Let SYTn be the set of all standard Young tableaux with n cells. After recalling the definitions of four partial orders, the weak, KL, geometric and chain orders on SYTn and some of their crucial properties, we prove three main results:

•

Intervals in any of these four orders essentially describe the product in a Hopf algebra of tableaux defined by Poirier and Reutenauer.

•

The map sending a tableau to its descent set induces a homotopy equivalence of the proper parts of all of these orders on tableaux with that of the Boolean algebra ²[n−1]. In particular, the Möbius function of these orders on tableaux is (−1)ⁿ⁻³.

•

For two of the four orders, one can define a more general order on skew tableaux having fixed inner boundary, and similarly analyze their homotopy type and Möbius function.

     

Computing tight upper bounds on the algebraic connectivity of certain graphs

A generalized Bethe tree is a rooted unweighted tree in which vertices at the same level have the same degree. Let B be a generalized Bethe tree. The algebraic connectivity of:

the generalized Bethe tree B,

a tree obtained from the union of B and a tree T isomorphic to a subtree of B such that the root vertex of T is the root vertex of B,

a tree obtained from the union of r generalized Bethe trees joined at their respective root vertices,

a graph obtained from the cycle C_r by attaching B, by its root, to each vertex of the cycle, and

a tree obtained from the path P_r by attaching B, by its root, to each vertex of the path,

is the smallest eigenvalue of a special type of symmetric tridiagonal matrices. In this paper, we first derive a procedure to compute a tight upper bound on the smallest eigenvalue of this special type of matrices. Finally, we apply the procedure to obtain a tight upper bound on the algebraic connectivity of the above mentioned graphs.