论文标题
线图的H份
The H-property of Line Graphons
论文作者
论文摘要
我们在本文中探索了足够的条件，可以持有$ h $ property，并特别关注所谓的线图。 GraphOn是单位方形$ [0,1]^2 $的对称，可测量的功能，封闭间隔$ [0,1] $。图形可以用于采样随机图，如果从中采样的$ n $ nodes上的图形在$ n $ nodes上进行图形，则具有$ h $ property，这承认是由discoint Cycles covers cover cover-node-cover-node cover-node cover cover被称为汉密尔顿分解 - 几乎肯定是$ n \ to \ n \ to \ infty $。阶梯式图是一个图形，它是域中的矩形上的分段常数。对于一个阶梯键，我们分配了两个对象：它的浓度向量，编码矩形的区域及其骨架图，描述了它们的支撑。这两个对象在我们的早期工作中使用[3]来确定阶梯式施法的必要条件，使其具有$ h $ property。在本文中，我们证明这些条件本质上也足以满足线圈类别的类别，即，骨骼图的阶梯图是终点节点上的self loop的线图。我们还调查了既不能满足必要条件和足够条件的边界案例。
We explore in this paper sufficient conditions for the $H$-property to hold, with a particular focus on the so-called line graphons. A graphon is a symmetric, measurable function from the unit square $[0,1]^2$ to the closed interval $[0,1]$. Graphons can be used to sample random graphs, and a graphon is said to have the $H$-property if graphs on $n$ nodes sampled from it admit a node-cover by disjoint cycles -- such a cover is called a Hamiltonian decomposition -- almost surely as $n \to \infty$. A step-graphon is a graphon which is piecewise constant over rectangles in the domain. To a step-graphon, we assign two objects: its concentration vector, encoding the areas of the rectangles, and its skeleton-graph, describing their supports. These two objects were used in our earlier work [3] to establish necessary conditions for a step-graphon to have the $H$-property. In this paper, we prove that these conditions are essentially also sufficient for the class of line-graphons, i.e., the step-graphons whose skeleton graphs are line graphs with a self-loop at an ending node. We also investigate borderline cases where neither the necessary nor the sufficient conditions are met.
