Connections for small vertex models

This paper is a first attempt at classifying connections on small vertex models i.e., commuting squares of the form displayed in (1.2) below. More precisely, if we letB(k,n) denote the collection of matricesW for which (1.2) is a commuting square then, we: (i) obtain a simple model form for a representative from each equivalence class inB(2,n), (ii) obtain necessary conditions for two such ‘model connections’ inB(2,n) to be themselves equivalent, (iii) show thatB(2,n) contains a (3n - 6)-parameter family of pairwise inequivalent connections, and (iv) show that the number (3n - 6) is sharp. Finally, we deduce that every graph that can arise as the principal graph of a finite depth subfactor of index 4 actually arises for one arising from a vertex model corresponding toB(2,n) for somen.     

Spectra of Some Interesting Combinatorial Matrices Related to Oriented Spanning Trees on a Directed Graph

The Laplacian of a directed graph G is the matrix L(G) = O(G) –, A(G) where A(G) is the adjaceney matrix of G and O(G) the diagonal matrix of vertex outdegrees. The eigenvalues of G are the eigenvalues of A(G). Given a directed graph G we construct a derived directed graph D(G) whose vertices are the oriented spanning trees of G. Using a counting argument, we describe the eigenvalues of D(G) and their multiplicities in terms of the eigenvalues of the induced subgraphs and the Laplacian matrix of G. Finally we compute the eigenvalues of D(G) for some specific directed graphs G. A recent conjecture of Propp for D(H _n ) follows, where H _n stands for the complete directed graph on n vertices without loops.     

Banach-stone theorems and separating maps

LetC(X,E) andC(Y,F) denote the spaces of continuous functions on the Tihonov spacesX andY, taking values in the Banach spacesE andF, respectively. A linear mapH:C(X,E)→C(Y,F) isseparating iff(x)g(x)=0 for allx inX impliesHf(y)Hg(y)=0 for ally inY. Some automatic continuity properties and Banach-Stone type theorems (i.e., asserting that isometries must be of a certain form) for separating mapsH between spaces of real- and complex-valued functions have already been developed. The extension of such results to spaces of vector-valued functions is the general subject of this paper. We prove in Theorem 4.1, for example, for compactX andY, that a linear isometryH betweenC(X,E) andC(Y,F) is a “Banach-Stone” map if and only ifH is “biseparating (i.e,H andH ⁻¹ are separating). The Banach-Stone theorems of Jerison and Lau for vector-valued functions are then deduced in Corollaries 4.3 and 4.4 for the cases whenE andF or their topological duals, respectively, are strictly convex. Research supported by the Fundació Caixa Castelló, MI/25.043/92     

On cardinality bounds involving the weak Lindelöf degree

We give a general closing-off argument in Theorem 2.3 from which several corollaries follow, including (1) if X is a locally compact Hausdorff space then |X| ≤ 2^wL(X)ψ(X), and (2) if X is a locally compact power homogeneous Hausdorff space then |X| ≤ 2^wL(X)t(X). The first extends the well-known cardinality bound 2^ψ(X) for a compactum X in a new direction. As |X| ≤ 2^wL(X)χ(X) for a normal spaceX[4], this enlarges the class of known Tychonoff spaces for which this bound holds. In 2.12 we give a short, direct proof of (1) that does not use 2.3. Yet 2.3 is broad enough to establish results much more general than (1), such as if X is a regular space with a π-base ? such that |B| ≤ 2^wL(X)χ(X) for all B ∈ ?, then |X| ≤ 2^wL(X)χ(X).

Separately, it is shown that if X is a regular space with a π-base whose elements have compact closure, then |X| ≤ 2^{wL(X)ψ(X)t(X)}. This partially answers a question from [4] and gives a third, separate proof of (1). We also show that if X is a weakly Lindelöf, normal, sequential space with χ(X) ≤ 2^?0, then |X| ≤ 2^?0.

Result (2) above is a new generalization of the cardinality bound 2^t(X) for a power homogeneous compactum X (Arhangel'skii, van Mill, and Ridderbos [3], De la Vega in the homogeneous case [10]). To this end we show that if U ? clD ? X, where X is power homogeneous and U is open, then |U| ≤ |D|^πχ(X). This is a strengthening of a result of Ridderbos [19].     

Corrigendum to “Discrepancy principle for the dynamical systems method” [Communications in Nonlinear Science and Numerical Simulation 10 (2005) 95–101]

Consider an operator equation B(u) − f = 0 in a real Hilbert space. Let us call this equation ill-posed if the operator B′(u) is not boundedly invertible, and well-posed otherwise. The dynamical systems method (DSM) for solving this equation consists of a construction of a Cauchy problem, which has the following properties: (1) it has a global solution for an arbitrary initial data, (2) this solution tends to a limit as time tends to infinity, (3) the limit is the minimal-norm solution to the equation B(u) = f. A global convergence theorem is proved for DSM for equation B(u) − f = 0 with monotone operators B.     

Function Spaces and Continuous Algebraic Pairings for Varieties

Given a quasi-projective complex variety X and a projective variety Y, one may endow the set of morphisms, Mor(X, Y), from X to Y with the natural structure of a topological space. We introduce a convenient technique (namely, the notion of a functor on the category of 'smooth curves') for studying these function complexes and for forming continuous pairings of such. Building on this technique, we establish several results, including (1) the existence of cap and join product pairings in topological cycle theory; (2) the agreement of cup product and intersection product for topological cycle theory; (3) the agreement of the motivic cohomology cup product with morphic cohomology cup product; and (4) the Whitney sum formula for the Chern classes in morphic cohomology of vector bundles.     

<Emphasis Type="Italic">X</Emphasis>-Trees and Weighted Quartet Systems

In this note, we consider a finite set X and maps W from the set $ \mathcal{S}_{2|2} (X) $ of all 2, 2- splits of X into $ \mathbb{R}_{\geq 0} $. We show that such a map W is induced, in a canonical way, by a binary X-tree for which a positive length $ \mathcal{l} (e) $ is associated to every inner edge e if and only if (i) exactly two of the three numbers W(ab|cd),W(ac|bd), and W(ad|cb) vanish, for any four distinct elements a, b, c, d in X, (ii) $ a \neq d \quad\mathrm{and}\quad W (ab|xc) + W(ax|cd) = W(ab|cd) $ holds for all a, b, c, d, x in X with #{a, b, c, x} = #{b, c, d, x} = 4 and $ W(ab|cx),W(ax|cd) $ > 0, and (iii) $ W (ab|uv) \geq \quad \mathrm{min} (W(ab|uw), W(ab|vw)) $ holds for any five distinct elements a, b, u, v, w in X. Possible generalizations regarding arbitrary $ \mathbb{R} $-trees and applications regarding tree-reconstruction algorithms are indicated.AMS Subject Classification: 05C05, 92D15, 92B05.     

Ridged Domains,Embedding Theorems and Poincaré Inequalities

We study the embeddings E : W(X(Ω), Y(Ω)) ↪ Z(Ω), where X(Ω), Y(Ω) and Z(Ω) are rearrangement–invariant Banach function spaces (BFS) defined on a generalized ridged domain Ω, and W denotes a first–order Sobolev–type space. We obtain two–sided estimates for the measure of non–compactness of E when Z(Ω) = X(Ω) and, in turn, necessary and sufficient conditions for a Poincaré–type inequality to be valid and also for E to be compact. The results are used to analyse the example of a trumpet–shaped domain Ω in Lorentz spaces. We consider the problem of determining the range of possible target spaces Z(Ω), in which case we prove that the problem is equivalent to an analogue on the generalized ridge Γ of Ω. The range of target spaces Z(Ω) is determined amongst a scale of (weighted) Lebesgue spaces for “rooms and passages” and trumpet–shaped domains.     

Two remarks on continuation procedures for solving some nonlinear equations

Let F be a mapping from R ⁿ⁺¹ into R ⁿ, x(t) be a parametrization for ∣t ? t₀ ∣ < c, of a smooth solution branch of the equation F(x) = 0, A(t) be the jacobian (n + 1) associated to a standard continuation method used for computing the solution branch. We study for a class of singularities at x(t₀) the behaviour, near t = t₀, of the determinant of A(t).     

Generalized mixed integer rounding inequalities: facets for infinite group polyhedra

We present a generalization of the mixed integer rounding (MIR) approach for generating valid inequalities for (mixed) integer programming (MIP) problems. For any positive integer n, we develop n facets for a certain (n + 1)-dimensional single-constraint polyhedron in a sequential manner. We then show that for any n, the last of these facets (which we call the n-step MIR facet) can be used to generate a family of valid inequalities for the feasible set of a general (mixed) IP constraint, which we refer to as the n-step MIR inequalities. The Gomory Mixed Integer Cut and the 2-step MIR inequality of Dash and günlük  (Math Program 105(1):29–53, 2006) are the first two families corresponding to n = 1,2, respectively. The n-step MIR inequalities are easily produced using periodic functions which we refer to as the n-step MIR functions. None of these functions dominates the other on its whole period. Finally, we prove that the n-step MIR inequalities generate two-slope facets for the infinite group polyhedra, and hence are potentially strong.      

Elliptic curves and their torsion subgroups over number fields of type (2, 2, ..., 2)

Suppose thatE: y ² =x(x + M) (x + N) is an elliptic curve, whereM N are rational numbers (#0, ±1), and are relatively prime. LetK be a number field of type (2,...,2) with degree 2′. For arbitrary n, the structure of the torsion subgroup E(K) _tors of theK-rational points (Mordell group) ofE is completely determined here. Explicitly given are the classification, criteria and parameterization, as well as the groups E(K) _tors themselves. The order of E( K)_tors is also proved to be a power of 2 for anyn. Besides, for any elliptic curveE over any number field F, it is shown that E( L)_tors = E( F) _tors holds for almost all extensionsL/F of degree p(a prime number). These results have remarkably developed the recent results by Kwon about torsion subgroups over quadratic fields.     

Characterizing maximal compact subgroups

We prove that for a compact subgroup H of a locally compact almost connected group G, the following properties are mutually equivalent: (1) H is a maximal compact subgroup of G, (2) the coset space G/H is \mathbbQ{\mathbb{Q}} -acyclic and \mathbbZ/2\mathbbZ{\mathbb{Z}/2\mathbb{Z}} -acyclic in Čech cohomology, (3) G/H is contractible, (4) G/H is homeomorphic to a Euclidean space, (5) G/H is an absolute extensor for paracompact spaces, (6) G/H is a G-equivariant absolute extensor for paracompact proper G-spaces having a paracompact orbit space.     

On graphs containing a given graph as center

We examine the problem of embedding a graph H as the center of a supergraph G, and we consider what properties one can restrict G to have. Letting A(H) denote the smallest difference ∣V(G)∣ - ∣V(H)∣ over graphs G having center isomorphic to H it is demonstrated that A(H) ≤ 4 for all H, and for 0 ≤ i ≤ 4 we characterize the class of trees T with A(T) = i. for n ≥ 2 and any graph H, we demonstrate a graph G with point and edge connectivity equal to n, with chromatic number X(G) = n + X(H), and whose center is isomorphic to H. Finally, if ∣V(H)∣ ≥ 9 and k ≥ ∣V(H)∣ + 1, then for n sufficiently large (with n even when k is odd) we can construct a k-regular graph on n vertices whose center is isomorphic to H.     

Primitive lattice points inside an ellipse

Let Q(u, v) be a positive definite binary quadratic form with arbitrary real coefficients. For large real x, one may ask for the number B(x) of primitive lattice points (integer points (m, n) with gcd(M, n) = 1) in the ellipse disc Q(u, v) x, in particular, for the remainder term R(x) in the asymptotics for B(x). While upper bounds for R(x) depend on zero-free regions of the zeta-function, and thus, in most published results, on the Riemann Hypothesis, the present paper deals with a lower estimate. It is proved that the absolute value or R(x) is, in integral mean, at least a positive constant c time x ^1/4. Furthermore, it is shown how to find an explicit value for c, for each specific given form Q.To Professor Ekkehard Kratzel on his 70th birthday     

Kostant's problem,Goldie rank and the Gelfand-Kirillov conjecture

Let g be a complex semisimple Lie algebra andU(g) its enveloping algebra. GivenM a simpleU(g) module, letL(M, M) denote the subspace of ad g finite elements of Hom(M, M). Kostant has asked if the natural homomorphism ofU(g) intoL(M, M) is surjective. Here the question is analysed for simple modules with a highest weight vector. This has a negative answer if g admits roots of different length ([7], 6.5). Here general conditions are obtained under whichU(g)/AnnM andL(M, M) have the same ring of fractions—in particular this is shown to always hold if g has only typeA _n factors. Combined with [21], this provides a method for determining the Goldie ranks for the primitive quotients ofU(g). Their precise form is given in typeA _n (Cartan notation) for which the generalized Gelfand-Kirillov conjecture for primitive quotients is also established.This paper was written while the author was a guest of the Institute for Advanced Studies, the Hebrew University of Jerusalem and on leave of absence from the Centre Nationale de la Recherche Scientifique     

On the Interval Number of a Triangulated Graph

The interval number of a simple undirected graph G, denoted i(G), is the least nonnegative integer r for which we can assign to each vertex in G a collection of at most r intervals on the real line such that two distinct vertices v and w of G are adjacent if and only if some interval for v intersects some interval for w. For triangulated graphs G, we consider the problem of finding a sharp upper bound for the interval number of G in terms of its clique number ω(G). The following partial results are proved. (1) For each triangulated graph G, i(G) ? ?ω(G)/2? + 1, and this is best possible for 2 ? ω(G) ? 6. (2) For each integer m ? 2, there exists a triangulated graph G with ω(G) = m and i(G) > m^1/2.     

A polynomial algorithm for finding (<Emphasis Type="Italic">g,f</Emphasis>)-colorings orthogonal to stars in bipartite graphs

Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two nonnegative integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). A (g, f)-coloring of G is a generalized edge-coloring in which each color appears at each vertex x at least g(x) and at most f(x) times. In this paper a polynomial algorithm to find a (g, f)-coloring of a bipartite graph with some constraints using the minimum number of colors is given. Furthermore, we show that the results in this paper are best possible.     

Reconstructing the number of copies of a valency-labeled finite graph in an infinite graph

Suppose that G, H are infinite graphs and there is a bijection Ψ; V(G) Ψ V(H) such that G - ξ ? H - Ψ(ξ) for every ξ ～ V(G). Let J be a finite graph and /(π) be a cardinal number for each π ? V(J). Suppose also that either /(π) is infinite for every π ? V(J) or J has a connected subgraph C such that /(π) is finite for every π ? V(C) and every vertex in V(J)/V(C) is adjacent to a vertex of C. Let (J, I, G) be the set of those subgraphs of G that are isomorphic to J under isomorphisms that map each vertex π of J to a vertex whose valency in G is /(π). We prove that the sets (J, I, G), m(J, I, H) have the same cardinality and include equal numbers of induced subgraphs of G, H respectively.     

Sufficient Condition to Resolve Costa's First Conjecture

In this work, we give a sufficient condition to resolve Costa's first conjecture for each positive integer n and d with n ≥ 4. Precisely, we show that if there exists a local ring (A, M) such that λ _A (M) = n, and if there exists an (n + 2)-presented A-submodule of M ^m , where m is a positive integer (for instance, if M contains a regular element), then we may construct an example of (n + 4, d)-ring which is neither an (n + 3, d)-ring nor an (n + 4, d ? 1)-ring. Finally, we construct a local ring (B, M) such that λ _B (M) = 0 (resp., λ _B (M) = 1) and so we exhibit for each positive integer d, an example of a (4, d)-ring (resp., (5, d)-ring) which is neither a (4, d ? 1)-ring (resp., neither a (5, d ? 1)-ring) nor a (2, d′)-ring (resp., nor a (3, d′)-ring) for each positive integer d′.     

On Random Sections of the Cube

Let f(j,k,n) denote the expected number of j -faces of a random k -section of the n -cube. A formula for f(0,k,n) is presented, and, for j\geq 1 , a lower bound for f(j,k,n) is derived, which implies a precise asymptotic formula for f(n-m,n-l,n) when 1≤ l<m are fixed integers and n→∈fty . Received August 1, 1998, and in revised form December 15, 1998.