PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
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 $$ \{ (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})$ , $$\sum_{\ell \in \mathcal{L}} \binom{|\ell|}{2} \leq \binom{|\mathcal{P}|}{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, $$\sum_{\ell \ni p} (|\ell| - 1) = |\mathcal{P}| - 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 $|\ell| - 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 | get metadata)

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 3909 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)