(+36) 88 424 483

   Egyetem str. 10, Building I, 9th floor, Veszprém H-8200

  

Thesis

The theoretical background of the project lies in combinatorics and number theory. The task is to generate subsets of prescribed properties in a set system whose members are certain 3-element sets and ordered pairs, and in some cases also singletons.

Let us fix a positive integer N, this will be the input of the program. The structure to be studied has the underlying set {1,2,...,N}, from which we shall select elements i,j,k according to the rules below. The system will contain sets of the following five types:
(a) triplets {i,j,k} such that i+j=k ;
(b) triplets {i,j,k} such that i+j+k=2N+1 ;
(c) ordered pairs (i,j) such that 2i=j ;
(d) ordered pairs (i,j) such that 2i+j=2N+1 ;
(e) the singleton set {i} in case if 2N+1 is a multiple of 3, and 3i=2N+1 .

We are looking for sets S which do not contain any triplets of types (a) and (b), neither pairs of types (c) and (d), nor the element occurring in the case of (e), moreover the following conditions are met:
If the second element j of an ordered pair (i,j) of type (c) or (d) is in S, then i is contained in a triplet whose other two elements are in S, or if this is not the case then there exists an element i' in S for which (i',i) is a pair of type (c) or (d); moreover if 2N+1 is a multiple of 3, then the element i occurring in (e) is contained in a triplet whose other two elements are in S.
Under these conditions those sets S are of interest which are maximal under inclusion.

As an example, if N=8 then S={1,3,5} is such a set, because the missing 2 and 6 occur as second members in pairs of type (c) where i=1 or i=3, the missing 4 and 8 occur in the triplets (1,3,4) and (3,5,8) of type (a), and the missing 7 occurs in the pair (5,7) of type (d). On the other hand, not all N admit such a set S, an example is N=3.

The program has to solve the following tasks, the optional ones may be omitted:
* given N, generate the triplets and pairs of the system, and also the element of type (e) when applicable;
* display the directed graph whose edges are the ordered pairs of the system, placing the elements in the vertices of a regular N-gon, and maybe drawing the same graph decomposed into its cycles also;
* determine the possible numbers of elements in those sets S which are maximal under inclusion with respect to the prescribed properties, and give a possible set S for each size;
* indicate if such a set S does not exist for the given N;
* perhaps for the possible numbers of elements, list all sets S of that size upon request;
* design a GUI which displays the results and also gives regularly updated information about the situation of the program during the run.