Forbidden and Colored Subgraphs

一个n × n的拉丁方框是一个n × n的方框，里面有n个不同的符号，每个符号在每一行和每一列中只出现一次。这个定义可能会让读者想起一个众所周知的叫做“数独”的谜题，它是一个9乘9的拉丁方块，加上一些额外的限制。对拉丁方格的研究可以追溯到18世纪欧拉的作品。拉丁平方与数学的各个子领域都有联系。例如，它们是代数中准群的乘法表，当人们希望通过诸如电力线等噪声信道传输数据时，它们被用作纠错码。无论如何填充一个3 × 3的拉丁方格，总是可以选择三个单元格，其中没有两个单元格共用一行、一列或一个符号。这样的细胞集合称为截线。相反，在2 × 2的拉丁正方形中不可能找到截线。赖泽在20世纪60年代提出的一个著名猜想断言，对于奇数n，总有可能在n × n的拉丁方中找到截线。在图论语言中，这相当于在一个分区大小等于n的适当边缘彩色完全二部图中寻找所谓的彩虹匹配问题。本项目旨在探索在彩色图中寻找某些彩虹结构的各种问题。当前的项目，虽然组合陈述，有连接到其他数学领域，如离散几何和代数，解决方案可能会涉及到一些代数和概率方法的使用，从而创建组合学和其他数学领域之间的进一步联系。研究生将作为这个项目的一部分接受培训。在这个项目中，我们将探讨与彩色图中各种生成和非生成彩色结构的存在性有关的问题。彩色图的彩虹子图是每条边都有不同颜色的子图。我们计划研究有两个共同主题的问题。第一个是理解一个对象的结构和属性，例如，一个图，假设它不包含一些禁止的子对象，例如，彩虹子图。这些可以被看作是适合于彩色设置的图兰型问题，在这里，人们想要找到，比如说，在给定数量的顶点上，在不包含固定彩虹子图的情况下，在一个适当的边缘彩色图中，边的最大数量。我们要研究的第二类问题是找出在什么限制下一个彩色图具有一定的生成或几乎生成的彩虹子图，如长路径或哈密顿路径，生成树或几乎生成树，完美匹配或几乎完美匹配。研究的问题包括但不限于图中大彩虹匹配的存在性、超图中大彩虹匹配的存在性、向量空间和拟阵中彩虹基的存在性、图兰型问题及其彩虹类似问题，如有理性数作为图兰指数的出现。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

An n by n Latin square is an n by n 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 9 by 9 Latin square with some additional constraints. The study of Latin squares dates back to the 1700s to the work of Euler. Latin squares have connections to various subfields in mathematics. For example, they are multiplication tables of quasigroups from algebra, they are used as error-correcting codes when one wishes to transmit data via a noisy channel such as power lines, etc. No matter how one fills a 3 by 3 Latin square, it is always possible to pick three cells, no two of which share a row, a column or a symbol. Such a collection of cells is called a transversal. In contrast, it is not possible to find a transversal in a two by two 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 n by n Latin square. In the graph theoretic language, this is equivalent to the problem of finding a so-called rainbow matching in a properly edge-colored complete bipartite graph with partition sizes equal to n. This project aims to explore various problems which are related to finding certain rainbow structures in colored graphs. The current project, while combinatorially stated, has connections to other fields of mathematics, such as discrete geometry and algebra, and solutions will likely involve some use of algebraic and probabilistic methods thus creating further connections between combinatorics and other fields of mathematics. Graduate students will be trained as part of this project.In this project we will explore questions related to the existence of various spanning and non-spanning colored structures in colored graphs. A rainbow subgraph of a colored graph is a subgraph in which each edge has a distinct color. We plan to work on questions that have two common themes at heart. The first one is understanding the structure and properties of an object, for example, a graph, given it does not contain some forbidden sub-object, for example, a rainbow subgraph. These can be viewed as Turan-type problems adapted to the colored setting, where one wants to find, say the maximum number of edges in a properly edge-colored graph on a given number of vertices without containing a fixed rainbow subgraph. The second type of problems we will study is to find out under what restrictions a colored graph has certain spanning or almost-spanning rainbow subgraphs, such as long or Hamiltonian paths, spanning or almost spanning trees, a perfect or almost perfect matching. The problems to study include but are not limited to the existence of large rainbow matchings in graphs, existence of large matchings in hypergraphs, the existence of rainbow bases for vector spaces and matroids, Turan-type problems and their rainbow analogues such as the appearance of a rational number as a Turan exponent.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.