论文标题
边界阈值维度：实现图形布尔作为多数门的功能
Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates
论文作者
论文摘要
A graph $G$ on $n$ vertices is a \emph{threshold graph} if there exist real numbers $a_1,a_2, \ldots, a_n$ and $b$ such that the zero-one solutions of the linear inequality $\sum \limits_{i=1}^n a_i x_i \leq b$ are the characteristic vectors of the cliques of $G$.在[CHV {á} Tal和Hammer，离散数学年鉴中引入的，1977年]，图$ g $的\ emph {阈值dimension}，由$ \ dimth（g）$表示，是其相互作用的最小阈值图的最小数量。给定$ n $顶点上的图形$ g $，与chv {Á} tal and Hammer一致，$ f_g \ colon \ {0,1 \}^n \ rightArrow \ rightArow \ {0,1 \} $是布尔函数，具有$ f_g（x）= 1 $ f_g（x）= 1 $ x $ x $的属性，仅$ x $ cltector $ x $ callique cltariquest。存在图$ g $的布尔函数$ f $，以便$ f = f_g $称为\ emph {graphic} boolean函数。因此，对于图形$ g $，$ \ dimth（g）$恰恰是\ emph {多数}门的最小数量，其和（或连接）意识到图形布尔函数$ f_g $。存在布尔函数的事实，可以将其实现为且指数级的许多大门促使我们研究图形的阈值维度。我们在图形的阈值尺寸上给出了紧密或几乎紧密的上限，其树宽度，最大程度，退化，顶点数，最小顶点盖的大小等。我们还研究了随机图的阈值尺寸和较高的围程的阈值。
A graph $G$ on $n$ vertices is a \emph{threshold graph} if there exist real numbers $a_1,a_2, \ldots, a_n$ and $b$ such that the zero-one solutions of the linear inequality $\sum \limits_{i=1}^n a_i x_i \leq b$ are the characteristic vectors of the cliques of $G$. Introduced in [Chv{á}tal and Hammer, Annals of Discrete Mathematics, 1977], the \emph{threshold dimension} of a graph $G$, denoted by $\dimth(G)$, is the minimum number of threshold graphs whose intersection yields $G$. Given a graph $G$ on $n$ vertices, in line with Chv{á}tal and Hammer, $f_G\colon \{0,1\}^n \rightarrow \{0,1\}$ is the Boolean function that has the property that $f_G(x) = 1$ if and only if $x$ is the characteristic vector of a clique in $G$. A Boolean function $f$ for which there exists a graph $G$ such that $f=f_G$ is called a \emph{graphic} Boolean function. It follows that for a graph $G$, $\dimth(G)$ is precisely the minimum number of \emph{majority} gates whose AND (or conjunction) realizes the graphic Boolean function $f_G$. The fact that there exist Boolean functions which can be realized as the AND of only exponentially many majority gates motivates us to study threshold dimension of graphs. We give tight or nearly tight upper bounds for the threshold dimension of a graph in terms of its treewidth, maximum degree, degeneracy, number of vertices, size of a minimum vertex cover, etc. We also study threshold dimension of random graphs and graphs with high girth.
