论文标题
图形的奇数封面
Odd Covers of Graphs
论文作者
论文摘要
鉴于有限的简单图$ g $，$ g $的奇数是完整的两部分图或双Qliques的集合，其中$ g $的每个边缘出现在一个奇数的二键中，$ g $的每个非边缘都出现在偶数bicliqliques中。我们表示$ g $ $ b_2（g）$的奇数封面的最低基数，并证明$ b_2（g）$在$ g $的邻接矩阵的$ \ mathbb {f} _2 $以下的一半以下。我们表明，在$ g $是两部分图的情况下，这种下限很紧，而当$ g $是一个奇怪的周期时，几乎很紧。但是，我们还提出了一个无限的图表，这表明该下限可以任意远离$ b_2（g）$。 Babai and Frankl（1992）提出了“奇数封面问题”，我们的语言等同于确定$ b_2（k_n）$。 Radhakrishnan，Sen和Vishwanathan（2000）确定了$ b_2（k_n）$，用于无限但密度为零的正整数子集$ n $。在本文中，我们确定$ b_2（k_n）$的密度$ 3/8 $子集的正整数子集。
Given a finite simple graph $G$, an odd cover of $G$ is a collection of complete bipartite graphs, or bicliques, in which each edge of $G$ appears in an odd number of bicliques and each non-edge of $G$ appears in an even number of bicliques. We denote the minimum cardinality of an odd cover of $G$ by $b_2(G)$ and prove that $b_2(G)$ is bounded below by half of the rank over $\mathbb{F}_2$ of the adjacency matrix of $G$. We show that this lower bound is tight in the case when $G$ is a bipartite graph and almost tight when $G$ is an odd cycle. However, we also present an infinite family of graphs which shows that this lower bound can be arbitrarily far away from $b_2(G)$. Babai and Frankl (1992) proposed the "odd cover problem," which in our language is equivalent to determining $b_2(K_n)$. Radhakrishnan, Sen, and Vishwanathan (2000) determined $b_2(K_n)$ for an infinite but density zero subset of positive integers $n$. In this paper, we determine $b_2(K_n)$ for a density $3/8$ subset of the positive integers.
