Planar and affine spaces

In this note, we characterize finite three-dimensional affine spaces as the only linear spaces endowed with set Ω of proper subspaces having the properties (1) every line contains a constant number of points, say n, with n>2; (2) every triple of noncollinear points is contained in a unique member of Ω; (3) disjoint or coincide is an equivalence relation in Ω with the additional property that every equivalence class covers all points. We also take a look at the case n=2 (in which case we have a complete graph endowed with a set Ω of proper complete subgraphs) and classify these objects: besides the affine 3-space of order 2, two small additional examples turn up. Furthermore, we generalize our result in the case of dimension greater than three to obtain a characterization of all finite affine spaces of dimension at least 3 with lines of size at least 3.     

Near vector spaces over GF(q) and (v,q+1,1)-BIBD''s

The usual construction of (v,q+1,1)−BIBD's from vector spaces over GF(q) is generalized to the class of near vector spaces over GF(q). It is shown that every (v,q+1,1)−BIBD can be constructed from a near vector space over GF(q). Some corollaries are: Given a (v₁,q+1,1)−BIBD P₁,B₁ and a (v₂,q+1,1)−BIBD P₂,B₂, there is a ((q−1)v₁v₂+v₁+v₂,q+1,1)−BIBD P₃,B₃ containing P₁,B₁ and P₂,B₂ as disjoint subdesigns. If there is a (v,q+1,1)−BIBD then there is a ((q−1)v+1,q,1)−BIBD. Every finite partial (v,q,1)−BIBD can be embedded in a finite (v′,q+1,1)−BIBD.     

The order-interval hypergraph of a finite poset and the König property

We study the hypergraph H(P) whose vertices are the points of a finite poset and whose edges are the maximal intervals in P (i.e. sets of the form I = {{v ε P: p ν q}}, p minimal, q maximal). We mention resp. show that the problems of the determination of the independence number , the point covering number τ, the matching number v and the edge covering number p are NP-complete. For interval orders we describe polynomial algorithms and prove the König property (v = τ) and the dual König property (a = p). Finally we show that the (dual) König property is preserved by product.     

On finite matroids with two more hyperplanes than points

One of the most interesting results about finite matroids of finite rank and generalized projective spaces is the result of Basterfield, Kelly and Green (1968/1970) (J.G. Basterfield, L.M. Kelly, A characterization of sets of n points which determine n hyperplanes, in: Proceedings of the Cambridge Philosophical Society, vol. 64, 1968, pp. 585-588; C. Greene, A rank inequality for finite geometric lattices, J. Combin Theory 9 (1970) 357-364) affirming that any matroid contains at least as many hyperplanes as points, with equality in the case of generalized projective spaces. Consequently, the goal is to characterize and classify all matroids containing more hyperplanes than points. In 1996, I obtained the classification of all finite matroids containing one more hyperplane than points. In this paper a complete classification of finite matroids with two more hyperplanes than points is obtained. Moreover, a partial contribution to the classification of those matroids containing a certain number of hyperplanes more than points is presented.     

Harmonic trees

A graph G is defined to be harmonic if there is a constant λ (necessarily a natural number) such that, for every vertex v, the sum of the degrees of the neighbors of v equals λd_G (v) where d_G (v) is the degree of v. We show that there is exactly one finite harmonic tree for every λ ε , and we give a recursive construction for all infinite harmonic trees.     

Coincidence of the upper Kuratowski topology with the co-compact topology on compact sets, and the Prohorov property

For a Hausdorff space X, let F be the hyperspace of all closed subsets of X and H a sublattice of F. Following Nogura and Shakhmatov, X is said to be H-trivial if the upper Kuratowski topology and the co-compact topology coincide on H. F-trivial spaces are the consonant spaces first introduced and studied by Dolecki, Greco and Lechicki. In this paper, we deal with K-trivial spaces and Fin-trivial space, where K and Fin are respectively the lattices of compact and of finite subsets of X. It is proved that if C_k(X) is a Baire space or more generally if X has ‘the moving off property’ of Gruenhage and Ma, then X is K-trivial. If X is countable, then C_p(X) is Baire if and only if X is Fin-trivial and all compact subsets of X are finite. As for consonant spaces, it turns out that every regular K-trivial space is a Prohorov space. This result remains true for any regular Fin-trivial space in which all compact subsets are scattered. It follows that every regular first countable space without isolated points, all compact subsets of which are countable, is Fin-nontrivial. Examples of K-trivial non-consonant spaces, of Fin-trivial K-nontrivial spaces and of countably compact Prohorov Fin-nontrivial spaces, are given. In particular, we show that all (generalized) Fréchet–Urysohn fans are K-trivial, answering a question by Nogura and Shakhmatov. Finally, we describe an example of a continuous open compact-covering mapping f :X→Y, where X is Prohorov and Y is not Prohorov, answering a long-standing question by Topsøe.     

On deformations of transversely homogeneous foliations

A transversely homogeneous foliation is a foliation whose transverse model is a homogeneous space G/H. In this paper we consider the class of transversely homogeneous foliations on a manifold M which can be defined by a family of 1-forms on M fulfilling the Maurer–Cartan equation of the Lie group G. This class includes as particular cases Lie foliations and certain homogeneous spaces foliated by points. We develop, for the foliations belonging to this class, a deformation theory for which both the foliation and the model homogeneous space G/H are allowed to change. As the main result we show that, under some cohomological assumptions, there exist a versal space of deformations of finite dimension for the foliations of the class and when the manifold M is compact. Some concrete examples are discussed.     

On some properties of the series ∑k=0 kx and the Stirling numbers of the second kind

We partially characterize the rational numbers x and integers n 0 for which the sum ∑_k=0^∞ kⁿx^k assumes integers. We prove that if ∑_k=0^∞ kⁿx^k is an integer for x = 1 − a/b with a, b> 0 integers and gcd(a,b) = 1, then a = 1 or 2. Partial results and conjectures are given which indicate for which b and n it is an integer if a = 2. The proof is based on lower bounds on the multiplicities of factors of the Stirling number of the second kind, S(n,k). More specifically, we obtain for all integers k, 2 k n, and a 3, provided a is odd or divisible by 4, where v_a(m) denotes the exponent of the highest power of a which divides m, for m and a> 1 integers.

New identities are also derived for the Stirling numbers, e.g., we show that ∑_k=0²ⁿk! S(2n, k) , for all integers n 1.     

Algorithmic complexity of list colorings

Given a graph G = (V,E) and a finite set L(v) at each vertex v ε V, the List Coloring problem asks whether there exists a function f:V → _vεVL(V) such that (i) f(v)εL(v) for each vεV and (ii) f(u) ≠f(v) whenever u, vεV and uvεE. One of our results states that this decision problem remains NP-complete even if all of the followingconditions are met: (1) each set L(v) has at most three elements, (2) each “color” xε_vεVL(v) occurs in at most three sets L(v), (3) each vertex vεV has degree at most three, and (4) G is a planar graph. On the other hand, strengthening any of the assumptions (1)–(3) yields a polynomially solvable problem. The connection between List Coloring and Boolean Satisfiability is discussed, too.     

On a straight-line embedding problem of graphs

Let G be a planar graph with n vertices, v be a specified vertex of G, and P be a set of n points in the Euclidian plane in general position. A straight-line embedding of G onto P is an embedding of G onto whose images of vertices are distinct points in P and whose images of edges are (straight) line segments. In this paper, we classify into five classes those pairs of G and v such that for any P and any p P, G has a straight-line embedding onto P which maps v to p. We then show that all graphs in three of the classes indeed have such an embedding. This result gives a solution to a generalized version of the rooted-tree embedding problem raised by M. Perles.     

On Eccentric Connectivity Index and Connectivity

Let G be a finite connected graph. The eccentric connectivity index ξ^c(G) of G is defined as ξ^c(G)= _{v∈V (G)} ec(v)deg(v), where ec(v) and deg(v) denote the eccentricity and degree of a vertex v in G, respectively. In this paper, we give an asymptotically sharp upper bound on the eccentric connectivity index in terms of order and vertex-connectivity and in terms of order and edge-connectivity. We also improve the bounds for triangle-free graphs.     

Further results on nearly Kirkman triple systems with subsystems

In this paper we further discuss the embedding problem for nearly Kirkman triple systems and get the result that: (1) For u≡v≡0 (mod 6), v78, and u3.5v, there exists an NKTS(u) containing a sub-NKTS(v). (2) For v=18,24,30,36,42,48,54,60,66 or 72, there exists an NKTS(u) containing a sub-NKTS(v) if and only if u≡0 (mod 6) and u3v.     

Finding all essential terms of a characteristic maxpolynomial

Let us denote ab=max(a,b) and ab=a+b for and extend this pair of operations to matrices and vectors in the same way as in linear algebra. We present an O(n²(m+n log n)) algorithm for finding all essential terms of the max-algebraic characteristic polynomial of an n×n matrix over with m finite elements. In the cases when all terms are essential, this algorithm also solves the following problem: Given an n×n matrix A and k{1,…,n}, find a k×k principal submatrix of A whose assignment problem value is maximum.     

Some results on integral sum graphs

Let Z denote the set of all integers. The integral sum graph of a finite subset S of Z is the graph (S,E) with vertex set S and edge set E such that for u,vS, uvE if and only if u+vS. A graph G is called an integral sum graph if it is isomorphic to the integral sum graph of some finite subset S of Z. The integral sum number of a given graph G, denoted by ζ(G), is the smallest number of isolated vertices which when added to G result in an integral sum graph. Let x denote the least integer not less than the real x. In this paper, we (i) determine the value of ζ(K_n−E(K_r)) for r2n/3−1, (ii) obtain a lower bound for ζ(K_n−E(K_r)) when 2r<2n/3−1 and n5, showing by construction that the bound is sharp when r=2, and (iii) determine the value of ζ(K_r,r) for r2. These results provide partial solutions to two problems posed by Harary (Discrete Math. 124 (1994) 101–108). Finally, we furnish a counterexample to a result on the sum number of K_r,s given by Hartsfiedl and Smyth (Graphs and Matrices, R. Rees (Ed.), Marcel, Dekker, New York, 1992, pp. 205–211).     

ContributionsThe existence of perfect Mendelsohn designs with block size 7

Necessary conditions for existence of a (v,k,λ) perfect Mendelsohn design (or PMD) are v k and λv(v − 1) ≡ 0 mod k. When k = 7, this condition is satisfied if v ≡ 0 or 1 mod 7 and v 7 when λ 0 mod 7 and for all v 7 when λ ≡ 0 mod 7. Bennett, Yin and Zhu have investigated the existence problem for k = 7, λ = 1 and λ even; here we provide several improvements on their results and also investigate the situation for λ odd. We reduce the total number of unknown (v,7,λ)-PMDs to 36,31 for λ = 1 and 5 for λ > 1. In particular, v = 294 is the largest unknown case for λ = 1, and the only unknown cases for λ > 1 are for v = 42, λ [2,3,5,9] and v = 18, λ = 7.     

Every tree is 3-equitable

A labeling of a graph is a function f from the vertex set to some subset of the natural numbers. The image of a vertex is called its label. We assign the label |f(u)−f(v)| to the edge incident with vertices u and v. In a k-equitable labeling the image of f is the set {0,1,2,…,k−1}. We require both the vertex labels and the edge labels to be as equally distributed as possible, i.e., if v_i denotes the number of vertices labeled i and e_i denotes the number of edges labeled i, we require |v_i−v_j|1 and |e_i−e_j|1 for every i,j in {0,1,2,…,k−1}. Equitable graph labelings were introduced by I. Cahit as a generalization for graceful labeling. We prove that every tree is 3-equitable.     

Choosability of planar graphs

A graph G = G(V, E) with lists L(v), associated with its vertices v V, is called L-list colourable if there is a proper vertex colouring of G in which the colour assigned to a vertex v is chosen from L(v). We say G is k-choosable if there is at least one L-list colouring for every possible list assignment L with L(v) = k v V(G).

Now, let an arbitrary vertex v of G be coloured with an arbitrary colour f of L(v). We investigate whether the colouring of v can be continued to an L-list colouring of the whole graph. G is called free k-choosable if such an L-list colouring exists for every list assignment L (L(v) = k v V(G)), every vertex v and every colour f L(v). We prove the equivalence of the well-known conjecture of Erd s et al. (1979): “Every planar graph is 5-choosable” with the following conjecture: “Every planar graph is free 5-choosable”.     

Solvable block transitive automorphism groups of 2−(v,5,1) designs

Let G be a solvable block transitive automorphism group of a 2−(v,5,1) design and suppose that G is not flag transitive. We will prove that

(1) if G is point imprimitive, then v=21, and GZ₂₁:Z₆;

(2) if G is point primitive, then GAΓL(1,v) and v=p^a, where p is a prime number with p≡21 (mod 40), and a an odd integer.

     

Harary's conjectures on integral sum graphs

Let N denote the set of positive integers and Z denote all integers. The (integral) sum graph of a finite subset S N(Z) is the graph (S, E) with uv ε E if and only if u + v ε S. A graph G is said to be an (integral) sum graph if it is isomorphic to the (integral) sum graph of some S N(Z). The (integral) sum number of a given graph G is the smallest number of isolated nodes which when added to G result in an (integral) sum graph.

We show that the integral sum number of a complete graph with n 4 nodes equals 2n − 3, which proves a conjecture of Harary. And we disprove another conjecture of Harary by showing that there are infinitely many trees which are not caterpillars but are integral sum graphs.