Taraz, AnuschAnuschTaraz12169240XAscolese, MichelaMichelaAscolese2025-03-102025-03-102025Technische Universiät Hamburg (2025)https://hdl.handle.net/11420/54556This thesis covers four topics within the wide area of Discrete Mathematics: for each of them, we investigate a different open problem and contribute to its solution. Even if they could appear different at first glance, the leitmotif that connects all of them is the definition of inverse problems concerning discrete structures, represented as subsets of points of $\mathbb{Z}^{2}$ or as matrices having integer or binary entries. At first, we focus our attention on an inverse problem classically studied in the field of Discrete Tomography, that is, the reconstruction of an unknown (discrete) object starting from partial information on it. Usually, the interior of the object is supposed to be inaccessible, and the information is acquired by means of X-rays, mathematically modeled by discrete lines in $\mathbb{Z}^{2}$, and addressed as \emph{projections}, while the object to be reconstructed is modeled as a set of points of the discrete plane, or, equivalently, as a binary image that is represented through a binary matrix. The main drawback in the reconstruction process is that in most cases the acquired information is not sufficient for the faithful determination of the unknown image, meaning that, given a set of discrete directions in $\mathbb{Z}^{2}$, there exist in general different objects having the same projections along such directions, and so the reconstruction problem is ill-posed. The problem we consider in this thesis is the determination of sets of directions satisfying the uniqueness property, meaning that, when we collect the projections along the directions of such sets, a binary image can always be reconstructed with no ambiguities. We then move from the field of Discrete Tomography to the field of Graph Theory, where a similar inverse problem is defined: the reconstruction of a simple (hyper)graph starting from the knowledge of its degree sequence and of the cardinalities of its (hyper)edges. In the previous perspective, this is equivalent to the reconstruction of a binary matrix, specifically, the incidence matrix that is used to represent a hypergraph, starting from its horizontal and vertical projections, with the further constraint that all the rows of the matrix are required to be distinct. This last condition makes the reconstruction problem to be NP-hard, so that our research consists of the investigation of instances for which a solution can be easily and quickly detected. We also consider the inverse problem of reconstructing a generic set of points in $\mathbb{Z}^{2}$ using a generalized notion of projection introduced by Maurice Nivat: instead of considering discrete lines, so \emph{linear} projections, we collect the projections using bi-dimensional windows. In this sense, we fix a finite connected set of positions in $\mathbb{Z}^{2}$, called \emph{polyomino}, and we move it on the discrete plane taking note of the number of points that lie inside it, in order to detect the presence of the points of the set we want to reconstruct. In this case, a special role is played by exact polyominoes, i.e., those polyominoes that can be used to tile the discrete plane by translation. In the last part of the thesis, we move apart from inverse problems and we focus our attention on exact polyominoes. We consider a special class of them, called \emph{prime double squares}, and we carry on the study of a conjecture proposed by Blondin Massé et al. in~2013. We provide a solution for it, relying on tools from Combinatorics on words. We conclude by presenting some results that may constitute a step ahead the exhaustive generation and enumeration of the class of prime double square polyominoes.Diese Arbeit behandelt vier Themen aus dem Bereich der diskreten Mathematik. Für jedes von ihnen untersuchen wir ein anderes offenes Problem und tragen zu seiner Lösung bei. Auch wenn die Themenbereiche auf den ersten Blick unterschiedlich erscheinen mögen, ist das Leitmotiv, welches alle verbindet, die Definition inverser Probleme bezüglich diskreter Strukturen, dargestellt als Teilmengen von Punkten von Z² oder als Matrizen mit ganzzahligen oder binären Einträgen. Zunächst konzentrieren wir uns auf ein inverses Problem, das klassisch im Bereich der diskreten Tomographie angesiedelt ist, d. h. die Rekonstruktion eines unbekannten (diskreten) Objekts ausgehend von Teilinformationen über dieses. Dann bewegen wir uns in den Bereich der Graphentheorie, wo wir ein ähnlich Problem untersuchen: die Rekonstruktion eines einfachen (Hyper-)Graphen, von welchem die Gradfolge sowie die Kardinalitäten seiner (Hyper-)Kanten bekannt sind. Wir betrachten auch das inverse Problem der Rekonstruktion einer generischen Menge von Punkten in Z² unter Verwendung eines verallgemeinerten Konzepts der Projektion, das von Maurice Nivat eingeführt wurde: Anstatt diskrete Linien, also lineare Projektionen, zu betrachten, erfassen wir die Projektionen mithilfe zweidimensionaler Fenster. Im letzten Teil der Arbeit entfernen wir uns von inversen Problemen und untersuchen stattdessen exakte Polyominos. Wir betrachten eine spezielle Klasse davon, die prime double squares genannt wird, und setzen die Untersuchung einer Vermutung fort, die Blondin Massé et al. im Jahr 2013 vorgeschlagen haben. Wir stellen eine Lösung dafür vor, welche auf Werkzeugen aus der Kombinatorik mit Wörtern beruht. Abschließend präsentieren wir einige Ergebnisse, welche einen weiteren Schritt bei der erschöpfenden Generierung und Aufzählung der Klasse der prime double square Polyominos beitragen können.enhttps://creativecommons.org/licenses/by/4.0/Discrete GeometryInverse problemsUniqueness of reconstructionUniform hypergraphExact polyominoNatural Sciences and Mathematics::510: MathematicsNatural Sciences and Mathematics::519: Applied Mathematics, ProbabilitiesTechnology::621: Applied Physics::621.3: Electrical Engineering, Electronic EngineeringDoctoral Thesishttps://doi.org/10.15480/882.1486410.15480/882.14864Gerard, YanYanGerardHajdu, LajosLajosHajduOther