论文标题
在包含子图的k副本以及搜索理论中的相关问题的图表上
On graphs that contain exactly k copies of a subgraph, and a related problem in search theory
论文作者
论文摘要
我们研究$ \ mathrm {exa} _k（n，f）$，是$ n $ vertex Graph $ g $中最大的边缘，其中包含给定子图$ f $的$ k $副本。 $ k = 0 $是Turán数字$ \ MATHRM {ex}（n，f）$，它是极端图理论中研究最多的参数之一。我们表明，对于任何$ f $和$ k $，$ \ mathrm {exa} _k（n，f）=（1+o（1））\ mathrm {ex}（ex}（n，f））$，并确定$ \ mathrm {exa} _k（exa} _k（exa} _k（n，k_3）$ and $ n，$ n $ n $ n $ n $ n $ n $ n $ exa $ n $ n $ n $ exa $ n $ n $ rm {exa的确切值 足够的。我们还探索了与搜索理论中以下知名问题的联系。为我们提供了一个订单$ n $的图，该图由$ f $的未知副本和一些孤立的顶点组成。我们可以将成对的顶点作为查询，答案告诉我们这些顶点之间是否有优势。我们的目标是使用尽可能少的查询来描述该图。 Aigner和Triesch在1990年表明，所需的查询数量至少为$ \ binom {n} {2} {2} - \ Mathrm {exa} _1（n，f）$。在其他结果中，我们表明，回答否的查询数量至少是$ \ binom {n} {2} - \ mathrm {exa} _1（n，f）$。
We study $\mathrm{exa}_k(n,F)$, the largest number of edges in an $n$-vertex graph $G$ that contains exactly $k$ copies of a given subgraph $F$. The case $k=0$ is the Turán number $\mathrm{ex}(n,F)$ that is among the most studied parameters in extremal graph theory. We show that for any $F$ and $k$, $\mathrm{exa}_k(n,F)=(1+o(1))\mathrm{ex}(n,F))$ and determine the exact values of $\mathrm{exa}_k(n,K_3)$ and $\mathrm{exa}_1(n,K_r)$ for $n$ large enough. We also explore a connection to the following well-known problem in search theory. We are given a graph of order $n$ that consists of an unknown copy of $F$ and some isolated vertices. We can ask pairs of vertices as queries, and the answer tells us whether there is an edge between those vertices. Our goal is to describe the graph using as few queries as possible. Aigner and Triesch in 1990 showed that the number of queries needed is at least $\binom{n}{2}-\mathrm{exa}_1(n,F)$. Among other results we show that the number of queries that were answered NO is at least $\binom{n}{2}-\mathrm{exa}_1(n,F)$.
