Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSylvester-Gallai for Arrangements of Subspaces
89
0
0.0
(
0
)
Added by
Guangda Hu
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this work we study arrangements of $k$-dimensional subspaces $V_1,ldots,V_n subset mathbb{C}^ell$. Our main result shows that, if every pair $V_{a},V_b$ of subspaces is contained in a dependent triple (a triple $V_{a},V_b,V_c$ contained in a $2k$-dimensional space), then the entire arrangement must be contained in a subspace whose dimension depends only on $k$ (and not on $n$). The theorem holds under the assumption that $V_a cap V_b = {0}$ for every pair (otherwise it is false). This generalizes the Sylvester-Gallai theorem (or Kellys theorem for complex numbers), which proves the $k=1$ case. Our proof also handles arrangements in which we have many pairs (instead of all) appearing in dependent triples, generalizing the quantitative results of Barak et. al. [BDWY-pnas]. One of the main ingredients in the proof is a strengthening of a Theorem of Barthe [Bar98] (from the $k=1$ to $k>1$ case) proving the existence of a linear map that makes the angles between pairs of subspaces large on average. Such a mapping can be found, unless there is an obstruction in the form of a low dimensional subspace intersecting many of the spaces in the arrangement (in which case one can use a different argument to prove the main theorem).
rate research
Read More
We study questions in incidence geometry where the precise position of points is `blurry (e.g. due to noise, inaccuracy or error). Thus lines are replaced by narrow tubes, and more generally affine subspaces are replaced by their small neighborhood. We show that the presence of a sufficiently large number of approximately collinear triples in a set of points in d dimensional complex space implies that the points are close to a low dimensional affine subspace. This can be viewed as a stable variant of the Sylvester-Gallai theorem and its extensions. Building on the recently found connection between Sylvester-Gallai type theorems and complex Locally Correctable Codes (LCCs), we define the new notion of stable LCCs, in which the (local) correction procedure can also handle small perturbations in the euclidean metric. We prove that such stable codes with constant query complexity do not exist. No impossibility results were known in any such local setting for more than 2 queries.
Given graphs $G$ and $H$ and a positive integer $k$, the emph{Gallai-Ramsey number}, denoted by $gr_{k}(G : H)$ is defined to be the minimum integer $n$ such that every coloring of $K_{n}$ using at most $k$ colors will contain either a rainbow copy of $G$ or a monochromatic copy of $H$. We consider this question in the cases where $G in {P_{4}, P_{5}}$. In the case where $G = P_{4}$, we completely solve the Gallai-Ramsey question by reducing to the $2$-color Ramsey numbers. In the case where $G = P_{5}$, we conjecture that the problem reduces to the $3$-color Ramsey numbers and provide several results in support of this conjecture.
Given a graph $G$ and a positive integer $k$, the emph{Gallai-Ramsey number} is defined to be the minimum number of vertices $n$ such that any $k$-edge coloring of $K_n$ contains either a rainbow (all different colored) copy of $G$ or a monochromatic copy of $G$. In this paper, we obtain general upper and lower bounds on the Gallai-Ramsey numbers for double stars $S(n,m)$, where $S(n,m)$ is the graph obtained from the union of two stars $K_{1,n}$ and $K_{1,m}$ by adding an edge between their centers. We also provide the sharp result in some cases.
A Gallai coloring is an edge coloring that avoids triangles colored with three different colors. Given integers $e_1ge e_2 ge dots ge e_k$ with $sum_{i=1}^ke_i={n choose 2}$ for some $n$, does there exist a Gallai $k$-coloring of $K_n$ with $e_i$ edges in color $i$? In this paper, we give several sufficient conditions and one necessary condition to guarantee a positive answer to the above question. In particular, we prove the existence of a Gallai-coloring if $e_1-e_kle 1$ and $k le lfloor n/2rfloor$. We prove that for any integer $kge 3$ there is a (unique) integer $g(k)$ with the following property: there exists a Gallai $k$-coloring of $K_n$ with $e_i$ edges in color $i$ for every $e_1ledots le e_k$ satisfying $sum_{i=1}^ke_i={nchoose 2}$, if and only if $nge g(k)$. We show that $g(3)=5$, $g(4)=8$, and $2k-2le g(k)le 8k^2+1$ for every $kge 3$.
Given two graphs $G$ and $H$, the $k$-colored Gallai-Ramsey number $gr_k(G : H)$ is defined to be the minimum integer $n$ such that every $k$-coloring of the complete graph on $n$ vertices contains either a rainbow copy of $G$ or a monochromatic copy of $H$. In this paper, we consider $gr_k(K_3 : H)$ where $H$ is a connected graph with five vertices and at most six edges. There are in total thirteen graphs in this graph class, and the Gallai-Ramsey numbers for some of them have been studied step by step in several papers. We determine all the Gallai-Ramsey numbers for the remaining graphs, and we also obtain some related results for a class of unicyclic graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
