The graphical relaxation: A new framework for the symmetric traveling salesman polytope

A present trend in the study of theSymmetric Traveling Salesman Polytope (STSP(n)) is to use, as a relaxation of the polytope, thegraphical relaxation (GTSP(n)) rather than the traditionalmonotone relaxation which seems to have attained its limits. In this paper, we show the very close relationship between STSP(n) and GTSP(n). In particular, we prove that every non-trivial facet of STSP(n) is the intersection ofn + 1 facets of GTSP(n),n of which are defined by the degree inequalities. This fact permits us to define a standard form for the facet-defining inequalities for STSP(n), that we calltight triangular, and to devise a proof technique that can be used to show that many known facet-defining inequalities for GTSP(n) define also facets of STSP(n). In addition, we give conditions that permit to obtain facet-defining inequalities by composition of facet-defining inequalities for STSP(n) and general lifting theorems to derive facet-defining inequalities for STSP(n +k) from inequalities defining facets of STSP(n).Partially financed by P.R.C. Mathématique et Informatique.     

-Operator frames for a Banach space

In this paper, (p,Y)-Bessel operator sequences, operator frames and (p,Y)-Riesz bases for a Banach space X are introduced and discussed as generalizations of the usual concepts for a Hilbert space and of the g-frames. It is proved that the set of all (p,Y)-Bessel operator sequences for a Banach space X is a Banach space and isometrically isomorphic to the operator space B(X,ℓ^p(Y)). Some necessary and sufficient conditions for a sequence of operators to be a (p,Y)-Bessel operator sequence are given. Also, a characterization of an independent (p,Y)-operator frame for X is obtained. Lastly, it is shown that an independent (p,Y)-operator frame for X is just a (p,Y)-Riesz basis for X and has a unique dual (q,Y^*)-operator frame for X^*.     

A remark on local-global principles for conjugacy classes

A local-global principle is shown to hold for all conjugacy classes of any inner form of GL(n), SL(n), U(n), SU(n), and for all semisimple conjugacy classes in any inner form of Sp(n), over fieldsk with vcd(k)≤1. Over number fields such a principle is known to hold for any inner form of GL(n) and U(n), and for the split forms of Sp(n), O(n), as well as for SL(p) but not for SL(n),n non-prime. The principle holds for all conjugacy classes in any inner form of GL(n), but not even for semisimple conjugacy classes in Sp(n), over fieldsk with vcd(k)≤2. The principle for conjugacy classes is related to that for centralizers.     

k-Bounded classes of dominant-independent perfect graphs

Let α(G), γ(G), and i(G) be the independence number, the domination number, and the independent domination number of a graph G, respectively. For any k ≥ 0, we define the following hereditary classes: αi(k) = {G : α(H) − i(H) ≤ k for every H ∈ ISub(G)}; αγ(k) = {G : α(H) − γ(H) ≤ k for every H ∈ ISub(G)}; and iγ(k) = {G : i(H) − γ(H) ≤ k for every H ∈ ISub(G)}, where ISub(G) is the set of all induced subgraphs of a graph G. In this article, we present a finite forbidden induced subgraph characterization for αi(k) and αγ(k) for any k ≥ 0. We conjecture that iγ(k) also has such a characterization. Up to the present, it is known only for iγ(0) (domination perfect graphs [Zverovich & Zverovich, J Graph Theory 20 (1995), 375–395]). © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 303–310, 1999     

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 (<Emphasis Type="Italic">n</Emphasis>,<Emphasis Type="Italic">m</Emphasis>)-semigroups

We generalize Green’s lemma and Green’s theorem for usual binary semigroups to (n,m)-semigroups, define and describe the regularity for an element of an (n,m)-semigroup, give some criteria for an element of an (n,m)-semigroup to be invertible, and further apply the invertibility for (n,m)-semigroups to (n,m)-groups and give some equivalent characterizations for (n,m)-groups. We establish Hosszú-Gluskin theorems for (n,m)-semigroups in two cases, as generalizations of the corresponding theorems for n-groups.     

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.     

On the maximum number of fixed points in automorphisms of prime order of 2-(v,k,1) designs

In this paper, we study 2-(v, k, 1) designs with automorphisms of prime orderp, having the maximum possible number of fixed points. We prove an upper bound on the number of fixed points, and we study the structure of designs in which this bound is met with equality (such a design is called ap-MFP(v, k)). Several characterizations and asymptotic existence results forp-MFP(v, k) are obtained. For (p, k)=(3,3), (5,5), (2,3) and (3,4), necessary and sufficient conditions onv are obtained for the existence of ap-MFP(v, k). Further, for 3≤k≤5 and for any primep≡1 modk(k−1), we establish necessary and sufficient conditions onv for the existence of ap-MFP(v, k).     

Generalized steiner triple systems with group size five

Generalized Steiner triple systems, GS(2, 3, n, g) are used to construct maximum constant weight codes over an alphabet of size g+1 with distance 3 and weight 3 in which each codeword has length n. The existence of GS(2, 3, n, g) has been solved for g=2, 3, 4, 9. In this paper, by introducing a special kind of holey generalized Steiner triple systems (denoted by HGS(2, 3, (n, u), g)), singular indirect product (SIP) construction for GDDs is used to construct generalized Steiner systems. The numerical necessary conditions for the existence of a GS(2, 3, n, g) are shown to be sufficient for g=5.     

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.     

Smallest maximally nonhamiltonian graphs II

Bollobás posed the problem of finding the least number of edges,f(n), in a maximally nonhamiltonian graph of ordern. Clark and Entringer showedf(n)=3n/2 for all evenn≥36 andf(n)=(3n+1)/2 or (3n+3)/2 for all oddn≥55. We showf(n)=(3n+1)/2 for all oddn≥53.     

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.     

Cohomological Characterizations of Biprojective and Biflat Banach Algebras

 Let A be a biprojective Banach algebra, and let A-mod-A be the category of Banach A-bimodules. In this paper, for every given -mod-A, we compute all the cohomology groups . Furthermore, we give some cohomological characterizations of biprojective Banach algebras. In particular, we show that the following properties of a Banach algebra A are equivalent to its biprojectivity: (i) for all -mod -A; (ii) for all -mod-A; (iii) for all -mod-A. (Here and are, respectively, the Banach A-bimodules of left, right and double multipliers of X.) Further, if A is a biflat Banach algebra and -mod-A, we compute all the cohomology groups , where is the Banach A-bimodule dual to X. Also, we give cohomological characterizations of biflat Banach algebras. We prove that a Banach algebra A is biflat if and only if any of the following conditions is valid: (i’) for all -mod-A; (ii’) for all -mod-A; (iii’) for all -mod-A.     

Integrodifferential systems with infinitely many delays

Summary In this paper we consider the initial-value problems: (P ₁ )X(t)=(AX)(t) for t>0, X(0+)=I, X(t)=0 for t<0 and (P ₂ ) Y(t)=(QY)(t) for t>0, Y(0+)=I, Y(t)=0 for t<0, where A and Q are linear specified operators, I and0 — the identity and null matrices of order n, and X(t), Y(t) are unknown functions whose values are square matrices of order n. Sufficient conditions are established under which the problems (P ₁ ) and (P ₂ ) have the same unique solution, locally summable on the half-axis t ⩾0. Using this fact and some properties of the Laplace transform we find a new proof for the variation of constants formula given in[1, 2]. On the basis of this formula we derive certain results concerning a class of integrodifferential systems with infinite delay. Entrata in Redazione il 2 marzo 1977.     

Some New Results on Circulant Weighing Matrices

We obtain a few structural theorems for circulant weighing matrices whose weight is the square of a prime number. Our results provide new schemes to search for these objects. We also establish the existence status of several previously open cases of circulant weighing matrices. More specifically we show their nonexistence for the parameter pairs (n, k) (here n is the order of the matrix and k its weight) = (147, 49), (125, 25), (200, 25), (55, 25), (95, 25), (133, 49), (195, 25), (11 w, 121) for w < 62.     

Linear and 2-Frugal Choosability of Graphs of Small Maximum Average Degree

A proper vertex colouring of a graph G is 2-frugal (resp. linear) if the graph induced by the vertices of any two colour classes is of maximum degree 2 (resp. is a forest of paths). A graph G is 2-frugally (resp. linearly) L-colourable if for a given list assignment L:V(G)? 2^{\mathbb N}{L:V(G)\mapsto 2^{\mathbb N}} , there exists a 2-frugal (resp. linear) colouring c of G such that c(v) ? L(v){c(v) \in L(v)} for all v ? V(G){v\in V(G)} . If G is 2-frugally (resp. linearly) L-list colourable for any list assignment such that |L(v)| ≥ k for all v ? V(G){v\in V(G)}, then G is 2-frugally (resp. linearly) k-choosable. In this paper, we improve some bounds on the 2-frugal choosability and linear choosability of graphs with small maximum average degree.     

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.     

On c‐Bhaskar Rao designs with block size 4

Several new families of c‐Bhaskar Rao designs with block size 4 are constructed. The necessary conditions for the existence of a c‐BRD (υ,4,λ) are that: (1)λ_min=?λ/3 ≤ c ≤ λ and (2a) c≡λ (mod 2), if υ > 4 or (2b) c≡ λ (mod 4), if υ = 4 or (2c) c≠ λ ? 2, if υ = 5. It is proved that these conditions are necessary, and are sufficient for most pairs of c and λ; in particular, they are sufficient whenever λ?c ≠ 2 for c > 0 and whenever c ? λ_min≠ 2 for c < 0. For c < 0, the necessary conditions are sufficient for υ> 101; for the classic Bhaskar Rao designs, i.e., c = 0, we show the necessary conditions are sufficient with the possible exception of 0‐BRD (υ,4,2)'s for υ≡ 4 (mod 6). © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 361–386, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10009     

The General Solution of Ming Antu＇s Problem

In two centuries ago,Ming Autu discovered the famous Catalan numbers while he tried to expand the function sin(2px) as power series of sin(x) for the case p=1,2,3.Very recently,P.J.Larcombe shows that for any p,sin(2px) can always be expressed as an infinite power series of sin(x) involving precise combinations of Catalan numbers as part of all but the initial p terms and gave all expansions for the case p=4,5.The present paper presents the desired expansion for arbitrary integer p.