An improved upper bound for Ramsey number N (3, 3, 3, 3; 2)

The Ramsey number N(3,3,3,3; 2) is the smallest integer n such that each 4-coloring by edges of the complete graph on n vertices contains monochromatic triangles. It is well known that 51 ≤ N(3, 3, 3, 3; 2) ≤ 65. Here we prove that N(3, 3, 3, 3; 2) ≤ 64.     

Shorter tours by nicer ears: 7/5-Approximation for the graph-TSP, 3/2 for the path version,and 4/3 for two-edge-connected subgraphs

We prove new results for approximating the graph-TSP and some related problems. We obtain polynomial-time algorithms with improved approximation guarantees. For the graph-TSP itself, we improve the approximation ratio to 7=5. For a generalization, the minimum T-tour problem, we obtain the first nontrivial approximation algorithm, with ratio 3=2. This contains the s-t-path graph-TSP as a special case. Our approximation guarantee for finding a smallest 2-edge-connected spanning subgraph is 4=3. The key new ingredient of all our algorithms is a special kind of ear-decomposition optimized using forest representations of hypergraphs. The same methods also provide the lower bounds (arising from LP relaxations) that we use to deduce the approximation ratios.     

Upper bounds for ramsey numbers R(3, 3, ⋖, 3) and Schur numbers

In this paper we show that for n ≥ 4, R(3, 3, ⋖, 3) < + 1. Consequently, a new bound for Schur numbers is also given. Also, for even n ≥ 6, the Schur number S_n is bounded by S_n < - n + 2. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 119–122, 1997     

Existence results for doubly near resolvable (υ, 3, 2)-BIBDs

Let V be a set of υ elements. A (1, 2; 3, υ, 1)-frame F is a square array of side v which satisfies the following properties. We index the rows and columns of F with the elements of V, V={x₁,x₂,…,x_υ}. (1) Each cell is either empty or contains a 3-subset of V. (2) Cell (x_i, x_i) is empty for i=1, 2,…, υ. (3) Row x_i of F contains each element of V−{x_i} once and column x_i of F contains each element of V−{x_i} once. (4) The collection of blocks obtained from the nonempty cells of F is a (υ, 3, 2)-BIBD. A (1, 2; 3, υ, 1)-frame is a doubly near resolvable (υ, 3, 2)-BIBD. In this paper, we first present a survey of existence results on doubly near resolvable (υ, 3, 2)-BIBDs and (1, 2; 3, υ, 1)-frames. We then use frame constructions to provide a new infinite class of doubly near resolvable (υ, 3, 2)-BIBDs by constructing (1, 2; 3, υ, 1)-frames.     

Characters,genericity, and multiplicity one for U(3)

Let ψ:U→ℂ be a generic character of the unipotent radicalU of a Borel subgroup of a quasisplitp-adic groupG. The number (0 or 1) of ψ-Whittaker models on an admissible irreducible representation π ofG was expressed by Rodier in terms of the limit of values of the trace of π at certain measures concentrated near the origin. An analogous statement holds in the twisted case. This twisted analogue is used in [F, p. 47] to provide a local proof of the multiplicity one theorem for U(3). This assert that each discrete spectrum automorphic representation of the quasisplit unitary group U(3) associated with a quadratic extensionE/F of number fields occurs in the discrete spectrum with multiplicity one. It is pointed out in [F, p. 47] that a proof of the twisted analogue of Rodier's theorem does not appear in print. It is then given below. Detailing this proof is necessitated in particular by the fact that the attempt in [F, p. 48] at a global proof of the multiplicity one theorem for U(3), although widely quoted, is incomplete, as we point out here. Partially supported by a Lady Davis Visiting Professorship at the Hebrew University and the Max-Planck-Institut für Mathematik, Bonn.     

COSET DIAGRAMS FOR A HOMOMORPHIC IMAGE OF △（3, 3, k）

Let q be a prime power. By PL（Fq） the authors mean a projective line over the finite field Fq with the additional point ∞. In this article, the authors parametrize the conjugacy classes of nondegenerate homomorphisms which represent actions of △（3, 3, k） = （u, v： u^3 = v^3 = （uv）^k = 1〉on PL（Fq）, where q ≡ ±1（modk）. Also, for various values of k, they find the conditions for the existence of coset diagrams depicting the permutation actions of △（3, 3, k） on PL（Fq）. The conditions are polynomials with integer coefficients and the diagrams are such that every vertex in them is fixed by （u^-v^-）^k. In this way, they get △（3, 3, k） as permutation groups on PL（Fq）.     

Incidence-polytopes of type {6, 3, 3}

From the hyperbolic honeycomb {6, 3, 3} we derive a class of abstract polytopes whose cells are isomorphic to the toroidal maps {6, 3} _b,c and vertex figures to tetrahedra. We give a criterion on the finiteness of these incidence-polytopes in terms of the group PSL ^± (2, []), leading, among other things, to the explicit recognition of the groups in some interesting special cases.Research supported by NSERC Canada Grant A8857.     

Root Configurations for Hyperbolic Polynomials of Degree 3, 4, and 5

A real polynomial of one real variable is (strictly) hyperbolic if it has only real (and distinct) roots. There are 10 (resp. 116) possible non-degenerate configurations between the roots of a strictly hyperbolic polynomial of degree 4 (resp. 5) and of its derivatives (i.e., configurations without equalities between roots). The standard Rolle theorem allows 12 (resp. 286) such configurations. The result is based on the study of the hyperbolicity domain of the family P(x,a)=x ⁿ+a ₁ x ^n-1+...+a _n for n=4,5 (i.e., of the set of values of aⁿ for which the polynomial is hyperbolic) and its stratification defined by the discriminant sets Res(P ⁽ⁱ⁾,P ^(j))=0, 0 i < jn-1.     

Synthesis of 3 : 4 dihydro 2H-pyrano (2, 3-b) quinolines

The synthesis of 3 : 4 dihydro 2H-pyrano(2, 3-b) quinolines is described.     

An upper bound for the Folkman number F(3, 3; 5)

Let F(p, q; r) denote the minimum number of vertices in a graph G that has the properties (1) G contains no complete subgraph on r vertices, and (2) any green-red coloring of the edges of G yields a green complete subgraph on p vertices or a red complete subgraph on q vertices. Folkman proved the existence of F(p, q; r) whenever r > max {p, q}. We show F(3, 3; 5) ≤ 17, improving a bound due to Irving and an earlier bound due to Graham and Spencer. © 1993 John Wiley & Sons, Inc.