(+36) 88 424 483

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

  

Thesis

Description of task:
A circular triple system of order n is a set system consisting of 3-element subsets over the set (0,1,...,n-1), such that if a triple (a,b,c) belongs to it, then it contains all triples of the form (a+i,b+i,c+i) (modulo n) for i=1,...,n-1. E.g. for n=5 one such system consists of the sets (0,1,2), (1,2,3), (2,3,4), (3,4,0), (4,0,1). Because of invariance under rotation, choosing c=0 we can describe such a system with the corresponding pairs (a,b), in our example it is (a,b)=(3,4). A program has to be developed, which supports the following operations for such systems:

  • reading input from an external file
  • for given integers n and k, random generation of a system described with exactly k pairs (a,b)
  • for given integers n and k, systematic and redundance-free generation of all systems described with exactly k pairs (a,b)
  • given a system of order n, and another of order m (m<n), decision of whether the smaller one is embeddable into the larger
  • conditional generating: construction of systems into which one or more given smaller systems cannot be embedded
  • extension of a system via GUI, by inseting a further pair (a,b); deciding embeddability into such an extended system
  • visual presentation of a given system
  • visual presentation of two systems side by side
  • deletion of one or more specified elements, visual presentation of the system obtained
  • determination of the smallest value t such that there exist t integers (x(0),x(1),...,x(t-1) -- one may assume x(0)=0) which contain at least one element from each triple of the system
  • determination of the largest value p such that there exists a patition of the set (0,1,...,n-1) in which each triple of the system is contained either in a single class or in the union of two classes
  • comparison of the parameters t and p above, also in systems modified by deletion


Supervisor: Zsolt Tuza

Contact address: