Existence of HSOLSSOMs of type

In this paper we investigate the existence of holey self-orthogonal Latin squares with a symmetric orthogonal mate of type 2ⁿu¹ (HSOLSSOM(2ⁿu¹)). For u2, necessary conditions for existence of such an HSOLSSOM are that u must be even and n3u/2+1. Xu Yunqing and Hu Yuwang have shown that these HSOLSSOMs exist whenever either (1) n9 and n3u/2+1 or (2) n263 and n2(u-2). In this paper we show that in (1) the condition n9 can be extended to n30 and that in (2), the condition n263 can be improved to n4, except possibly for 19 pairs (n,u), the largest of which is (53,28).     

On the number of independent chorded cycles in a graph

Hajnal and Corrádi proved that any simple graph on at least 3k vertices with minimal degree at least 2k contains k independent cycles. We prove the analogous result for chorded cycles. Let G be a simple graph with |V(G)|4k and minimal degree δ(G)3k. Then G contains k independent chorded cycles. This result is sharp.     

On the code generated by the incidence matrix of points and k-spaces in and its dual

In this paper, we study the p-ary linear code C_k(n,q), q=p^h, p prime, h1, generated by the incidence matrix of points and k-dimensional spaces in PG(n,q). For kn/2, we link codewords of C_k(n,q)C_k(n,q) of weight smaller than 2q^k to k-blocking sets. We first prove that such a k-blocking set is uniquely reducible to a minimal k-blocking set, and exclude all codewords arising from small linear k-blocking sets. For k<n/2, we present counterexamples to lemmas valid for kn/2. Next, we study the dual code of C_k(n,q) and present a lower bound on the weight of the codewords, hence extending the results of Sachar [H. Sachar, The F_p span of the incidence matrix of a finite projective plane, Geom. Dedicata 8 (1979) 407–415] to general dimension.     

disjoint cycles containing specified independent vertices

Let k1 be an integer and G be a graph of order n3k satisfying the condition that σ₂(G)n+k-1. Let v₁,…,v_k be k independent vertices of G, and suppose that G has k vertex-disjoint triangles C₁,…,C_k with v_iV(C_i) for all 1ik.Then G has k vertex-disjoint cycles such that

(i) for all 1ik.

(ii) , and

(iii) At least k-1 of the k cycles are triangles.

The condition of degree sum σ₂(G)n+k-1 is sharp.

On shredders and vertex connectivity augmentation

We consider the following problem: given a k-(node) connected graph G find a smallest set F of new edges so that the graph G+F is (k+1)-connected. The complexity status of this problem is an open question. The problem admits a 2-approximation algorithm. Another algorithm due to Jordán computes an augmenting edge set with at most (k−1)/2 edges over the optimum. CV(G) is a k-separator (k-shredder) of G if |C|=k and the number b(C) of connected components of G−C is at least two (at least three). We will show that the problem is polynomially solvable for graphs that have a k-separator C with b(C)k+1. This leads to a new splitting-off theorem for node connectivity. We also prove that in a k-connected graph G on n nodes the number of k-shredders with at least p components (p3) is less than 2n/(2p−3), and that this bound is asymptotically tight.     

On the structure of semi-invariant polynomials in Ore extensions

Let D be an X-outer S-derivation of a prime ring R, where S is an automorphism of R. The following is proved among other things: The degree of the minimal semi-invariant polynomial of the Ore extension R[X;S,D] is ν if charR=0, and is p^kν for some k0 if charR=p2, where ν is the least integer ν1 such that S^νDS^−ν−D is X-inner. A similar result holds for cv-polynomials. These are done by introducing the new notion of k-basic polynomials for each integer k0, which enable us to analyze semi-invariant polynomials inductively.     

The dominating set problem is fixed parameter tractable for graphs of bounded genus

We describe an algorithm for the dominating set problem with time complexity O((4g+40)^kn²) for graphs of bounded genus g1, where k is the size of the set. It has previously been shown that this problem is fixed parameter tractable for planar graphs. We give a simpler proof for the previous O(8^kn²) result for planar graphs. Our method is a refinement of the earlier techniques.     

Algorithms for extracting motifs from biological weighted sequences

In this paper we present three algorithms for the Motif Identification Problem in Biological Weighted Sequences. The first algorithm extracts repeated motifs from a biological weighted sequence. The motifs correspond to repetitive words which are approximately equal, under a Hamming distance, with probability of occurrence 1/k, where k is a small constant. The second algorithm extracts common motifs from a set of N2 weighted sequences. In this case, the motifs consists of words that must occur with probability 1/k, in 1qN distinct sequences of the set. The third algorithm extracts maximal pairs from a biological weighted sequence. A pair in a sequence is the occurrence of the same word twice. In addition, the algorithms presented in this paper improve previous work on these problems.     

The maximum spectral radius of -free graphs of given order and size

Suppose that G is a graph with n vertices and m edges, and let μ be the spectral radius of its adjacency matrix.Recently we showed that if G has no 4-cycle, then μ²-μn-1, with equality if and only if G is the friendship graph.Here we prove that if m9 and G has no 4-cycle, then μ²m, with equality if G is a star. For 4m8 this assertion fails.     

Selecting distances in arrangements of hyperplanes spanned by points

In this paper we consider a problem of distance selection in the arrangement of hyperplanes induced by n given points. Given a set of n points in d-dimensional space and a number k, , determine the hyperplane that is spanned by d points and at distance ranked by k from the origin. For the planar case we present an O(nlog²n) runtime algorithm using parametric search partly different from the usual approach [N. Megiddo, J. ACM 30 (1983) 852]. We establish a connection between this problem in 3-d and the well-known 3SUM problem using an auxiliary problem of counting the number of vertices in the arrangement of n planes that lie between two sheets of a hyperboloid. We show that the 3-d problem is almost 3SUM-hard and solve it by an O(n²log²n) runtime algorithm. We generalize these results to the d-dimensional (d4) space and consider also a problem of enumerating distances.     

The union of minimal hitting sets: Parameterized combinatorial bounds and counting

A k-hitting set in a hypergraph is a set of at most k vertices that intersects all hyperedges. We study the union of all inclusion-minimal k-hitting sets in hypergraphs of rank r (where the rank is the maximum size of hyperedges). We show that this union is relevant for certain combinatorial inference problems and give worst-case bounds on its size, depending on r and k. For r=2 our result is tight, and for each r3 we have an asymptotically optimal bound and make progress regarding the constant factor. The exact worst-case size for r3 remains an open problem. We also propose an algorithm for counting all k-hitting sets in hypergraphs of rank r. Its asymptotic runtime matches the best one known for the much more special problem of finding one k-hitting set. The results are used for efficient counting of k-hitting sets that contain any particular vertex.     

A Characterization of Graphs with No Cube Minor

In this paper it is shown that any 4-connected graph that does not contain a minor isomorphic to the cube is a minor of the line graph of V_n for some n6 or a minor of one of five graphs. Moreover, there exists a unique 5-connected graph on at least 8 vertices with no cube minor and a unique 4-connected graph with a vertex of degree at least 8 with no cube minor. Further, it is shown that any graph with no cube minor is obtained from 4-connected such graphs by 0-, 1-, and 2-summing, and 3-summing over a specified triangles.     

Continued fractions with multiple limits

For integers m2, we study divergent continued fractions whose numerators and denominators in each of the m arithmetic progressions modulo m converge. Special cases give, among other things, an infinite sequence of divergence theorems, the first of which is the classical Stern–Stolz theorem.We give a theorem on a class of Poincaré-type recurrences which shows that they tend to limits when the limits are taken in residue classes and the roots of their characteristic polynomials are distinct roots of unity.We also generalize a curious q-continued fraction of Ramanujan's with three limits to a continued fraction with k distinct limit points, k2. The k limits are evaluated in terms of ratios of certain q-series.Finally, we show how to use Daniel Bernoulli's continued fraction in an elementary way to create analytic continued fractions with m limit points, for any positive integer m2.     

Representable orientations of the free spikes

All orientations of binary and ternary matroids are representable [R.G. Bland, M. Las Vergnas, Orientability of matroids, J. Combinatorial Theory Ser. B 24 (1) (1978) 94–123; J. Lee, M. Scobee, A characterization of the orientations of ternary matroids, J. Combin. Theory Ser. B 77 (2) (1999) 263–291]. In this paper we show that this is not the case for matroids that are representable over GF(p^k) where k2. Specifically, we show that there are orientations of the rank-k free spike that are not representable for all k4. The proof uses threshold functions to obtain an upper bound on the number of representable orientations of the free spikes.     

Perfect codes in direct products of cycles—a complete characterization

Let be a direct product of cycles. It is known that for any r1, and any n2, each connected component of G contains a so-called canonical r-perfect code provided that each ℓ_i is a multiple of rⁿ+(r+1)ⁿ. Here we prove that up to a reasonably defined equivalence, these are the only perfect codes that exist.     

Hilbert's Tenth Problem for function fields of varieties over number fields and p-adic fields

Let k be a subfield of a p-adic field of odd residue characteristic, and let be the function field of a variety of dimension n1 over k. Then Hilbert's Tenth Problem for is undecidable. In particular, Hilbert's Tenth Problem for function fields of varieties over number fields of dimension 1 is undecidable.     

Stable extendibility of vector bundles over lens spaces mod 3 and the stable splitting problem

Let Lⁿ(3) denote the (2n+1)-dimensional standard lens space mod 3. In this paper, we study the conditions for a given real vector bundle over Lⁿ(3) to be stably extendible to L^m(3) for every mn, and establish the formula on the power ζ^k=ζζ (k-fold) of a real vector bundle ζ over Lⁿ(3). Moreover, we answer the stable splitting problem for real vector bundles over Lⁿ(3) by means of arithmetic conditions.     

Cycles through a prescribed vertex set in N-connected graphs

A well-known result of Dirac (Math. Nachr. 22 (1960) 61) says that given n vertices in an n-connected G, G has a cycle through all of them. In this paper, we generalize Dirac's result as follows:Given at most vertices in an n-connected graph G when n3 and , then G has a cycle through exactly n vertices of them.This improves the previous known bound given by Kaneko and Saito (J. Graph Theory 15(6) (1991) 655).     

Resource augmentation for online bounded space bin packing

We study online bounded space bin packing in the resource augmentation model of competitive analysis. In this model, the online bounded space packing algorithm has to pack a list L of items in (0,1] into a small number of bins of size b1. Its performance is measured by comparing the produced packing against the optimal offline packing of the list L into bins of size 1.We present a complete solution to this problem: For every bin size b1, we design online bounded space bin packing algorithms whose worst case ratio in this model comes arbitrarily close to a certain bound ρ(b). Moreover, we prove that no online bounded space algorithm can perform better than ρ(b) in the worst case.