Completions of epsilon-dense partial Latin squares

A classical question in combinatorics is the following: given a partial Latin square $P$, when can we complete $P$ to a Latin square $L$? In this paper, we investigate the class of textbf{$epsilon$-dense partial Latin squares}: partial Latin squares in which each symbol, row, and column contains no more than $epsilon n$-many nonblank cells. Based on a conjecture of Nash-Williams, Daykin and H"aggkvist conjectured that all $frac{1}{4}$-dense partial Latin squares are completable. In this paper, we will discuss the proof methods and results used in previous attempts to resolve this conjecture, introduce a novel technique derived from a paper by Jacobson and Matthews on generating random Latin squares, and use this novel technique to study $ epsilon$-dense partial Latin squares that contain no more than $delta n^2$ filled cells in total.

In Chapter 2, we construct completions for all $ epsilon$-dense partial Latin squares containing no more than $delta n^2$ filled cells in total, given that $epsilon < frac{1}{12}, delta < frac{ left(1-12epsilonright)^{2}}{10409}$. In particular, we show that all $9.8 cdot 10^{-5}$-dense partial Latin squares are completable. In Chapter 4, we augment these results by roughly a factor of two using some probabilistic techniques. These results improve prior work by Gustavsson, which required $epsilon = delta leq 10^{-7}$, as well as Chetwynd and H"aggkvist, which required $epsilon = delta = 10^{-5}$, $n$ even and greater than $10^7$.

If we omit the probabilistic techniques noted above, we further show that such completions can always be found in polynomial time. This contrasts a result of Colbourn, which states that completing arbitrary partial Latin squares is an NP-complete task. In Chapter 3, we strengthen Colbourn's result to the claim that completing an arbitrary $left(frac{1}{2} + epsilonright)$-dense partial Latin square is NP-complete, for any $epsilon > 0$.

Colbourn's result hinges heavily on a connection between triangulations of tripartite graphs and Latin squares. Motivated by this, we use our results on Latin squares to prove that any tripartite graph $G = (V_1, V_2, V_3)$ such that begin{itemize} item $|V_1| = |V_2| = |V_3| = n$, item For every vertex $v in V_i$, $deg_+(v) = deg_-(v) geq (1- epsilon)n,$ and item $|E(G)| > (1 - delta)cdot 3n^2$ end{itemize} admits a triangulation, if $epsilon < frac{1}{132}$, $delta < frac{(1 -132epsilon)^2 }{83272}$. In particular, this holds when $epsilon = delta=1.197 cdot 10^{-5}$.

This strengthens results of Gustavsson, which requires $epsilon = delta = 10^{-7}$.

In an unrelated vein, Chapter 6 explores the class of textbf{quasirandom graphs}, a notion first introduced by Chung, Graham and Wilson cite{chung1989quasi} in 1989. Roughly speaking, a sequence of graphs is called "quasirandom"' if it has a number of properties possessed by the random graph, all of which turn out to be equivalent. In this chapter, we study possible extensions of these results to random $k$-edge colorings, and create an analogue of Chung, Graham and Wilson's result for such colorings.

Combinatória: abordagem precisa

O objetivo central deste projeto é precisar matematicamente certos objetos combinatórios que servem como ponto de partida nas apresentações usuais da Análise Combinatória e são comumente apresentados de maneira informal e intuitiva. Estabelecido este referencial teórico preciso, pretendemos, a partir dele, reapresentar os conceitos de Análise Combinatória de modo mais rigoroso privilegiando sempre a apresentação mais natural possível. Mais precisamente, estaremos interessados em reapresentar os resultados referentes ao capítulo dois do livro do professor Augusto C. Morgado a partir de uma versão matematicamente mais precisa dos Princípios Aditivo e Multiplicativo. Além disso, pretendemos que os argumentos usados em nossas deduções usem predominantemente indução ou construção de bijeções, o que é um dos grandes objetos de estudo da combinatória moderna

Free Indexation: Combinatorial Analysis and a Compositional Algorithm

In the principles-and-parameters model of language, the principle known as "free indexation'' plays an important part in determining the referential properties of elements such as anaphors and pronominals. This paper addresses two issues. (1) We investigate the combinatorics of free indexation. In particular, we show that free indexation must produce an exponential number of referentially distinct structures. (2) We introduce a compositional free indexation algorithm. We prove that the algorithm is "optimal.'' More precisely, by relating the compositional structure of the formulation to the combinatorial analysis, we show that the algorithm enumerates precisely all possible indexings, without duplicates.

The Effect of Indexing on the Complexity of Object Recognition

Many current recognition systems use constrained search to locate objects in cluttered environments. Previous formal analysis has shown that the expected amount of search is quadratic in the number of model and data features, if all the data is known to come from a sinlge object, but is exponential when spurious data is included. If one can group the data into subsets likely to have come from a single object, then terminating the search once a "good enough" interpretation is found reduces the expected search to cubic. Without successful grouping, terminated search is still exponential. These results apply to finding instances of a known object in the data. In this paper, we turn to the problem of selecting models from a library, and examine the combinatorics of determining that a candidate object is not present in the data. We show that the expected search is again exponential, implying that naﶥ approaches to indexing are likely to carry an expensive overhead, since an exponential amount of work is needed to week out each of the incorrect models. The analytic results are shown to be in agreement with empirical data for cluttered object recognition.

The Geometry of Frequency Squares

Mavron, Vassili; Jungnickel, D.; McDonough, T.P., (2001) 'The Geometry of Frequency Squares', Journal of Combinatorial Theory, Series A 96, pp.376-387 RAE2008

Quasi -symmetric designs with good blocks and intersection number one

Mavron, Vassili; McDonough, T.P.; Schrikhande, M.S., (2003) 'Quasi -symmetric designs with good blocks and intersection number one', Designs Codes and Cryptography 28(2) pp.147-162 RAE2008

Information sets and partial permutation decoding for codes from finite geometries

Mavron, Vassili; McDonough, T.P.; Key, J.D., (2006) 'Information sets and partial permutation decoding for codes from finite geometries', Finite Fields and their applications 12(2) pp.232-247 RAE2008

Non-tactical symmetric nets

Mavron, Vassili; Al-Kenani, A.N., (2003) 'Non-tactical symmetric nets', Journal of the London Mathematical Society 67(2) pp.273-288 RAE2008

Covering Partial Cubes with Zones

http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p31

Performance assessment in serious games: Compensating for the effects of randomness

This paper is about performance assessment in serious games. We conceive serious gaming as a process of player-lead decision taking. Starting from combinatorics and item-response theory we provide an analytical model that makes explicit to what extent observed player performances (decisions) are blurred by chance processes (guessing behaviors). We found large effects both theoretically and practically. In two existing serious games random guess scores were found to explain up to 41% of total scores. Monte Carlo simulation of random game play confirmed the substantial impact of randomness on performance. For valid performance assessments, be it in-game or post-game, the effects of randomness should be included to produce re-calibrated scores that can reasonably be interpreted as the players´ achievements.

Two-dimensional Banach spaces with polynomial numerical index zero

We study two-dimensional Banach spaces with polynomial numerical indices equal to zero.

A bargaining set for monotonic simple games based on external and internal stability

A new bargaining set based on notions of both internal and external stability is developed in the context of endogenous coalition formation. It allows to make an explicit distinction between within-group and outside-group deviation options. This type of distinction is not present in current bargaining sets. For the class of monotonic proper simple games, the outcomes in the bargaining set are characterized. Furthermore, it is shown that the bargaining set of any homogeneous weighted majority game contains an outcome for which the underlying coalition structure consists of a minimal winning coalition and its complement.