Parameters for which the Griesmer bound is not sharp

We prove for a large class of parameters t and r that a multiset of at most tθ_d-k+rθ_d-k-2 points in PG(d,q) that blocks every k-dimensional subspace at least t times must contain a sum of t subspaces of codimension k.We use our results to identify a class of parameters for linear codes for which the Griesmer bound is not sharp. Our theorem generalizes the non-existence results from Maruta [On the achievement of the Griesmer bound, Des. Codes Cryptogr. 12 (1997) 83-87] and Klein [On codes meeting the Griesmer bound, Discrete Math. 274 (2004) 289-297].     

A graph which is edge transitive but not arc transitive

A graph having 27 vertices is described, whose automorphism group is transitive on vertices and undirected edges, but not on directed edges.     

A topological space for which graph embeddability is undecidable

There exists a path-connected subspace of the plane for which graph embeddability is undecidable.     

On the graph for which there is a tree as the inverse interchange graph of a local graph

Let G be a finite, connected, undirected graph without loops and multiple edges. The note modifies slightly the concept of I^–1 (T_t), the inverse interchange graph of the local graph G(T_t) defined by a reference tree t G, and considers the properties of the graph G, when I^–1(T_t) is a tree.     

A lower bound for the circumference of a graph

Let G=(V, E) be a block of order n, different from K_n. Let m=min {d(x)+d(y): [x, y]?E}. We show that if m?n then G contains a cycle of length at least m.     

A tight lower bound for the completion time variance problem

We consider the completion time variance problem. Our main result is a tight lower bound for the mean completion time of an optimal sequence. This result can be applied to reduce the time required to solve the problem.     

A cohesive set which is not high

We study the degrees of unsolvability of sets which are cohesive (or have weaker recursion-theoretic “smallness” properties). We answer a question raised by the first author in 1972 by showing that there is a cohesive set A whose degree a satisfies a' = 0″ and hence is not high. We characterize the jumps of the degrees of r-cohesive sets, and we show that the degrees of r-cohesive sets coincide with those of the cohesive sets. We obtain analogous results for strongly hyperimmune and strongly hyperhyperimmune sets in place of r-cohesive and cohesive sets, respectively. We show that every strongly hyperimmune set whose degree contains either a Boolean combination of ∑2 sets or a 1-generic set is of high degree. We also study primitive recursive analogues of these notions and in this case we characterize the corresponding degrees exactly. MSC: 03D30, 03D55.     

A graph theoretical bound for the p-median problem

The p-median problem is a minisium network location problem that seeks to find the optimal location of p centres in a network. In the present paper a graph-theoretical bound is developed for the problem. This bound is based on shortest spanning trees and arborescences and other graphical properties of the problem. It is shown that the graph-theoretical bound dominates a bound based on shortest distances.     

A lower bound for the interval number of a graph

The interval number i(G) of a graph G with n vertices is the lowest integer m such that G is the intersection graph of some family of sets I₁,…,I_n with every I_i being the union of at most m real intervals. In this article a lower bound for i(G) is proved followed by some considerations about the construction of graphs that are critical with respect to the interval number.     

A weakly definable type which is not definable

Summary For each completion of Peano Arithmetic there is a weakly definable type which is not definable.     

A compact group which is not Valdivia compact

A compact space is Valdivia compact if it can be embedded in a Tikhonov cube in such a way that the intersection is dense in , where is the sigma-product ( the set of points with countably many non-zero coordinates). We show that there exists a compact connected Abelian group of weight which is not Valdivia compact, and deduce that Valdivia compact spaces are not preserved by open maps.

     

A countably categorical theory which is not G-compact

We give an example of a countably categorical theory which is not G-compact. The countable model of this theory does not have AZ-enumerations.     

A lower bound for the independence number of a planar graph

A subset of the vertices of a graph is independent if no two vertices in the subset are adjacent. The independence number α(G) is the maximum number of vertices in an independent set. We prove that if G is a planar graph on N vertices then $\text{α(G)/N ?}\text{2}\text{9}$.     

A bound on the chromatic number of a graph

We give an upper bound on the chromatic number of a graph in terms of its maximum degree and the size of the largest complete subgraph. Our results extends a theorem due to Brooks.