论文标题
（广义）旋塞图的（广义）正交维度：边界和应用
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications
论文作者
论文摘要
图形$ g =（v，e）$的正交性维度是$ \ mathbb {f} $是最小的整数$ t $，在\ mathbb {f}^t $ in \ mathbb {f}^t $ in $ u_v，langle u_v，u_v，u_v，u_v，u_v，u_v，u_v，u_v，u_v，u_v，u_v $ v \ v \ v p $ v y n yneq in \ mathbb {f}^t $中的分配中$ \ langle u_v，u_ {v'} \ rangle = 0 $，nesh $ v $和$ v'$都是$ g $的相邻顶点。图表的正交维度的研究是由信息理论和理论计算机科学中的各种应用激励的。本工作的贡献是两个方面。 首先，我们证明存在一个常数的$ c $，以便对于每个足够大的整数$ t $，它是$ \ mathsf {np} $ - 很难确定输入图的正交性维度是$ \ m athbb {r} $的正交尺寸，最多是$ t $还是至少是$ 3T/2-C $。证明的核心是几何结果，可能具有独立感兴趣，这是对旋塞图家族的正交性维度参数的概括，类似于stahl的长期猜想（J.comb。theo。Ser。B，1976）。 其次，我们研究了不包含某些固定子图的图形的有限磁场上最小的正交性维度。特别是，我们提供了无三角形的$ n $ vertex图的明确结构，其补充具有正交性尺寸在二进制字段上最多$ n^{1-δ} $，对于某些常数$δ> 0 $。我们的结果涉及广义旋塞图家族的构造，它们是由电路下限的刚性方法激励的。我们使用它们来回答Codenotti，Pudlák和Resta（理论Comput。Sci。，2000）提出的几个问题，尤其是在每个有限领域都反驳了它们奇怪的交替猜想。
The orthogonality dimension of a graph $G=(V,E)$ over a field $\mathbb{F}$ is the smallest integer $t$ for which there exists an assignment of a vector $u_v \in \mathbb{F}^t$ with $\langle u_v,u_v \rangle \neq 0$ to every vertex $v \in V$, such that $\langle u_v, u_{v'} \rangle = 0$ whenever $v$ and $v'$ are adjacent vertices in $G$. The study of the orthogonality dimension of graphs is motivated by various applications in information theory and in theoretical computer science. The contribution of the present work is two-fold. First, we prove that there exists a constant $c$ such that for every sufficiently large integer $t$, it is $\mathsf{NP}$-hard to decide whether the orthogonality dimension of an input graph over $\mathbb{R}$ is at most $t$ or at least $3t/2-c$. At the heart of the proof lies a geometric result, which might be of independent interest, on a generalization of the orthogonality dimension parameter for the family of Kneser graphs, analogously to a long-standing conjecture of Stahl (J. Comb. Theo. Ser. B, 1976). Second, we study the smallest possible orthogonality dimension over finite fields of the complement of graphs that do not contain certain fixed subgraphs. In particular, we provide an explicit construction of triangle-free $n$-vertex graphs whose complement has orthogonality dimension over the binary field at most $n^{1-δ}$ for some constant $δ>0$. Our results involve constructions from the family of generalized Kneser graphs and they are motivated by the rigidity approach to circuit lower bounds. We use them to answer a couple of questions raised by Codenotti, Pudlák, and Resta (Theor. Comput. Sci., 2000), and in particular, to disprove their Odd Alternating Cycle Conjecture over every finite field.
