TurantypeProblems · Turan-type problems for graphs and hypergraphs

Turan-type problems for graphs and hypergraphs

Advances in technology have called for the need to understand large complex networks. All networks in real world can be modeled using a graph or a hypergraph: individual objects are represented using nodes (vertices) while connections among groups of them are represented using subsets (hyperedges). For graphs, these connections are between pairs of nodes, while for hypergraphs any number of nodes can interact within each subgroup. What sort of substructures must be present in a network given we know how dense the network is? This is the general question that Turán-type problems address. In this project, we study two sets of problems; the first one is Turán-type extremal problems for graphs and hypergraphs, the second one is extremal problems in Latin squares and the existence of rainbow subgraphs in edge-coloured graphs. In Turán-type extremal problems, roughly speaking, we want to determine how dense a system (graph, hypergraph, set system, etc.) can be when certain subconfigurations are forbidden. Turán-type problems have played a central role in the development of extremal combinatorics, as studying these problems helps us to understand how local structures and their distribution throughout a system affect global parameters of the system. This has also its real-world applications as large networks arise frequently when we model real-world human activities (the web graph modeling the internet being one example). Studying and analyzing these networks contribute significantly to the efficiency and well-functioning of modern society. Pursuing Turán-type problems will also inspire new techniques with applications throughout discrete mathematics, since we are pushing extremal combinatorics into new and challenging directions. Throughout the course of more than sixty years, efforts to tackle these problems have led to the introduction of new and powerful tools that draw ideas from other branches of mathematics such as probability, algebra, geometry, number theory, and analysis. These tools have in return greatly propelled the developments of extremal combinatorics, which has applications in other fields of mathematics, such as number theory, additive combinatorics and in computer science, such as communication complexity, information theory and others. The second set of problems concerns Latin squares and rainbow subgraphs in graphs. An nxn Latin square is an nxn square filled with n different symbols, each of which occurs exactly once in each row and column. This definition might remind the reader of a commonly known puzzle called ‘sudoku’ which is a 9x9 Latin square with some additional constraints. The study of Latin squares is very old; it dates back to the 1700s to the work of the famous mathematician Leonard Euler. Latin squares have connections to various fields in mathematics. For example, they are multiplication tables of quasigroups from algebra. They are also used as error-correcting codes when, for example, one wishes to transmit data via a noisy channel, such as power lines. No matter how one fills a 3x3 Latin square, it is always possible to pick three cells no two of which share a row, column or symbol. Such a collection of cells is called a transversal. In contrast, it is not possible to find a transversal in a 2x2 Latin square. A famous conjecture from the 1960s due to Ryser asserts that for odd n, it is always possible to find a transversal in an nxn Latin square. In this project we study this and related problems. Progress on this question would lead to the development of new methods connecting combinatorics and algebra.

Текст от CORDIS, на английски · Данни: CORDIS, © Европейски съюз