Partition of <Emphasis Type="Italic">C</Emphasis><Subscript>4</Subscript>-Designs into Minimum and Maximum Number of <Emphasis Type="Italic">P</Emphasis><Subscript>3</Subscript>-Designs

Let be a C₄-design of order n and index , on the vertex set V, |V|=n. If V₁V_m=V is a partition of the vertex set, such that the intersections of the with V_i form a P₃-design of order |V_i| and the same index , for each 1im, then 2m log₃(2n+1). The minimum bound is best possible for every . The maximum bound is best possible for =2, and hence also for every even .Supported by MIUR, Italy and CNR-GNSAGAAlso affiliated with the Department of Computer Science, University of Veszprém, Hungary; supported in part by the Hungarian Scientific Research Fund, grant OTKA T-32969AMS classification: 05B05     

On hamiltonicity of <Emphasis Type="Italic">P</Emphasis><Subscript>3</Subscript>-dominated graphs

We introduce a new class of graphs which we call P ₃-dominated graphs. This class properly contains all quasi-claw-free graphs, and hence all claw-free graphs. Let G be a 2-connected P ₃-dominated graph. We prove that G is hamiltonian if α(G ²) ≤ κ(G), with two exceptions: K _2,3 and K _1,1,3. We also prove that G is hamiltonian, if G is 3-connected and |V(G)| ≤ 5δ(G) − 5. These results extend known results on (quasi-)claw-free graphs. This paper was completed when both authors visited the Center for Combinatorics, Nankai University, Tianjin. They gratefully acknowledge the hospitality and support of the Center for Combinatorics and Nankai University. The work of E.Vumar is sponsored by SRF for ROCS, REM.     

Automorphisms of Coxeter groups of type <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

A Coxeter system (W, S) is said to be of type K _n if the associated Coxeter graph Γ_S is complete on n vertices and has only odd edge labels. If W satisfies either of: (1) n = 3; (2) W is rigid; then the automorphism group of W is generated by the inner automorphisms of W and any automorphisms induced by Γ_S. Indeed, Aut(W) is the semidirect product of Inn(W) and the group of diagram automorphisms, and furthermore W is strongly rigid. We also show that if W is a Coxeter group of type K _n then W has exactly one conjugacy class of involutions and hence Aut(W) = Spec(W).     

New characterization of <Emphasis Type="Italic">S</Emphasis><Subscript>4</Subscript>(<Emphasis Type="Italic">q</Emphasis>) by its noncommuting graph

Let G be a nonabelian group, and associate the noncommuting graph ?(G) with G as follows: the vertex set of ?(G) is G\Z(G) with two vertices x and y joined by an edge whenever the commutator of x and y is not the identity. Let S ₄(q) be the projective symplectic simple group, where q is a prime power. We prove that if G is a group with ?(G) ? ?(S ₄(q)) then G ? S ₄(q).     

On the Chromatic Number of the Square of the Kneser Graph <Emphasis Type="Italic">K</Emphasis>(2<Emphasis Type="Italic">k</Emphasis>+1, <Emphasis Type="Italic">k</Emphasis>)

The Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of an n-element set, with two vertices adjacent if the sets are disjoint. The chromatic number of the Kneser graph K(n, k) is n–2k+2. Zoltán Füredi raised the question of determining the chromatic number of the square of the Kneser graph, where the square of a graph is the graph obtained by adding edges joining vertices at distance at most 2. We prove that (K²(2k+1, k))4k when k is odd and (K²(2k+1, k))4k+2 when k is even. Also, we use intersecting families of sets to prove lower bounds on (K²(2k+1, k)), and we find the exact maximum size of an intersecting family of 4-sets in a 9-element set such that no two members of the family share three elements.This work was partially supported by NSF grant DMS-0099608Final version received: April 23, 2003     

On the Theory of <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>(<Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">q</Emphasis></Subscript>)-Banach Lattices

Given 1≤ p,q < ∞, let BL_pL_q be the class of all Banach lattices X such that X is isometrically lattice isomorphic to a band in some L_p(L_q)-Banach lattice. We show that the range of a positive contractive projection on any BL_pL_q-Banach lattice is itself in BL_pL_q. It is a consequence of this theorem and previous results that BL_pL_q is first-order axiomatizable in the language of Banach lattices. By studying the pavings of arbitrary BL_pL_q-Banach lattices by finite dimensional sublattices that are themselves in this class, we give an explicit set of axioms for BL_pL_q. We also consider the class of all sublattices of L_p(L_q)-Banach lattices; for this class (when p/q is not an integer) we give a set of axioms that are similar to Krivine’s well-known axioms for the subspaces of L_p-Banach spaces (when p/2 is not an integer). We also extend this result to the limiting case q = ∞.     

3-Connected {<Emphasis Type="Italic">K</Emphasis><Subscript>1,3</Subscript>, <Emphasis Type="Italic">P</Emphasis><Subscript>9</Subscript>}-Free Graphs are Hamiltonian-Connected

We investigate pairs of forbidden subgraphs that imply a 3-connected graph is Hamiltonian-connected. In particular we show that the pair {K _1,3, P ₉} is such a pair. As it is known that P ₁₀ cannot replace P ₉, this result is best possible. Further, we show that certain other graphs are not possible.     

Paired-Domination in <Emphasis Type="Italic">P</Emphasis><Subscript>5</Subscript>-Free Graphs

A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired-domination number of G, denoted by , is the minimum cardinality of a paired-dominating set of G. In [1], the authors gave tight bounds for paired-dominating sets of generalized claw-free graphs. Yet, the critical cases are not claws but subdivided stars. We here give a bound for graphs containing no induced P ₅, which seems to be the critical case.     

A Characterization of PSL(3, <Emphasis Type="Italic">q</Emphasis>) for <Emphasis Type="Italic">q</Emphasis>=2<Superscript><Emphasis Type="Italic">m</Emphasis></Superscript>

The order components of a finite group are introduced in [12]. In [9], it is proved that the group PSL(3,q), where q is an odd prime power, is uniquely determined by its order components. In this paper, we show that the group PSL(3, q), where q=2 ^m , is also uniquely determined by its order components. Received December 15, 2000, Revised August 15, 2001, Accepted November 13, 2001     

Continuous <Emphasis Type="Italic">l</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis>,<Emphasis Type="Italic">p</Emphasis></Subscript>-symmetric distributions

For p > 0, the l _n,p -generalized surface measure on the l _n,p -unit sphere is studied and used for deriving a geometric measure representation for l _n,p -symmetric distributions having a density.     

Integral varieties of the canonical cone structure on <Emphasis Type="Italic">G</Emphasis>/<Emphasis Type="Italic">P</Emphasis>

The canonical cone structure on a compact Hermitian symmetric space G/P is the fiber bundle where is the cone of the highest weight vectors under the action of the reductive part of P. It is known that the cone coincides with the cone of the vectors tangent to the lines in G/P passing through x, when we consider G/P as a projective variety under its homogeneous embedding into the projective space of the irreducible representation space V of G with highest weight associated to P. A subvariety X of G/P is said to be an integral variety of at all smooth points xG/P. Equivalently, an integral variety of is a subvariety of G/P whose embedded projective tangent space at each smooth point is a linear space We prove a kind of rigidity of the integral varieties under some dimension condition. After making a uniform setting to study the problem, we apply the theory of Lie algebra cohomology as a main tool. Finally we show that the dimension condition is necessary by constructing counterexamples.     

Exponentially Many Monochromatic <Emphasis Type="Italic">n</Emphasis>-Matchings in <Emphasis Type="Italic">K</Emphasis><Subscript>3<Emphasis Type="Italic">n</Emphasis>-1</Subscript>

Erdös et al and Gerencsér et al had shown that in any 2-edge-coloring of K _3n-1, there is a n-matching containing edges with the same color(we call such matching monochromatic matching). In this paper we show that for any 2-edge-coloring of K _3n-1 there exists a monochromatic subgraph H of K _3n-1 which contains exponentially many monochromatic n-matchings.     

On a new property of <Emphasis Type="Italic">n</Emphasis>-poised and <Emphasis Type="Italic">G</Emphasis><Emphasis Type="Italic">C</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> sets

In this paper we consider n-poised planar node sets, as well as more special ones, called G C _n sets. For the latter sets each n-fundamental polynomial is a product of n linear factors as it always holds in the univariate case. A line ? is called k-node line for a node set \(\mathcal X\) if it passes through exactly k nodes. An (n + 1)-node line is called maximal line. In 1982 M. Gasca and J. I. Maeztu conjectured that every G C _n set possesses necessarily a maximal line. Till now the conjecture is confirmed to be true for n ≤ 5. It is well-known that any maximal line M of \(\mathcal X\) is used by each node in \(\mathcal X\setminus M, \)meaning that it is a factor of the fundamental polynomial. In this paper we prove, in particular, that if the Gasca-Maeztu conjecture is true then any n-node line of G C _n set \(\mathcal {X}\) is used either by exactly \(\binom {n}{2}\) nodes or by exactly \(\binom {n-1}{2}\) nodes. We prove also similar statements concerning n-node or (n ? 1)-node lines in more general n-poised sets. This is a new phenomenon in n-poised and G C _n sets. At the end we present a conjecture concerning any k-node line.     

Quasirecognition by prime graph of the simple group <Superscript>2</Superscript><Emphasis Type="Italic">G</Emphasis><Subscript>2</Subscript>(<Emphasis Type="Italic">q</Emphasis>)

Let G be a finite group. The main result of this paper is as follows: If G is a finite group, such that Γ(G) = Γ(²G₂(q)), where q = 3²ⁿ⁺¹ for some n ≥ 1, then G has a (unique) nonabelian composition factor isomorphic to ² G ₂(q). We infer that if G is a finite group satisfying |G| = |² G ₂(q)| and Γ(G) = Γ (² G ₂(q)) then G ? = ² G ₂(q). This enables us to give new proofs for some theorems; e.g., a conjecture of W. Shi and J. Bi. Some applications of this result are also considered to the problem of recognition by element orders of finite groups.     

Maximum Packings and Minimum Coverings of <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">v</Emphasis></Subscript> with Octagons

In this paper, we completely settle the maximum packing and minimum covering problem of K _v with octagons for v odd, give the maximum G-packing (minimum G-covering) for all possible leaves(repeats).     

On <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis>,<Emphasis Type="Italic">q</Emphasis></Subscript>-factorization of complete bipartite multigraphs

Let λK _m,n be a complete bipartite multigraph with two partite sets having m and n vertices, respectively. A K _p,q -factorization of λK _m,n is a set of edge-disjoint K _p,q -factors of λK _m,n which partition the set of edges of λK _m,n . When p = 1 and q is a prime number, Wang, in his paper [On K _1,q -factorization of complete bipartite graph, Discrete Math., 126: (1994), 359-364], investigated the K _1,q -factorization of K _m,n and gave a sufficient condition for such a factorization to exist. In papers [K _1,k -factorization of complete bipartite graphs, Discrete Math., 259: 301-306 (2002),; K _p,q -factorization of complete bipartite graphs, Sci. China Ser. A-Math., 47: (2004), 473-479], Du and Wang extended Wang’s result to the case that p and q are any positive integers. In this paper, we give a sufficient condition for λK _m,n to have a K _p,q -factorization. As a special case, it is shown that the necessary condition for the K _p,q -factorization of λK _m,n is always sufficient when p : q = k : (k + 1) for any positive integer k.     

Enumeration of <Emphasis Type="Italic">P</Emphasis><Subscript>4</Subscript>-Free Chordal Graphs

We count labelled chordal graphs with no induced path of length 3, both exactly and asymptotically. These graphs correspond to rooted trees in which no vertex has exactly one child, and each vertex has been expanded to a clique. Some properties of random graphs of this type are also derived. The corresponding unlabelled graphs are in 1-1 correspondence with unlabelled rooted trees on the same number of vertices. Research supported by the Australian Research Council. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, CanadaResearch carried out while this author was working at CWI and Utrecht University, The Netherlands     

<Emphasis Type="Italic">P</Emphasis>-adic continued fractions

We study Schneider’s p-adic continued fraction algorithms. For p=2, we give a combinatorial characterization of rational numbers that have terminating expansions. For arbitrary p, we give data showing that rationals with terminating expansions are relatively rare. Finally, we prove an analogue of Khinchin’s theorem.     

Structure of the semigroup <Emphasis Type="Italic">OT</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

We study the structure of the semigroup OT _n , which is a unique (up to an isomorphism) R-section of the semigroup T _n . For this semigroup, we describe Green relations, determine regular and nilpotent elements, describe maximal nilpotent subsemigroups, and determine the unique irreducible system of generatrices and maximal subsemigroups.