Network (discrete mathematics)

In discrete mathematics and geometry, a network is the name for a finite incidence structure with some additional properties. The term generalizes the term affine plane and specializes the term affine block plan . In a network, as in an affine plane, a parallel relation can be defined solely on the basis of the incidence.

Definitions and characteristics

A finite incidence structure, i.e. a triple of sets with and, is called a network if the following axioms are fulfilled: ${\displaystyle {\mathcal {N}}=({\mathfrak {p}},{\mathfrak {G}},I)}$ ${\displaystyle {\mathfrak {p}}\cap {\mathfrak {G}}=\emptyset }$ ${\displaystyle I\subseteq {\mathfrak {p}}\times {\mathfrak {G}}}$

1. At most one straight line goes through each two different points . ${\displaystyle p_{1},p_{2}\in {\mathfrak {p}}}$ ${\displaystyle G\in {\mathfrak {G}}}$
2. If , and if p does not incur with G , then there exists exactly one straight line which incurs with p but does not incise on G with any point . ${\displaystyle p\in {\mathfrak {p}},G\in {\mathfrak {G}}}$ ${\displaystyle H\in {\mathfrak {G}}}$
3. Every line is incised with at least two points. There is a point through which at least two straight lines go. If exactly two straight lines go through each point, each straight line has the same number of points.

Parallelism relation

With the second axiom it is possible to define a parallel relation on the set of straight lines ${\displaystyle {\mathcal {N}}}$

${\displaystyle G\parallel H\quad \Leftrightarrow \quad \left(G=H\lor (G)\cap (H)=\emptyset \right)}$ to introduce.

Key figures of a network

• Natural numbers exist for every network in such a way that exactly r straight lines pass through each point and exactly n points lie on each straight line . In this situation it is called a network ${\displaystyle r,n\in \mathbb {N} }$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle (r,n)}$
• It always applies . ${\displaystyle r\leq n+1}$
• If a network is a network, a network is obtained by removing a certain number of sets of parallels from the original set of lines, in which case only at least two sets of parallels must remain. ${\displaystyle {\mathcal {N}}=({\mathfrak {p}},{\mathfrak {G}},I)}$ ${\displaystyle {\mathcal {N'}}=({\mathfrak {p}},{\mathfrak {G}}',I')}$
• Every affine plane of order q is a network. A finite incidence structure is an affine plane if and only if it is a -net. ${\displaystyle (q+1,q)}$ ${\displaystyle (n+1,n)}$
• Each network is an incidence structure of the type , that is, a tactical configuration . If and only if is, the network is an affine plane. ${\displaystyle (r,n)}$ ${\displaystyle (m,1),m\in \{1,2\}}$ ${\displaystyle m=2}$

Examples and counterexamples

• For any natural number , the finite, plane grid of points with the parallels to the x - and y -axis as straight lines is a -net. If n is a prime power, then this network can be thought of as generated from an affine plane of order n , from which all sets of parallels except the parallels to the coordinate axes, i.e. sets, have been left out. ${\displaystyle n\geq 2}$ ${\displaystyle {\mathfrak {p}}=\{(x,y)\in \mathbb {Z} ^{2}|\;1\leq x,y\leq n\}}$ ${\displaystyle (2,n)}$ ${\displaystyle n-1}$
• The finite spatial lattice constructed in the same way has 3 straight lines through each point and n points on each straight line. It is an incidence structure of the type , but not a network, since the second axiom (uniqueness of parallels) is not satisfied. ${\displaystyle (1,1)}$
• Another generalization of the concept of affine geometry for arbitrarily dimensional spaces is the concept of weakly affine space . Met a finite weak affine space the axiom (2e) "There is a natural number , so that each line g exactly s contains points." And this space is in addition in the following sense precisely : "Are disjoint two lines, then they are parallel. ", then it is a network. ${\displaystyle s\geq 2}$
• A projective plane is never a network since the second axiom (existence of parallels) is not fulfilled.

construction

Construction from Latin squares

From each list of mutually orthogonal Latin squares (MOLS = mutually orthogonal Latin squares ) of order can be a produce net. Each of the Latin squares determines the incidence relation for the points in relation to a family of parallels. Then there are the two shares that are parallel to the or axis. Details of the construction are described in the article "Latin Square" in the section Latin Square # Geometry: Orthogonal Latin Squares and Finite Planes . ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle (q+2,n)}$ ${\displaystyle n^{2}\,}$ ${\displaystyle {\mathfrak {p}}=\{(x,y)|x,y\in \{1,2,3,\ldots n\}\}}$ ${\displaystyle x}$ ${\displaystyle y}$

The example described above of a "grid" with two sets of parallels also belongs to this type. It belongs to an empty list of MOLS.

Conversely, the sets of parallels in a network determine a list of MOLS of the order . Hence: A -net exists if and only if is. , the sequence of the largest possible numbers of pairwise orthogonal Latin squares of the order , is sequence A001438 in OEIS . ${\displaystyle r}$ ${\displaystyle (r,n)}$ ${\displaystyle r-2\,}$ ${\displaystyle n}$ ${\displaystyle (r,n)}$ ${\displaystyle r-2\leq R(n)}$ ${\displaystyle R(n)}$ ${\displaystyle n}$

Construction from smaller networks

A network can always be constructed from one and one network . One possible method is outlined in Latin Square # Orthogonal Latin Squares and MOLS . ${\displaystyle (r,m)}$ ${\displaystyle (r,n)}$ ${\displaystyle (r,m\cdot n)}$

Application: authentication

A digital signature is an authentication system that is used to guarantee that a certain message actually comes from a certain sender. Such a digital signature can be implemented with an (r, n) network : ${\displaystyle {\mathcal {N}}}$

• The possible data sets are the r families of parallels in the network , ${\displaystyle {\mathcal {N}}}$
• the possible keys are the points of the network ${\displaystyle n^{2}}$
• and the sent messages are straight out of a straight line ( message ) is valid, so it has the correct digital signature when they agreed with the point (the key incised). ${\displaystyle {\mathcal {N}}}$

Encryption does not take place here: an attacker can of course infer the set of parallels, i.e. the data set, from the information sent, a straight line in the network, but he cannot recognize the key. An authentication system with k keys, in which an attacker who knows at most one message, can only cheat with a probability of cheating, i.e. sending his own message as valid or replacing an authentic message with another, is called perfect , because this is precisely the probability of cheating corresponds to the probability of successfully “guessing” a key without prior information. ${\displaystyle 1/{\sqrt {k}}}$

The network based authentication system is perfect and it can be shown that any perfect authentication system is determined by a network. The largest possible number of possible data sets is obtained for , that is, when the network is an affine plane. ${\displaystyle r=n+1}$

literature

• Albrecht Beutelspacher : Introduction to Finite Geometry . I. Block plans. BI Wissenschaftsverlag, Mannheim / Vienna / Zurich 1982, ISBN 3-411-01632-9 , Chapter 3. Construction of block plans.
• Albrecht Beutelspacher , Ute Rosenbaum: Projective geometry . From the basics to the applications (=  Vieweg Studium: advanced course in mathematics ). 2nd, revised and expanded edition. Vieweg, Wiesbaden 2004, ISBN 3-528-17241-X ( table of contents [accessed April 1, 2012]).
• Harris F. MacNeish: Euler squares . In: The Annals of Mathematics . tape 23 , no. 3 , March 1922, p. 221-227 , JSTOR : 1967920 .

References and comments

1. ↑ Beutelspacher (1982), Section 3.4 Recursive Methods
2. ↑ The last requirement is only made in the special case mentioned, because it can always be proven from the other axioms if exactly two straight lines do not go through each point, Beutelspacher (1982), p. 131
3. ↑ The symbol stands for the set of points that intersect with the line G , cf. Incidence structure # Notation and basic terms . ${\displaystyle (G)}$
4. ↑ ^{a b} MacNeish (1922)
5. ↑ Beutelsbacher and Rosenbaum, 6.3 Authentication
6. ↑ Beutelsbacher and Rosenbaum, sentence 6.3.4
7. ^ Marijke De Soete, Klaus Vedder, Michael Walker: Cartesian Authentication Schemes . In: Advances in Cryptology - EUROCRYPT '89 . tape 434 , 1990, pp. 476-490 , doi : 10.1007 / 3-540-46885-4_46 .