Small point sets of PG(n, q 3) intersecting each k-subspace in 1 mod q points

The main result of this paper is that point sets of PG(n, q ³), q = p ^h , p ≥ 7 prime, of size less than 3(q ^3(n?k) + 1)/2 intersecting each k-space in 1 modulo q points (these are always small minimal blocking sets with respect to k-spaces) are linear blocking sets. As a consequence, we get that minimal blocking sets of PG(n, p ³), p ≥ 7 prime, of size less than 3(p ^3(n?k) + 1)/2 with respect to k-spaces are linear. We also give a classification of small linear blocking sets of PG(n, q ³) which meet every (n ? 2)-space in 1 modulo q points.     

Combinatorial constructions for optimal 2-D optical orthogonal codes with AM-OPPTS property

We develop a new one-to-one correspondence between a two-dimensional (m × n, k, ρ) optical orthogonal code (2-D (m × n, k, ρ)-OOC) with AM-OPPTS (at most one-pulse per time slot) property and a certain combinatorial subject, called an n-cyclic holey packing of type m ⁿ . By this link, an upper bound on the size of a 2-D (m × n, k, ρ)-OOC with AM-OPPTS property is derived. Afterwards, we employ combinatorial methods to construct infinitely many 2-D (m × n, k, 1)-OOCs with AM-OPPTS property, whose existence was previously unknown. All these constructions meet the upper bounds with equality and are thus optimal.     

On the Enumeration of Non-Crossing Pairings of Well-Balanced Binary Strings

A non-crossing pairing on a binary string pairs ones and zeroes such that the arcs representing the pairings are non-crossing. A binary string is well-balanced if it is of the form ${1^{a_1} 0^{a_1}1^{a_2} 0^{a_2} . . .1^{a_r} 0^{a_r}}$ . In this paper we establish connections between non-crossing pairings of well-balanced binary strings and various lattice paths in plane. We show that for well-balanced binary strings with a ₁ ≤ a ₂ ≤  . . . ≤  a _r , the number of non-crossing pairings is equal to the number of lattice paths on the plane with certain right boundary, and hence can be enumerated by differential Goncarov polynomials. For the regular binary strings S =  (1 ^k 0 ^k ) ⁿ , the number of non-crossing pairings is given by the (k + 1)-Catalan numbers. We present a simple bijective proof for this case.     

Nonnegative sectional curvature hypersurfaces in a real space form

In this paper, we investigate the nonnegative sectional curvature hypersurfaces in a real space form M ⁿ⁺¹(c). We obtain some rigidity results of nonnegative sectional curvature hypersurfaces M ⁿ⁺¹(c) with constant mean curvature or with constant scalar curvature. In particular, we give a certain characterization of the Riemannian product S ^k (a) × S ^n-k (√1 ? a ²), 1 ≤ k ≤ n ? 1, in S ⁿ⁺¹(1) and the Riemannian product H ^k (tanh² r ? 1) × S ^n-k (coth² r ? 1), 1 ≤ k ≤ n ? 1, in H ⁿ⁺¹(?1).     

Forbidden (0,1)-Vectors in Hyperplanes of ℝ n : The Restricted Case

In this paper we continue our investigation on “Extremal problems under dimension constraint” introduced in [2]. Let E(n, k) be the set of (0,1)-vectors in ? ⁿ with k one's. Given 1 ≤ m, w ≤ n let X ? E(n, m) satisfy span (X) ∩ E(n, w) = ?. How big can |X| be? This is the main problem studied in this paper. We solve this problem for all parameters 1 ≤ m, w ≤ n and n > n ₀(m, w).     

Geometry of D’Atri spaces of type k

A Riemannian n-dimensional manifold M is a D’Atri space of type k (or k-D’Atri space), 1 ≤ k ≤ n ? 1, if the geodesic symmetries preserve the k-th elementary symmetric functions of the eigenvalues of the shape operators of all small geodesic spheres in M. Symmetric spaces are k-D’Atri spaces for all possible k ≥ 1 and the property 1-D’Atri is the D’Atri condition in the usual sense. In this article we study some aspects of the geometry of k-D’Atri spaces, in particular those related to properties of Jacobi operators along geodesics. We show that k-D’Atri spaces for all k = 1, . . ., l satisfy that ${{\rm{tr}}(R_{v}^{k})}$ , v a unit vector in TM, is invariant under the geodesic flow for all k = 1, . . ., l. Further, if M is k-D’Atri for all k = 1, . . ., n ? 1, then the eigenvalues of Jacobi operators are constant functions along geodesics. In the case of spaces of Iwasawa type, we show that k-D’Atri spaces for all k = 1, . . ., n ? 1 are exactly the symmetric spaces of noncompact type. Moreover, in the class of Damek-Ricci spaces, the symmetric spaces of rank one are characterized as those that are 3-D’Atri.     

Spanning Connectivity of the Power of a Graph and Hamilton-Connected Index of a Graph

Let G = (V, E) be a connected graph. The hamiltonian index h(G) (Hamilton-connected index hc(G)) of G is the least nonnegative integer k for which the iterated line graph L ^k (G) is hamiltonian (Hamilton-connected). In this paper we show the following. (a) If |V(G)| ≥ k + 1 ≥ 4, then in G ^k , for any pair of distinct vertices {u, v}, there exists k internally disjoint (u, v)-paths that contains all vertices of G; (b) for a tree T,  h(T) ≤ hc(T) ≤ h(T) + 1, and for a unicyclic graph G,  h(G) ≤ hc(G) ≤ max{h(G) + 1, k′ + 1}, where k′ is the length of a longest path with all vertices on the cycle such that the two ends of it are of degree at least 3 and all internal vertices are of degree 2; (c) we also characterize the trees and unicyclic graphs G for which hc(G) = h(G) + 1.     

On multiple caps in finite projective spaces

In this paper, we consider new results on (k, n)-caps with n > 2. We provide a lower bound on the size of such caps. Furthermore, we generalize two product constructions for (k, 2)-caps to caps with larger n. We give explicit constructions for good caps with small n. In particular, we determine the largest size of a (k, 3)-cap in PG(3, 5), which turns out to be 44. The results on caps in PG(3, 5) provide a solution to four of the eight open instances of the main coding theory problem for q = 5 and k = 4.     

Smallest Set-Transversals of k-Partitions

We asymptotically solve an open problem raised independently by Sterboul (Colloq Math Soc J Bolyai 3:1387–1404, 1973), Arocha et al. (J Graph Theory 16:319–326, 1992) and Voloshin (Australas J Combin 11:25–45, 1995). For integers n ≥ k ≥ 2, let f(n, k) denote the minimum cardinality of a family ${\mathcal H}$ of k-element sets over an n-element underlying set X such that every partition ${X_1\cup\cdots\cup X_k=X}$ into k nonempty classes completely partitions some ${H\in\mathcal H}$ ;  that is, ${|H\cap X_i|=1}$ holds for all 1 ≤ i ≤ k. This very natural function—whose defining property for k = 2 just means that ${\mathcal H}$ is a connected graph—turns out to be related to several extensively studied areas in combinatorics and graph theory. We prove general estimates from which ${ f(n,k) = (1+o(1))\, \tfrac{2}{n}\,{n\choose k}}$ follows for every fixed k, and also for all k = o(n ^1/3), as n → ∞. Further, we disprove a conjecture of Arocha et al. (1992). The exact determination of f(n,k) for all n and k appears to be far beyond reach to our present knowledge, since e.g. the equality ${f(n,n-2)={n-2\choose 2}-{\rm ex}(n,\{C_3,C_4\})}$ holds, where the last term is the Turán number for graphs of girth 5.     

Flip Graphs of Bounded Degree Triangulations

We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider triangulations of sets of n points in convex position in the plane and prove that their flip graph is connected if and only if k > 6; the diameter of the flip graph is O(n ²). We also show that, for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for k ≤ 9, and flip graphs of triangulations can be disconnected for any k. Additionally, we consider a relaxed version of the original problem. We allow the violation of the degree bound k by a small constant. Any two triangulations with maximum degree at most k of a convex point set are connected in the flip graph by a path of length O(n log n), where every intermediate triangulation has maximum degree at most k + 4.     

Shortest string containing all permutations

In this paper, we consider the problem of constructing a shortest string of {1,2,…,n} containing all permutations on n elements as subsequences. For example, the string 1 2 1 3 1 2 1 contains the 6 (=3!) permutations of {1,2,3} and no string with less than 7 digits contains all the six permutations. Note that a given permutation, such as 1 2 3, does not have to be consecutive but must be from left to right in the string.We shall first give a rule for constructing a string of {1,2,…,n} of infinite length and the show that the leftmost n²?2n+4 digits of the string contain all the n! permutations (for n≥3). We conjecture that the number of digits f(n) = n²?2n+4 (for n≥3) is the minimum.Then we study a new function F(n,k) which is the minimum number of digits required for a string of n digits to contain all permutations of i digits, i≤k. We conjecture that F(n,k) = k(n?1) for 4≤k ≤n?1.     

A Note on Turán Numbers for Even Wheels

The Turán number ex(n, G) is the maximum number of edges in any n-vertex graph that does not contain a subgraph isomorphic to G. We consider a very special case of the Simonovits’s theorem (Simonovits in: Theory of graphs, Academic Press, New York, 1968) which determine an asymptotic result for Turán numbers for graphs with some properties. In the paper we present a more precise result for even wheels. We provide the exact value for Turán number ex(n, W _2k ) for n ≥ 6k ? 10 and k ≥ 3. In addition, we show that ${ex(n,W_6)= \lfloor\frac{n^2}{3}\rfloor}$ for all n ≥ 6. These numbers can be useful to calculate some Ramsey numbers.     

On the number of cycles possible in digraphs with large girth

We consider directed graphs which have no short cycles. In particular, if n is the number of vertices in a graph which has no cycles of length less than n ? k, for some constant k < ?n, then we show that the graph has no more than 3^k cycles. In addition, we show that for k ≤ ½n, there are graphs with exactly 3^k cycles. We thus are able to show that it is possible to bound the number of cycles possible in a graph which has no cycles of length less than f(n) by a polynomial in n if and only if f(n) ≥ n ? rlog(n) for some r.     

On stress matrices of (d + 1)-lateration frameworks in general position

Let (G, P) be a bar framework of n vertices in general position in ${\mathbb{R}^d}$ , for d ≤ n ? 1, where G is a (d + 1)-lateration graph. In this paper, we present a constructive proof that (G, P) admits a positive semidefinite stress matrix with rank (n ? d ? 1). We also prove a similar result for a sensor network, where the graph consists of m(≥ d + 1) anchors.     

The number of designs with geometric parameters grows exponentially

It is well-known that the number of 2-designs with the parameters of a classical point-hyperplane design PG _n-1(n, q) grows exponentially. Here we extend this result to the number of 2-designs with the parameters of PG _d (n, q), where 2 ≤ d ≤ n ? 1. We also establish a characterization of the classical geometric designs in terms of hyperplanes and, in the special case d = 2, also in terms of lines. Finally, we shall discuss some interesting configurations of hyperplanes arising in designs with geometric parameters.     

A Turán-Type Problem on Distances in Graphs

We suggest a new type of problem about distances in graphs and make several conjectures. As a first step towards proving them, we show that for sufficiently large values of n and k, a graph on n vertices that has no three vertices pairwise at distance k has at most (n ? k + 1)²/4 pairs of vertices at distance k.     

Rainbow Connection Number and Radius

The rainbow connection number, rc(G), of a connected graph G is the minimum number of colours needed to colour its edges, so that every pair of its vertices is connected by at least one path in which no two edges are coloured the same. In this note we show that for every bridgeless graph G with radius r, rc(G) ≤  r(r + 2). We demonstrate that this bound is the best possible for rc(G) as a function of r, not just for bridgeless graphs, but also for graphs of any stronger connectivity. It may be noted that for a general 1-connected graph G, rc(G) can be arbitrarily larger than its radius (K _1,n for instance). We further show that for every bridgeless graph G with radius r and chordality (size of a largest induced cycle) k, rc(G) ≤  rk. Hitherto, the only reported upper bound on the rainbow connection number of bridgeless graphs is 4n/5 ? 1, where n is order of the graph (Caro et al. in Electron J Comb 15(1):Research paper 57, 13, 2008). It is known that computing rc(G) is NP-Hard (Chakraborty and fischer in J Comb Optim 1–18, 2009). Here, we present a (r + 3)-factor approximation algorithm which runs in O(nm) time and a (d + 3)-factor approximation algorithm which runs in O(dm) time to rainbow colour any connected graph G on n vertices, with m edges, diameter d and radius r.     

On B(n,k) 2-groups

A finite group G is said to be a B(n, k) group if for any n-element subset {a ₁,…, a _n } of G, |{a _i a _j |1 ≤ i, j ≤ n}| ≤k. In this article, we give characterizations of the B(5, 19) 2-groups, and the B(6, k) 2-groups for 21 ≤ k ≤ 28.     

Packing Triangles in K 4-Free Graphs

Paul Erd?s conjectured that every K ₄-free graph of order n and size ${k + \lfloor n^2/4\rfloor}$ contains at least k edge disjoint triangles. In this note, we prove that such a graph contains at least 32k/35 + o(n ²) edge disjoint triangles and prove his conjecture for k ≥  0.077n ².     

Solving Non-Homogeneous Nested Recursions Using Trees

The solutions to certain nested recursions, such as Conolly’s C(n) = C(n?C(n?1)) + C(n?1?C(n?2)), with initial conditions C(1) = 1, C(2) = 2, have a well-established combinatorial interpretation in terms of counting leaves in an infinite binary tree. This tree-based interpretation, and its generalization to a similar k-term nested recursion, only apply to homogeneous recursions and only solve each recursion for one set of initial conditions determined by the tree. In this paper, we extend the tree-based interpretation to solve a non-homogeneous version of the k-term recursion that includes a constant term. To do so we introduce a tree-grafting methodology that inserts copies of a finite tree into the infinite k-ary tree associated with the solution of the corresponding homogeneous k-term recursion. This technique also solves the given non-homogeneous recursion with various sets of initial conditions.