PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Medium Entry average rating: No information on entry rating
linear space and near-linear space (Definition)

A near-linear space $ \mathscr{S}=(\mathcal{P},\mathcal{L})$ consists of a set of points $ \mathcal{P}$ and a set of lines $ \mathcal{L}$ satisfying the properties:

  1. any line contains at least two points, and
  2. any two points are on at most one line.

A near-linear space is also called a partial plane.

A linear space is a near-linear space in which every pair of distinct points are on exactly one line. (This usage of the term has no relation to its occasional appearance in linear algebra as a synonym for a vector space.)

Examples:

  1. If we take all the vertices in a graph as points, and edges as lines, it is then a near-linear space in which every line contains two points.
  2. Let $ \mathbb{F}$ be a finite field. Let $ \mathcal{P}$ be the elements in the Cartesian product $ \mathbb{F}\times \mathbb{F}$. The solutions to a linear equation
    $\displaystyle \{ (x,y)\in\mathcal{P} \mid ax+by =c\} $
    for some $ a, b, c\in \mathbb{F}$, where $ a$ and $ b$ are not both zero, form a line in $ \mathcal{L}$. Since any two points determine a unique line, $ \mathscr{A} = (\mathcal{P},\mathcal{L})$ is a linear space, called the affine plane over $ \mathbb{F}$.

Some properties:

  1. In a near-linear space, if two distinct lines intersect, they intersect in one point.
  2. There is no proper inclusion of lines in a near-linear space, i.e., if $ \ell_1$ and $ \ell_2$ are two lines such that $ \ell_1 \subseteq \ell_2$, then $ \ell_1=\ell_2$.
  3. In a near-linear space $ \mathscr{S}=(\mathcal{P},\mathcal{L})$,
    $\displaystyle \sum_{\ell \in \mathcal{L}} \binom{\vert\ell\vert}{2} \leq \binom{\vert\mathcal{P}\vert}{2}$
    with equality holds if and only if $ \mathscr{S}$ is a linear space.
  4. Let $ p$ be an arbitrary point in a linear space,
    $\displaystyle \sum_{\ell \ni p} (\vert\ell\vert - 1) = \vert\mathcal{P}\vert - 1$
    where the sum is taken over all lines containing $ p$. This holds because given any point, this point forms exactly one line with every other point, so $ \vert\ell\vert - 1$ counts the number of points $ p$ shares in line $ \ell$. Summing over all lines gives all the points except $ p$.



"linear space and near-linear space" is owned by kshum. [ full author list (3) | owner history (2) ]
(view preamble)

View style:

See Also: finite plane, projective plane, De Bruijn--Erdős theorem


Attachments:
criterion for a near-linear space being a linear space (Theorem) by kshum
Log in to rate this entry.
(view current ratings)

Cross-references: number, sum, equality, inclusion, intersect, affine plane, linear equation, solutions, Cartesian product, finite field, edges, graph, vertices, vector space, linear algebra, relation, term, plane, contains, properties, lines, points
There are 2 references to this entry.

This is version 12 of linear space and near-linear space, born on 2002-10-07, modified 2006-06-28.
Object id is 3509, canonical name is LinearSpace2.
Accessed 3309 times total.

Classification:
AMS MSC05C65 (Combinatorics :: Graph theory :: Hypergraphs)

Pending Errata and Addenda
None.
[ View all 5 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)