Forbidden and Colored Subgraphs

禁止和彩色子图

• 批准号: 2247013
• 负责人: Liana Yepremyan
• 金额: $ 21万
• 依托单位: Emory University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-07-01 至 2026-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2247013&HistoricalAwards=false
• 关键词: Forbidden; Colored; Subgraphs

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.

n x n拉丁正方形是一个n乘n正方形，填充了n个不同的符号，每个符号正好在每个行和列中恰好发生一次。这个定义可能会提醒读者一个名为“ sudoku”的众所周知的难题，该难题是9 x 9乘9的拉丁正方形，并具有一些其他约束。拉丁正方形的研究可以追溯到1700年代。拉丁正方形与数学各个子场有连接。例如，它们是来自代数的准群的乘法表，当一个人希望通过嘈杂的通道（例如电源线）等传输数据时，它们被用作错误校正代码。这样的细胞收集称为横向。相比之下，无法在两个乘两个拉丁正方形中找到横向。 1960年代，由于Ryser的著名缔约方宣称，对于奇数N，总是有可能在N Latin Square中找到横向。在图理论语言中，这相当于在适当边缘色的完整的两部分图中找到所谓的彩虹匹配的问题，其分区大小等于n。该项目旨在探索与在彩色图中找到某些彩虹结构有关的各种问题。当前的项目虽然在组合上陈述，但它与其他数学领域（例如离散的几何图形和代数）具有连接，解决方案可能涉及一些代数和概率方法的使用，从而在组合剂和其他数学领域之间建立进一步的联系。研究生将作为该项目的一部分进行培训。在这个项目中，我们将探讨与彩色图中各种跨越和非跨性彩色结构存在有关的问题。彩色图的彩虹子图是每个边缘具有独特颜色的子图。我们计划讨论具有两个共同主题的问题。第一个是了解对象的结构和属性，例如图形，因为它不包含某些禁止的子观测值，例如彩虹子图。这些可以看作是适合彩色设置的turan型问题，在这里，人们想在其中找到最大的边缘数量，而在给定数量的顶点上，不包含固定的彩虹子图片。我们将研究的第二种问题是在彩色图具有某些跨度或几乎跨越的彩虹子图的限制下，例如长期或哈密顿路径，跨越或几乎跨越树木，完美或几乎完美的匹配。要研究的问题包括但不限于图表中存在大彩虹匹配，在超图中存在较大的匹配项，存在矢量空间和矩形的彩虹基地的存在，turan型问题，turan型问题以及他们的彩虹类似物，以及他们的启发性奖励，以表现出nsf的宣传和依据。更广泛的影响审查标准。