Combinatorial Aspects of Discrete Structures - Graphs and Latin Squares

Discrete structures are fundamental to both mathematics and computer science, serving as the basis for numerous computational and algorithmic frameworks. This dissertation explores two key areas where combinatorial methods provide deep insights into the properties and applications of discrete structures: combinatorial topology in graph theory and cellular automata (CA)-based Latin squares in cryptography. In the first part, we investigate eulerian magnitude homology, a novel extension of standard magnitude homology, and its application to Erdos-Rényi random graphs and random geometric graphs. We develop new tools, including the eulerian Asao-Izumihara complex, to study torsion in these homology groups and establish conditions under which the eulerian magnitude homology of Erd ̋os-Rényi random graphs is torsion-free. Additionally, we introduce an efficient algorithm to compute the ranks of first-diagonal eulerian magnitude homology groups, proving its computational complexity. The second part of the dissertation shifts focus to cellular automata (CA), where we explore their use in generating Latin squares through bipermutive rules. These CA-based Latin squares find applications in cryptography, particularly in designing secure cryptographic functions and correlation-immune functions for coding theory. This thesis demonstrates how discrete mathematical structures, through combinatorial techniques, contribute to both theoretical advancements and practical applications in modern computation and cryptography.

Discrete structures are fundamental to both mathematics and computer science, serving as the basis for numerous computational and algorithmic frameworks. This dissertation explores two key areas where combinatorial methods provide deep insights into the properties and applications of discrete structures: combinatorial topology in graph theory and cellular automata (CA)-based Latin squares in cryptography. In the first part, we investigate eulerian magnitude homology, a novel extension of standard magnitude homology, and its application to Erdos-Rényi random graphs and random geometric graphs. We develop new tools, including the eulerian Asao-Izumihara complex, to study torsion in these homology groups and establish conditions under which the eulerian magnitude homology of Erd ̋os-Rényi random graphs is torsion-free. Additionally, we introduce an efficient algorithm to compute the ranks of first-diagonal eulerian magnitude homology groups, proving its computational complexity. The second part of the dissertation shifts focus to cellular automata (CA), where we explore their use in generating Latin squares through bipermutive rules. These CA-based Latin squares find applications in cryptography, particularly in designing secure cryptographic functions and correlation-immune functions for coding theory. This thesis demonstrates how discrete mathematical structures, through combinatorial techniques, contribute to both theoretical advancements and practical applications in modern computation and cryptography.