On Sets Defining Few Ordinary Lines

Let $P$ P be a set of $n$ n points in the plane, not all on a line. We show that if $n$ n is large then there are at least $n/2$ n / 2 ordinary lines, that is to say lines passing through exactly two points of $P$ P . This confirms, for large $n$ n , a conjecture of Dirac and Motzkin. In fact we describe the exact extremisers for this problem, as well as all sets having fewer than $n-C$ n - C ordinary lines for some absolute constant $C$ C . We also solve, for large $n$ n , the “orchard-planting problem”, which asks for the maximum number of lines through exactly 3 points of $P$ P . Underlying these results is a structure theorem which states that if $P$ P has at most $Kn$ K n ordinary lines then all but O(K) points of $P$ P lie on a cubic curve, if $n$ n is sufficiently large depending on $K$ K .     

Small Triangle-Free Configurations of Points and Lines

In the paper we show that all combinatorial triangle-free configurations for v ≤ 18 are geometrically realizable. We also show that there is a unique smallest astral (18₃) triangle-free configuration and its Levi graph is the generalized Petersen graph G(18,5). In addition, we present geometric realizations of the unique flag transitive triangle-free configuration (20₃) and the unique point transitive triangle-free configuration (21₃).     

A Bichromatic Incidence Bound and an Application

We prove a new, tight upper bound on the number of incidences between points and hyperplanes in Euclidean d-space. Given n points, of which k are colored red, there are O _d (m ^2/3 k ^2/3 n ^(d−2)/3+kn ^d−2+m) incidences between the k red points and m hyperplanes spanned by all n points provided that m=Ω(n ^d−2). For the monochromatic case k=n, this was proved by Agarwal and Aronov (Discrete Comput. Geom. 7(4):359–369, 1992).     

Groups with Few Nonmodular Subgroups

Let G be a Tarski-free group such that the join of all nonmodular subgroups of G is a proper subgroup in G. It is proved that G contains a finite normal subgroup N such that the quotient group G/N has a modular subgroup lattice.__________Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 56, No. 10, pp. 1419 – 1423, October, 2004.     

On Rings with Few Orbits

In this article we investigate the structure of rings with some strong symmetry condition.     

Finite Groups with Few TI-Subgroups

A subgroup A of a finite group G is called a TI-subgroup if either A ∩ A ^x  = 1 or A ∩ A ^x  = A holds for all x ∈ G. In this paper, finite group all of whose meta-cyclic subgroups are TI-subgroups are classified completely. In particular, such groups are solvable.     

Equivelar Polyhedra with Few Vertices

We know that the polyhedra corresponding to the Platonic solids are equivelar. In this article we have classified completely all the simplicial equivelar polyhedra on ≤ 11 vertices. There are exactly 27 such polyhedra. For each n\geq -4 , we have classified all the (p,q) such that there exists an equivelar polyhedron of type {p,q} and of Euler characteristic n . We have also constructed five types of equivelar polyhedra of Euler characteristic -2m , for each m\geq 2 . Received February 14, 2000, and in revised form August 15, 2000. Online publication March 26, 2001.     

Decomposition of Bicolored Square Arrays into Bichromatic Diagonals

Let M be an array (), where each of its cells is colored in one of two colors. We give a necessary and sufficient condition for the existence of a partition of M into n diagonals, each containing at least one cell of each color. As a consequence, it follows that if each color appears in at least cells, then such a partition exists. The proof uses results on completion of partial Latin squares.     

Spanning Trees with Few Leaves

In this paper, we prove that an m-connected graph G on n vertices has a spanning tree with at most k leaves (for k ≥ 2 and m ≥ 1) if every independent set of G with cardinality m + k contains at least one pair of vertices with degree sum at least n − k + 1. This is a common generalization of results due to Broersma and Tuinstra and to Win.     

Tiling Hamming Space with Few Spheres

We show that if the collection of all binary vectors of lengthnis partitioned intokspheres, then eitherk2 orkn+2. Moreover, such partitions withk=n+2 are essentially unique.     

Geometric Graphs with Few Disjoint Edges

A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position, the edges are represented by straight line segments connecting the corresponding points. Improving a result of Pach and T?rőcsik, we show that a geometric graph on n vertices with no k+1 pairwise disjoint edges has at most k ³ (n+1) edges. On the other hand, we construct geometric graphs with n vertices and approximately (3/2)(k-1)n edges, containing no k+1 pairwise disjoint edges. We also improve both the lower and upper bounds of Goddard, Katchalski, and Kleitman on the maximum number of edges in a geometric graph with no four pairwise disjoint edges. Received May 7, 1998, and in revised form March 24, 1999.     

Finite Groups with Few Non-Abelian Subgroups

Let G be a finite group and τ(G) denote the number of conjugacy classes of all non-abelian subgroups of G. The symbol π(G) denotes the set of the prime divisors of |G|. In this paper, finite groups with τ(G) ≤ |π(G)| are classified completely. Furthermore, finite nonsolvable groups with τ(G) = |π(G)| +1 are determined.     

Soluble Groups with Few Non-Baer Subgroups

We characterize non-finitely generated soluble groups with the maximal condition on non-Baer subgroups and prove that a non-Baer soluble group is a ^ˇCernikov group or it has an infinite properly descending series of non-Baer subgroups.