Two-Weight Codes, Partial Geometries and Steiner Systems

Two-weight codes and projectivesets having two intersection sizes with hyperplanes are equivalentobjects and they define strongly regular graphs. We construct projective sets in PG(2m – 1,q) that have the sameintersection numbers with hyperplanes as the hyperbolic quadricQ⁺(2m – 1,q). We investigate these sets; we provethat if q = 2 the corresponding strongly regular graphsare switching equivalent and that they contain subconstituentsthat are point graphs of partial geometries. If m = 4the partial geometries have parameters s = 7, t = 8, = 4 and some of them are embeddable in Steinersystems S(2,8,120).     

Distance-Regular (0,α)-Reguli

We introduce distance-regular (0,α)-reguli and show that they give rise to (0,α)-geometries with a distance-regular point graph. This generalises the SPG-reguli of Thas [14] and the strongly regular (α,β)-reguli of Hamilton and Mathon [9], which yield semipartial geometries and strongly regular (α,β)-geometries, respectively. We describe two infinite classes of examples, one of which is a generalisation of the well-known semipartial geometry T_n^*(B) arising from a Baer subspace PG(n, q) in PG(n, q²). Research Fellow supported by the Flemish Institute for the Promotion of Scientific and Technological Research in Industry (IWT), grant no. IWT/SB/13367/Tonesi Research assistant of the Fund for Scientific Research Flanders (FWO-Vlaanderen).     

Randomized online graph coloring

We study the problem of coloring graphs in an online manner. The only known deterministic online graph coloring algorithm with a sublinear performance function was found by [9.], 319–325). Their algorithm colors graphs of chromatic number χ with no more than (2χn)/log^* n colors, where n is the number of vertices. They point out that the performance can be improved slightly for graphs with bounded chromatic number. For three-chromatic graphs the number of colors used, for example, is O(n log log log n/log log n). We show that randomization helps in coloring graphs online. We present a simple randomized online algorithm to color graphs with expected number of colors O(2^χχ²n^{(χ−2)/(χ−1)}(log n)^1/(χ−1)). For three-colorable graphs the expected number of colors our algorithm uses is . All our algorithms run in polynomial time. It is interesting to note that our algorithm compares well with the best known polynomial time offline algorithms. For instance, the best polynomial time algorithm known for three-colorable graphs, due to [4.] pp. 554–562). We also prove a lower bound of Ω((1/(χ − 1))((log n/(12(χ + 1))) − 1)^χ−1) for the randomized model. No lower bound for the randomized model was previously known. For bounded χ, our result improves even the best known lower bound for the deterministic case: Ω((log n/log log n)^χ−1), due to Noga Alon (personal communication, September 1989).     

Partial Ovoids in Classical Finite Polar Spaces

Ovoids in finite polar spaces are related to many other objects in finite geometries. In this article, we prove some new upper bounds for the size of partial ovoids in Q ^–(2n+1,q) and W(2n+ 1,q). Further, we give a combinatorial proof for the non-existence of ovoids of H(2n +1,q ²) for n>q ³.     

On-line coloring of perfect graphs

Lovász, Saks, and Trotter showed that there exists an on-line algorithm which will color any on-linek-colorable graph onn vertices withO(nlog^(2k–3) n/log^(2k–4) n) colors. Vishwanathan showed that at least (log ^k–1 n/k ^k ) colors are needed. While these remain the best known bounds, they give a distressingly weak approximation of the number of colors required. In this article we study the case of perfect graphs. We prove that there exists an on-line algorithm which will color any on-linek-colorable perfect graph onn vertices withn ^10k/loglogn colors and that Vishwanathan's techniques can be slightly modified to show that his lower bound also holds for perfect graphs. This suggests that Vishwanathan's lower bound is far from tight in the general case.Research partially supported by Office of Naval Research grant N00014-90-J-1206.     

Embeddings on a boolean cube

In this paper, we characterize a class of graphs which can be embedded on a boolean cube. Some of the graphs in this class are identified with the well known graphs such asmulti-dimensional mesh of trees, tree of meshes, etc. We suggest (i) an embedding of anr-dimensional mesh of trees ofn ^r (r+1)–rn ^r–1 nodes on a boolean cube of (2n) ^r nodes, and (ii) an embedding of a tree of meshes with 2n ² logn+n ² nodes on a boolean cube withn ² exp₂ (log (2 logn+1)]) nodes.     

Some Infinite Families of Locally Partial Geometries Generalizing the Classical Laguerre Planes

Starting with a subgeometry Ω embedded in a β-dimensional projective space PG(β, q), β 1, we construct inductively a series of rank n residually connected geometries Γ^{(n, β, Ω)}, n β, by putting Γ^{(β, β, Ω)} = Ω and extending Γ^{(n - 1, β, Ω)} with a partial geometry.     

Steiner systems andn −1-isomorphisms

In this work we introduce the concept of n ^–1-isomorphism between Steiner systems (this coincides with the concept of isomorphism whenever n=1).Precisely two Steiner systems S₁ and S₂ are said to be n^–1-isomorphic if there exist n partial systems S _i ⁽¹⁾ ,...,S _i ⁽ⁿ⁾ contained in Si, i.{1,2},such that S ₁ ^(k) and S ₂ ^(k) are isomorphic for each k{1,..., n}.The n^–1-isomorphisms are also used to study nets replacements, see Ostrom [8], and to study the transformation methods of designs and other incidence structures introduced in [9] and generalized in [1] and [10].Work done under the auspicies of G.N.S.A.G.A. supported by 40% grants of M.U.R.S.T.     

Limit theorems for sums of dependent random variables occurring in statistical mechanics

Summary We study the asymptotic behavior of partial sums S _nfor certain triangular arrays of dependent, identically distributed random variables which arise naturally in statistical mechanics. A typical result is that under appropriate assumptions there exist a real number m, a positive real number , and a positive integer k so that (S _n–nm)/n^1–1/2k converges weakly to a random variable with density proportional to exp(–¦s¦ ^2k/(2k)!). We explain the relation of these results to topics in Gaussian quadrature, to the theory of moment spaces, and to critical phenomena in physical systems.Alfred P. Sloan Research Fellow. Research supported in part by a Broadened Faculty Research Grant at the University of Massachusetts and by National Science Foundation Grant MPS 76-06644Research supported in part by National Science Foundation Grants MPS 74-04870 A01 and MCS 77-20683     

New Cyclic Difference Sets with Singer Parameters Constructed from d-Homogeneous Functions

In this paper, for a prime power q, new cyclic difference sets with Singer para- meters ((q ⁿ –1/q–1), (q ^n–1–1/q–1), (q ^n–2–1/q–1)) are constructed by using q-ary sequences (d-homogeneous functions) of period q ⁿ –1 and the generalization of GMW difference sets is proposed by combining the generation methods of d-form sequences and extended sequences. When q is a power of 3, new cyclic difference sets with Singer parameters ((q ⁿ –1/q–1), (q ^n–1–1/q–1), (q ^n–2–1/q–1)) are constructed from the ternary sequences of period q ⁿ –1 with ideal autocorrelation introduced by Helleseth, Kumar, and Martinsen.     

Geometric convergence to e−z by rational functions with real poles

Summary In this paper, we show that there exists a sequence of rational functions of the formR _n(z)=p_n–1(z)/(1+z/n)ⁿ,n=1, 2, ..., with degp _n–1n–1, which converges geometrically toe ^–z in the uniform norm on [0, +), as well as on some infinite sector symmetric about the positive real axis. We also discuss the usefulness of such rational functions in approximating the solutions of heat-conduction type problems.Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2688, and by the University of South Florida Research Council.Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2729, and by the Energy Research and Development Administration (ERDA) under Grant E(11-1)-2075.     

On the Spectrum of the Sizes of Maximal Partial Line Spreads in <Emphasis Type="Italic">PG</Emphasis>(2<Emphasis Type="Italic">n</Emphasis>,<Emphasis Type="Italic">q</Emphasis>), <Emphasis Type="Italic">n</Emphasis> ≥ 3

A lot of research has been done on the spectrum of the sizes of maximal partial spreads in PG(3,q) [P. Govaerts and L. Storme, Designs Codes and Cryptography, Vol. 28 (2003) pp. 51–63; O. Heden, Discrete Mathematics, Vol. 120 (1993) pp. 75–91; O. Heden, Discrete Mathematics, Vol. 142 (1995) pp. 97–106; O. Heden, Discrete Mathematics, Vol. 243 (2002) pp. 135–150]. In [A. Gács and T. Sznyi, Designs Codes and Cryptography, Vol. 29 (2003) pp. 123–129], results on the spectrum of the sizes of maximal partial line spreads in PG(N,q), N 5, are given. In PG(2n,q), n 3, the largest possible size for a partial line spread is q^2n-1+q^2n-3+...+q³+1. The largest size for the maximal partial line spreads constructed in [A. Gács and T. Sznyi, Designs Codes and Cryptography, Vol. 29 (2003) pp. 123–129] is (q²ⁿ⁺¹–q)/(q²–1)–q³+q²–2q+2. This shows that there is a non-empty interval of values of k for which it is still not known whether there exists a maximal partial line spread of size k in PG(2n,q). We now show that there indeed exists a maximal partial line spread of size k for every value of k in that interval when q 9.J. Eisfeld: Supported by the FWO Research Network WO.011.96NP. Sziklai: The research of this author was partially supported by OTKA D32817, F030737, F043772, FKFP 0063/2001 and Magyary Zoltan grants. The third author is grateful for the hospitality of Ghent University.     

Skew-symmetric association schemes with two classes and strongly regular graphs of type L 2n−1(4n−1)

A construction of a pair of strongly regular graphs ⁿ and ⁿ of type L _2n–1(4n–1) from a pair of skew-symmetric association schemes W, W of order 4n–1 is presented. Examples of graphs with the same parameters as ⁿ and ⁿ, i.e., of type L _2n–1(4n–1), were known only if 4n–1=p ³, where p is a prime. The first new graph appearing in the series has parameters (v, k, )=(225, 98, 45). A 4-vertex condition for relations of a skew-symmetric association scheme (very similar to one for the strongly regular graphs) is introduced and is proved to hold in any case. This has allowed us to check the 4-vertex condition for ⁿ and ⁿ, thus to prove that ⁿ and ⁿ are not rank three graphs if n>2.     

Finding Hamiltonian circuits in quasi-adjoint graphs

This paper is motivated by a method used for DNA sequencing by hybridization presented in [Jacek Blazewicz, Marta Kasprzak, Computational complexity of isothermic DNA sequencing by hybridization, Discrete Appl. Math. 154 (5) (2006) 718–729]. This paper presents a class of digraphs: the quasi-adjoint graphs. This class includes the ones used in the paper cited above. A polynomial recognition algorithm in O(n³), as well as a polynomial algorithm in O(n²+m²) for finding a Hamiltonian circuit in these graphs are given. Furthermore, some results about related problems such as finding a Eulerian circuit while respecting some forbidden transitions (a path with three vertices) are discussed.     

Constrained near-minimax approximation by weighted expansion and interpolation using Chebyshev polynomials of the second,third, and fourth kinds

Well known results on near-minimax approximation using Chebyshev polynomials of the first kind are here extended to Chebyshev polynomials of the second, third, and fourth kinds. Specifically, polynomial approximations of degreen weighted by (1–x ²)^1/2, (1+x)^1/2 or (1–x)^1/2 are obtained as partial sums of weighted expansions in Chebyshev polynomials of the second, third, or fourth kinds, respectively, to a functionf continuous on [–1, 1] and constrained to vanish, respectively, at ±1, –1 or +1. In each case a formula for the norm of the resulting projection is determined and shown to be asymptotic to 4^–2logn +A +o(1), and this provides in each case and explicit bound on the relative closeness of a minimax approximation. The constantA that occurs for the second kind polynomial is markedly smaller, by about 0.27, than that for the third and fourth kind, while the latterA is identical to that for the first kind, where the projection norm is the classical Lebesgue constant _n . The results on the third and fourth kind polynomials are shown to relate very closely to previous work of P.V. Galkin and of L. Brutman.Analogous approximations are also obtained by interpolation at zeros of second, third, or fourth kind polynomials of degreen+1, and the norms of resulting projections are obtained explicitly. These are all observed to be asymptotic to 2^–1logn +B +o(1), and so near-minimax approximations are again obtained. The norms for first, third, and fourth kind projections appear to be converging to each other. However, for the second kind projection, we prove that the constantB is smaller by a quantity asymptotic to 2^–1log2, based on a conjecture about the point of attainment of the supremum defining the projection norm, and we demonstrate that the projection itself is remarkably close to a minimal (weighted) interpolation projection.All four kinds of Chebyshev polynomials possess a weighted minimax property, and, in consequence, all the eight approximations discussed here coincide with minimax approximations when the functionf is a suitably weighted polynomial of degreen+1.     

Enumeration and limit laws for series–parallel graphs

We show that the number g_n of labelled series–parallel graphs on n vertices is asymptotically g_ngn^−5/2γⁿn!, where γ and g are explicit computable constants. We show that the number of edges in random series–parallel graphs is asymptotically normal with linear mean and variance, and that it is sharply concentrated around its expected value. Similar results are proved for labelled outerplanar graphs and for graphs not containing K_2,3 as a minor.     

An optimal lower bound on the number of variables for graph identification

In this paper we show that (n) variables are needed for first-order logic with counting to identify graphs onn vertices. Thek-variable language with counting is equivalent to the (k–1)-dimensional Weisfeiler-Lehman method. We thus settle a long-standing open problem. Previously it was an open question whether or not 4 variables suffice. Our lower bound remains true over a set of graphs of color class size 4. This contrasts sharply with the fact that 3 variables suffice to identify all graphs of color class size 3, and 2 variables suffice to identify almost all graphs. Our lower bound is optimal up to multiplication by a constant becausen variables obviously suffice to identify graphs onn vertices.Research supported by NSF grant CCR-8709818.Research supported by NSF grant CCR-8805978 and Pennsylvania State University Research Initiation grant 428-45.Research supported by NSF grants DCR-8603346 and CCR-8806308.     

Linking (n − 2)-dimensional panels inn-space II: (n − 2, 2)-frameworks and body and hinge structures

An (n – 1, 2)-framework inn-space is a structure consisting of a finite set of (n – 2)-dimensional panels and a set of rigid bars each joining a pair of panels using ball joints. A body and hinge (or (n + 1,n – 1)-) framework inn-space consists of a finite set ofn-dimensional bodies articulated by a set of (n – 2)-dimensional hinges, i.e., joints in 2-space, line hinges in 3-space, plane-hinges in 4-space, etc. In this paper we characterize the graphs of all rigid (n – 1, 2)- and (n + 1,n – 1)-frameworks inn-space. Rigidity here is statical rigidity or equivalently infinitesimal rigidity.     

Generalized Neuwirth Groups and Seifert Fibered Manifolds

The topological properties of the generalized Neuwirth groups, _n^k are discussed. For examp, we demonstrate that the group, _n^k is the fundamental group of the Seifert fibered space _n^k. Moreover, discuss some other invariants and algebraic properties of the above groups.This work was supported by Polish grant (BW-5100–5–0259–9) and the Russian Foundation for Basic Research (grant number 98–01–00699).2000 Mathematics Subject Classification: 20F34, 57M05, 57M60     

Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3

The best approximation algorithm for Max Cut in graphs of maximum degree 3 uses semidefinite programming, has approximation ratio 0.9326, and its running time is Θ(n^3.5logn); but the best combinatorial algorithms have approximation ratio 4/5 only, achieved in O(n²) time [J.A. Bondy, S.C. Locke, J. Graph Theory 10 (1986) 477–504; E. Halperin, et al., J. Algorithms 53 (2004) 169–185]. Here we present an improved combinatorial approximation, which is a 5/6-approximation algorithm that runs in O(n²) time, perhaps improvable even to O(n). Our main tool is a new type of vertex decomposition for graphs of maximum degree 3.