5

Extremal solutions to some art gallery and terminal-pairability problems

The thesis consists of two parts. In both parts, the problems studied are of significant interest, but are either _NP_-hard or unknown to be polynomially decidable. Realistically, this forces us to relax the objective of optimality or restrict the …

Seating couples and Tic-Tac-Toe

We partially solve an additive combinatorial problem and then use it to construct optimal pairing strategies for certain generalised Tic-Tac-Toe games.

Combiantorial Nullstellensätze (in Hungarian)

Generalizations and applications of Alon's Nullstellensatz are discussed. Several proof techniques are collected, and a common generalization of two Nullstellensätze is given (though retrospectively this result is not useful at all).