论文标题
解决katona问题的解决方案
Solution to a problem of Katona on counting cliques of weighted graphs
论文作者
论文摘要
图$ g $的顶点套装$ v（g）的子集$ i $称为$ k $ clique独立套装$ g $的$ g $，如果$ k $ i $ in $ i $ $ i $ a $ k $ -clique的$ k $ clique的$ g $。独立套件是$ 2 $ -Clique Independent Set。令$π_k（g）$表示$ g $的$ k $ cliques的数量。对于函数$ w：v（g）\ rightarrow \ {0，1，2，\ dots \} $，让$ g（w）$是从$ g $获得的图表，将每个顶点$ v $替换为$ w（v）$ - clique $ k^v $，每个顶点$ k^u $ k^u $ k^u $ k^u k^U $ k^$ k^v $ k^v v vertex a $ \ {u，v \} $ $ g $。对于整数$ m \ geq 1 $，请考虑使用$ \ sum_ {v \ in V（g）} w（v）= m $的任何$ w $。对于$ u \ subseteq v（g）$，我们说$ w $在$ u $上是均匀的，如果$ w（v）= 0 $ in v（g）\ setMinus u $ in v（g）\ setMinus u $，并且对于u $ u $ u $，$ w（$ w（u）的每个$ u \ w（u） \ right \ rfloor $或$ w（u）= \ left \ lceil m/| u | \ right \ rceil $。卡托纳（Katona）询问$π_k（g（w））$是否最小，当$ w $在最大的$ k $ clique独立套件上是$ g $的均匀。他特别强调了Sperner Graph $ b_n $，由$ v（b_n）= \ {x \ colon x \ subseteq \ {1，\ dots，n \} \} $ and $ e（b_n）= \ {\ {\ {x，y \} \ colon x \ subseT \ n \ s $他提供了$ k = 2 $（和任何$ g $）的肯定答案。我们确定每个$ k \ geq 3 $的答案为负的图形。其中包括$ n \ geq 2 $的$ b_n $。概括了Sperner的定理以及Qian，Engel和Xu的最新结果，我们表明$π_k（b_n（w））$是最大的$ w $在最大的独立套装$ b_n $上时最小的。我们还表明，对于完整的多方图和弦图，相同的保留也相同。我们表明，使用Bohman在无三角形图上的深层结果，并非每个图形都是如此。
A subset $I$ of the vertex set $V(G)$ of a graph $G$ is called a $k$-clique independent set of $G$ if no $k$ vertices in $I$ form a $k$-clique of $G$. An independent set is a $2$-clique independent set. Let $π_k(G)$ denote the number of $k$-cliques of $G$. For a function $w: V(G) \rightarrow \{0, 1, 2, \dots\}$, let $G(w)$ be the graph obtained from $G$ by replacing each vertex $v$ by a $w(v)$-clique $K^v$ and making each vertex of $K^u$ adjacent to each vertex of $K^v$ for each edge $\{u,v\}$ of $G$. For an integer $m \geq 1$, consider any $w$ with $\sum_{v \in V(G)} w(v) = m$. For $U \subseteq V(G)$, we say that $w$ is uniform on $U$ if $w(v) = 0$ for each $v \in V(G) \setminus U$ and, for each $u \in U$, $w(u) = \left\lfloor m/|U| \right\rfloor$ or $w(u) = \left\lceil m/|U| \right\rceil$. Katona asked if $π_k(G(w))$ is smallest when $w$ is uniform on a largest $k$-clique independent set of $G$. He placed particular emphasis on the Sperner graph $B_n$, given by $V(B_n) = \{X \colon X \subseteq \{1, \dots, n\}\}$ and $E(B_n) = \{\{X,Y\} \colon X \subsetneq Y \in V(B_n)\}$. He provided an affirmative answer for $k = 2$ (and any $G$). We determine graphs for which the answer is negative for every $k \geq 3$. These include $B_n$ for $n \geq 2$. Generalizing Sperner's Theorem and a recent result of Qian, Engel and Xu, we show that $π_k(B_n(w))$ is smallest when $w$ is uniform on a largest independent set of $B_n$. We also show that the same holds for complete multipartite graphs and chordal graphs. We show that this is not true of every graph, using a deep result of Bohman on triangle-free graphs.
