Exact enumeration of Hamiltonian circuits, walks, and chains in two and three dimensions

《无穷维Hamilton算子特征函数系的完备性及其在弹性力学中的应用》篇一摘要：本文研究无穷维Hamilton算子特征函数系的完备性，探讨了其在弹性力学中的具体应用。

通过深入分析Hamilton算子的基本性质，揭示了其特征函数系在弹性力学问题中的重要性。

同时，探讨了这一理论在实际问题中的实践应用，为弹性力学领域的研究提供了新的视角和思路。

一、引言随着现代数学物理的不断发展，Hamilton算子作为描述物理系统的重要工具，在各个领域都得到了广泛的应用。

特别是在弹性力学领域，Hamilton算子特征函数系的完备性对于描述和分析弹性体的力学行为具有重要意义。

本文旨在探讨无穷维Hamilton 算子特征函数系的完备性，并探讨其在弹性力学中的应用。

二、无穷维Hamilton算子及其特征函数系无穷维Hamilton算子是在Hamilton系统中用于描述动态平衡和演化规律的数学工具。

它包含了系统动力学的大部分信息，并通过其特征函数系将复杂的系统简化为一系列独立的简单系统。

其特征函数系具有完备性，即系统的所有可能状态都可以由这些特征函数线性表示。

三、特征函数系的完备性证明为了证明无穷维Hamilton算子特征函数系的完备性，我们首先需要明确其基本性质和定义。

通过构造一系列的数学命题和推导，我们可以证明这些特征函数在一定的条件下能够构成一个完备的函数系。

具体来说，我们可以通过分析这些函数的正交性、完备性和线性无关性等性质来证明其完备性。

四、在弹性力学中的应用在弹性力学中，无穷维Hamilton算子特征函数系的完备性为描述和分析弹性体的力学行为提供了有力的工具。

具体来说，我们可以利用这些特征函数来描述弹性体的振动模式、应力分布和变形行为等。

此外，这些特征函数还可以用于构建弹性力学问题的数值解法，如有限元法等。

通过将复杂的弹性力学问题转化为一系列简单的特征函数问题，我们可以更方便地求解和分析这些问题。

五、实例分析为了进一步说明无穷维Hamilton算子特征函数系在弹性力学中的应用，我们以一个具体的弹性力学问题为例进行分析。

一类三次多项式Hamilton系统的极限环分支杨军【摘要】主要研究了如下近似Hamilton系统{x=y y=-x3＋εQ（x,y）的极限环情况,其中Q（x,y）=∑lj=0 ajxj｜y｜2m.通过分析其一阶Melnikov函数,证明了当l=2n-2或2n-1时其存在n个极限环.%In this paper,we shall discuss a kind of near-Hamiltonian systems as follow：{x=y y=-x3＋εQ（x,y） Where Q（x,y）=∑l j=0 ajxj｜y｜2m,and investigate the bifurcation of limit cycles near the center by Melnikov function.Through analysing the first Melnikov function of the system,we prove that system exists n limit cycles when l=2n-2 or 2n-1.【期刊名称】《商丘师范学院学报》【年(卷),期】2011(027)009【总页数】3页(P20-22)【关键词】Hamilton系统;极限环;Abel积分;幂零中心【作者】杨军【作者单位】浙江师范大学数理与信息工程学院,浙江金华321004【正文语种】中文【中图分类】O175.12的极限环情况，其中.通过分析其一阶Melnikov函数，证明了当l=2n－2或2n－1时其存在n个极限环.由于Hamilton系统在非线性科学中占有重要地位，因此许多科学家利用不同的理论与方法多角度地考虑研究了此系统.设H(x，y)是关于(x，y)的实多项式，我们称具有如下形式的系统为平面多项式Hamilton系统:考虑(1)的扰动系统的极限环情况，其中P，Q是关于x，y的m次多项式，ε是小正参数.假设，当0＜h1时曲线H(x，y)=h在原点附近有闭轨Γh.考虑多项式1－形式:其中max(deg P，deg Q)=n≥2.对给定m和n，确定Abel积分的孤立零点的个数的最大值Z(m，n).上述Abel积分是指有理多项式1－形式沿代数闭曲线的积分.函数I(h)的实零点个数与系统(2)的极限环情况有着十分密切的联系.我们称上述Abel积分I(h)为系统(2)的一阶Melnikov函数.引理1［1］(1)若h=，0＜ε≪1时，H(x，y)=为系统(2)的闭轨，则必有I)=0; (2)若存在自然数k，使则存在σ＞0，δ＞0，使得当0＜|ε|＜σ时，系统(2)在Γh的δ邻域内至多有k个极限环.利用此函数研究系统(2)极限环分支情况，已有了丰富的研究结果与方法.文献［2－6］考虑原点为初等中心时系统(2)的极限环分支.对于原点为退化中心的情形也有了一些结论，文献［7－15］考虑原点为幂零中心时系统(2)的极限环分支情况. 本文研究系统的极限环情况，其中易见，当ε=0时，系统(3)是Hamilton系统，且Hamilton函数为:通过定性分析，我们知道，此时系统(3)的原点为幂零中心，且为全局中心.其相图见图1.我们考虑系统(3)的极限环情况.由引言，我们知道系统(3)的Abel积分为当l=2n－2或2n－1时，通过计算，得其中x1，x2为方程H(x，0)=h(h＞0)的两根，即为，任意h＞0，Γh与x轴的两个交点的横坐标，x1=－=－x.，且x12因为式变为令，则则其中是关于μ的n次多项式.因为且，则有下列引理引理2(1)h*∈(0，+∞)使得I(h*)=0，当且仅当存在μ*∈(0，+∞)使得A(μ*)=0，且μ*=;(2)I(h*)=0且I'(h*)＞0(＜0)当且仅当A(μ*)=0且A(μ*)＞0(＜0).定理1扰动系统(3)至多存在n个极限环.证明通过上述分析及引理(2)即可证得.Where，and investigate the bifurcation of limit cycles near the center by Melnikov function.Through analysing the first Melnikov function of the system，we prove that system exists n limit cycles when l=2n－2 or 2n－1.【相关文献】［1］张芷芬，李承治.向量场的分岔理论基础［M］.北京:高等教育出版社，1997.［2］Li J.Hilbert＇s 16th problem and bifurcations of planar ploynomial vector fileds ［J］.Inter.Jour.Bifur.＆Chaos，2003，13:1347－106.［3］Caubergh M，Dumortier F.Hopf－Takens bifurcations and centres［J］.J.Diff.Equs.，2004，202:1－31.［4］侯衍芬，韩茂安.平面近Hamilton系统的Melnikov函数与Hopf分支［J］.上海师范大学学报(自然科学版)，2006，1:1－10.［5］Han M.On Hopf cyclicity of planar systems［J］.J.M.A.A，2000，245:404－422. ［6］韩茂安.动力系统的周期解与分支理论［M］.北京:科学出版社，2002.253－268.［7］Andreev A F.Investigation of the behaveior of the integral curves of a system of two differential equations in the neighourhood of a singular point［J］.A.M.S.Transl.，1958，8:183－207.［8］Gasull A，Llibre J，Maosas V.The focus－centre problem for a type of degenerate system［J］.Nonlinearity，2000，13:699－729.［9］Hector G，Jaume G，Jaume L.The problem of distinguishing between a center and a focus for nilpotnet and degenerate analytic systems［J］.J.Diff.Equs.，2006，227:406－426.［10］lvarez M J，Gasull A.Monodromy and Stability for Nilpotent Critical Points ［J］.Inter.Jour.Bifur.＆Chaos，2005，15(4):1253－1265.［11］Jiang J，Han M.Melnikov function and limit cycle bifurcation from a nilpotent center［J］.Bulletin des Sciences Mathematiques，2008，132:182－193.［12］Han M，Jiang J，Zhu H.Limit cycle bifurcations in near－Hamiltonian systems by peryurbing a nilpotent center［J］.Inter.Jour.Bifur.＆Chaos，2008，10:3013－3027. ［13］江娇.平面系统的局部分支［D］，上海:上海交通大学，2007.［14］Álvarez M J，Gasull A.Generating limit cycles from a nilpotent critical point via normal form［J］.Journal of Mathematical Analysis and Applications，2006，318:271－287.［15］Han M，Shu C，Yang J，Chian A C L.Polynomial Hailtonian systems with a nilpotnet critical point［J］.Advances in Space Research，2010，46(4):521－525.。

哈密顿方法哈密顿方法，又称为Hamiltonian方法，是经典力学中用来描述物理系统动力学的一种方法，由爱德华·哈密顿（Edward Hamilton）在19世纪中期发明。

哈密顿方法是用来解决动力学问题的一种规范方法，它是基于特定原理和数学框架来构建物理模型的一种方法。

哈密顿方法的核心思想是用哈密顿函数（Hamiltonian）来描述物理系统，在这个函数的基础上，通过一个特定的形式来描述运动方程，使用哈密顿铁运动方程将物理系统的演化过程描述为一组动量方程和位置方程。

哈密顿方法的优点在于可以将形式简洁的哈密顿铁运动方程用于各种问题的求解，同时也提供了一种易于理解的物理解释。

另外，哈密顿方法还具有误差分析、稳定性分析等方面的优点。

哈密顿方法的基本概念包括哈密顿函数、哈密顿铁运动方程和哈密顿量子力学等。

下面将详细介绍这些概念和应用。

一、哈密顿函数哈密顿函数是哈密顿方法的起点和核心。

它是物理系统的一个数学描述，同时也是一个能量函数。

哈密顿函数的定义如下：H = ∑ p i q ˙ i - L ( q , q ˙ )其中，H是哈密顿函数；p是动量；q是位置；q˙是位置的一阶时间导数，L是拉格朗日函数。

从这个公式可以看到，哈密顿函数是由动量和位置两部分组成的。

动量是物理系统的关键参数之一，在哈密顿方法中，通过将物理系统的动量与位置分开来研究，我们可以得到系统的许多性质，例如能量守恒等。

同时，哈密顿函数也是一个能量函数，可以通过它计算物理系统的能量。

因此，它具有重要的物理意义和实用价值。

二、哈密顿铁运动方程哈密顿铁运动方程是描述物理系统演化过程的基本方程。

这个方程可以使用哈密顿函数来表达。

它由位置和动量分别构成的一组方程组成。

哈密顿铁运动方程的基本形式如下：这里，t是时间，q和p分别是位置和动量。

这个方程组可以解决各种物理问题，例如守恒定理、稳定性、非线性系统等。

三、哈密顿量子力学哈密顿量子力学是量子力学的一个分支，并与哈密顿方法紧密相关。

哈密尔顿环c算法全文共四篇示例，供读者参考第一篇示例：哈密尔顿环（Hamiltonian cycle）是图论中一个重要的概念，指的是图G中一条包含所有顶点且恰好经过一次的环。

哈密尔顿环问题是一个NP难题，即目前尚未找到有效的多项式时间算法来解决该问题。

寻找哈密尔顿环的有效算法一直是图论领域的热门研究方向之一。

在图论中，哈密尔顿环的存在性和性质一直备受关注。

给定一个图G，如果存在一个哈密尔顿环，那么这个图被称为哈密尔顿图；如果不存在哈密尔顿环，但是对于图中的任意两个不同的顶点u和v，存在经过这两个顶点的哈密尔顿路径（即包含u和v并且其余顶点均不重复的路径），则称之为哈密尔顿连通图。

哈密尔顿图和哈密尔顿连通图是图论中两个非常重要的概念，它们的研究对于理解各种应用问题具有重要的意义。

现在我们来介绍一种经典的哈密尔顿环算法——C算法。

C算法是一种基于回溯思想的搜索算法，它通过递归地搜索图中的所有可能的路径来找到哈密尔顿环。

虽然C算法在最坏情况下可能需要指数级的时间复杂度来解决哈密尔顿环问题，但是在实际应用中，它仍然是一种较为有效的方法。

C算法的基本思想是从图中的任意一个顶点开始，逐步向下一个未访问的顶点移动，并判断是否满足环的条件。

在搜索过程中，如果无法找到符合条件的路径，则回退到上一个节点，继续向其他未访问过的节点探索。

通过递归的方式，C算法最终可以找到所有可能的哈密尔顿环。

在实际应用中，C算法通常需要配合一些剪枝策略来提高搜索效率。

在搜索过程中，可以根据一些启发式规则来减少搜索空间，从而快速排除不可能存在哈密尔顿环的路径。

还可以利用一些局部优化技巧，如动态规划、记忆化搜索等，来加速查找哈密尔顿环的速度。

虽然C算法在最坏情况下的时间复杂度较高，但在实际应用中，它仍然是一种可行的方法。

通过合理设计剪枝策略和优化技巧，我们可以提高C算法的搜索效率，从而更快地找到哈密尔顿环。

在解决具体问题时，我们可以根据实际情况选择不同的搜索策略和优化方法，以达到更好的效果。

《无穷维Hamilton算子的特征值问题》篇一摘要：本文探讨了无穷维Hamilton算子的特征值问题，首先对相关概念进行了阐述，接着对问题的基本性质进行了分析，然后利用数学分析方法和技巧对问题进行了解析和求解，最后对研究结果进行了总结和展望。

一、引言在数学物理和量子力学中，Hamilton算子是一个重要的概念，它描述了系统的能量和动力学特性。

随着研究的深入，人们开始关注无穷维Hamilton算子的特征值问题，这涉及到更广泛的物理系统和更复杂的数学结构。

本文旨在探讨无穷维Hamilton算子的特征值问题，为相关研究提供理论依据。

二、Hamilton算子及其基本性质Hamilton算子是一个自伴的线性算子，其定义在Hilbert空间上。

在无穷维的情况下，Hamilton算子具有更复杂的性质和更广泛的应用。

特征值问题通常指的是寻找满足特定条件的算子特征向量的问题。

对于Hamilton算子而言，其特征值和特征向量描述了系统的能量状态和波函数。

三、无穷维Hamilton算子的特征值问题无穷维Hamilton算子的特征值问题是一个复杂的数学问题，涉及到无穷维Hilbert空间中的自伴算子。

在这个问题中，我们需要找到满足一定条件的特征向量和特征值，这些特征向量和特征值描述了系统的能级和对应的波函数。

这个问题具有挑战性，因为需要处理无穷维的Hilbert空间和自伴算子。

四、问题的分析和求解为了解决无穷维Hamilton算子的特征值问题，我们采用了数学分析的方法和技巧。

首先，我们分析了Hamilton算子的基本性质和结构，包括其自伴性、正定性等。

然后，我们利用变分法、微分方程等数学工具对问题进行求解。

具体而言，我们首先通过构造适当的试探函数空间，然后利用自伴性和正定性等性质将原问题转化为一个有限维的优化问题。

接着，我们利用微分方程等工具对优化问题进行求解，得到了一组特征向量和特征值的近似解。

最后，我们通过数值分析和实验验证了我们的解的正确性和有效性。

《无穷维Hamilton算子的拟谱》篇一摘要：本文旨在探讨无穷维Hamilton算子的拟谱问题。

首先，我们将介绍Hamilton算子的基本概念及其在物理和数学领域的重要性。

随后，我们将阐述拟谱方法的基本原理和在处理无穷维系统中的优势。

最后，我们将详细描述我们的研究方法和结果，以及这些结果对无穷维系统理论和相关领域研究的潜在贡献。

一、引言Hamilton算子是一种广泛应用于量子力学、光学、电磁学等领域的数学工具。

在处理具有无穷维度的系统时，Hamilton算子的谱问题变得尤为重要。

然而，由于无穷维系统的复杂性，直接求解其谱往往面临巨大挑战。

因此，寻求有效的拟谱方法成为研究的关键。

二、Hamilton算子的基本概念Hamilton算子是一种描述系统动力学的算子，具有特定的形式和性质。

在量子力学中，它描述了粒子的能量和动量关系。

在光学和电磁学中，它用于描述光场或电磁场的演化。

由于系统的复杂性，Hamilton算子往往具有无穷维度，使得其谱的求解变得困难。

三、拟谱方法的基本原理及优势拟谱方法是一种用于处理无穷维系统的数学方法。

它通过将系统在一定的近似空间中进行展开，将原本复杂的无穷维问题转化为有限维问题进行处理。

这种方法在处理具有复杂相互作用的系统时具有显著优势，能够有效地降低问题的复杂度。

四、无穷维Hamilton算子的拟谱研究针对无穷维Hamilton算子的拟谱问题，我们采用了一种基于拟谱方法的解决方案。

首先，我们选择了一个合适的近似空间，将Hamilton算子在这个空间中进行展开。

然后，我们利用数值方法求解展开后的有限维问题，得到Hamilton算子的近似谱。

最后，我们通过分析近似谱的性质，了解原系统的动力学特性。

五、研究方法与结果我们采用了一种基于多项式展开的拟谱方法。

首先，我们选择了一组合适的多项式基函数作为近似空间的基底。

然后，我们将Hamilton算子在这组基底上进行展开，得到一个有限维的矩阵表示。

Caley-Hamilton定理，或凯莱-哈密顿定理，是线性代数中的一个重要定理。

这个定理表明，对于任何位于交换环上的实或复矩阵，其特征多项式可以被其极小多项式整除。

在寻找若尔当标准形时特别有用。

这个定理是以数学家阿瑟·凯莱和威廉·卢云·哈密顿命名的，表达了矩阵的特征多项式和极小多项式之间的深刻关系。

这个定理的现代形式如下：
设A是一个n x n矩阵，则存在一个整数k，使得p(A) = 0，其中p是A的极小多项式。

在线性代数中，这个定理的使用对于理解和操作矩阵的特性非常重要，特别是对于求解线性方程组和找到若尔当标准形等问题。

The acyclic orientation gameon random graphsNoga Alon∗Zsolt Tuza†Dedicated to Professor Paul Erd˝o s on the occasion of his80th birthdayAbstractIt is shown that in the random graph G n,p with(fixed)edge probability p>0,the number of edges that have to be examined in order to identify anacyclic orientation isΘ(n log n)almost surely.For unrestricted p,an upperbound of O(n log3n)is established.Graphs G=(V,E)in which all edgeshave to be examined are considered,as well.1IntroductionIn this note we investigate the typical length of the following2-person game.Given a graph G=(V,E),in each step of the game player A(Algy)selects an edge e∈E and player S(Strategist)orients e in the way he likes;the only restriction is that S must not create a directed circuit.The game is over when the actually obtained partial orientation of G extends to a unique acyclic orientation.The goal of A is to locate such an orientation with as few questions as possible,while S aims at the opposite.Assuming that both A and S play optimally,the number of questions during the game on G is denoted by c(G).A different but equivalent formulation of this nice game wasfirst given by Manber and Tompa[8],who were motivated by a problem of testing whether a given coloring of a graph is a proper coloring.Some recent results concerning c(G)have been obtained by Aigner,Triesch and the second author in[1],including the generalestimatesn log nα−O(n)≤c(G)≤αn(lognα+1)(1)where n is the number of vertices,αdenotes the(vertex)independence number, and“log”means logarithm in base2.Let us note that a related lower bound can ∗Department of Mathematics,Raymond and Beverly Sackler Faculty of Exact Sciences,Tel Aviv University,Tel Aviv,Israel and School of Mathematics,Institute for Advanced Study,Princeton, NJ08540,USA.Research supported in part by a USA-Israeli BSF Grant and by the Sloan Foun-dation Grant No.93-6-6.†Computer and Automation Institute,Hungarian Academy of Sciences,H-1111Budapest, Kende u.13–17,Hungary.Research supported in part by the OTKA Research Fund of the Hun-garian Academy of Sciences,grant no.2569.1be deduced also from one of the results of[7]stating that a graph G with degree sequence d1,...,d n has at least n i=1((d i+1)!)1/(d i+1)acyclic orientations.This clearly implies that for any such G,c(G)≥ni=1logd i+1e.Let G n,p denote,as usual,the random graph on n labelled vertices with edge probability p.(See,e.g.,[6]for the model and some of its properties.)When the edge probability p isfixed,the above inequalities determine c(G n,p)within the accuracy of a multiplicative factor of O(log n)(with probability that tends to1as n tends to infinity).In the present note wefirst derive a more exact estimate,showing that in fact O(n log n)is the correct order of magnitude,i.e.,the lower bound is tight for all(fixed)p>0.Theorem1For anyfixed edge probability p>0,the random graph G=G n,p has c(G)=Θ(n log n)with probability1−o(1).Our argument proving the above theorem supplies very little information for the case where p(n)tends to zero as n gets large,and it remains an open problem to analyze the exact behavior of c(G n,p)where the edge probability p=p(n)tends to zero as n→∞.It may be true,however,that c(G n,p)=O(n log n)holds for all p. By(1),this bound,if true,would be tight for p=cn−c for all admissible choices of the constants c>0and0≤c <1.Note that the gap between the upper and lower bounds in(1)increases when p(n)decreases,and is a power of n when1/p(n)is a power of n.The next theorem supplies a much sharper estimate for sparse random graphs. Theorem2For any edge probability p=p(n),the random graph G=G n,p has c(G)=O(n log3n)with probability1−o(1).The proofs of Theorems1and2are different,but both combine some of the techniques used in the study of parallel comparison algorithms(see[3],[4],[2],[9]) with several new ideas.We note that the exponent of log n in Theorem2can be reduced slightly below3at the cost of making the argument somewhat more complicated,but—as this would not reduce the exponent to less than2,and as we suspect that the optimum value of the exponent is1actually—we do not present the more complicated proof.Let us recall from[1]that another challenging unsolved problem is to prove that c(G)≤1n2+o(n2)for all graphs G on n vertices.If valid,this upper bound would be best possible in general.We also note that there is no known sequence(G n)n>0of graphs,where G n has n vertices,for which the difference c(G n)−14n2tends toinfinity with n.The proofs of Theorems1and2are presented in Sections2and3,respectively. Thefinal Section4contains some comments on graphs G=(V,E)for which c(G)= |E|.22Fixed edge probabilityIn this section we prove Theorem1.For simplicity,we denote G n,p by G,where p is anyfixed positive edge probability.The argument is based on the following properties that hold for G almost surely.(Here and in what follows,“almost surely”always means“with probability that tends to1as n tends to infinity”.In addition, as usual,for two positive real functions f(x)and g(x),the notation f(x)=Θ(g(x)) means“f(x)=O(g(x))and g(x)=O(f(x))”.)1.For some function k=k(n)of orderΘ(log n),any two disjoint sets of k verticeseach are joined by at least one edge.2.There is a function k =k (n)=Θ(log n)such that,for any two disjoint setsX and Y of k vertices each,there is a vertex x∈X with at least k neighbors in Y,where k=k(n)is a function satisfying the requirements of(1)above. Thefirst property is well-known,and the second one is a fairly simple consequence of the Chernoffinequality.Indeed,the expected number of edges between X and Y is pc2log2n for k =c log n,while the nonexistence of x∈X with sufficiently many neighbors in Y would admit no more than kc log n edges;and the pair X,Y can be chosen in at most exp(2c log2n)different ways.Thus,choosing c sufficiently large (here“large”also depends on the value of the edge probability p)the requirement holds for all X and Y almost surely.An essential step in the proof of Theorem1is the following“deterministic”statement concerning linear extensions of partial orders.Tofix the notation,for an oriented acyclic digraph D=(V,A)we denote by D∗the transitive closure of D, i.e.,D∗=(V,A∗)is the smallest digraph in which A⊂A∗and xy,yz∈A∗implies xz∈A∗for all x,y,z∈V.Two vertices x,y∈V are comparable if xy∈A∗or yx∈A∗;for xy∈A∗we also say“x is smaller than y”or“y is larger than x”.A linear extension L of D is an ordering v1v2...v n of V such that i<j holds whenever v i is smaller than v j.In the next assertion we need not assume that the values of k and k are propor-tional to log n.Lemma3Suppose that the underlying undirected graph of an acyclic oriented graph D=(V,A)of order n satisfies the properties(1)and(2)above,for some k and k . Then,in every linear extension L=v1v2...v n of D,for every integer r between1 and n there is a subscript i(r−2k <i<r+2k )for which there are at least r−2k vertices smaller than v i and at least n−r−2k vertices larger than v i.Proof.Consider the set Y+={v i|r+k <i≤r+2k }.By(2),there are fewer than k vertices in{v j|1≤i≤r+k }having at most k−1neighbors in Y+.Denote by Z+the set of vertices v j having at least k neighbors in Y+,with j≤r+k .By(2),|Z+|>r holds.For each v j∈Z+,the(at least)k neighbors of v j in Y+dominate all but at most k−1vertices of{v i|r+2k <i≤n},by(1). Thus,every vertex v j∈Z+is smaller than at least k vertices in Y+and at least3n−r−k−2k vertices following Y+,i.e.,v j is smaller than at least n−r−2k vertices of D.Similarly,for the set Y−={v i|r−2k <i≤r−k }we canfind a set Z−⊆{v j|r−k <j≤n}of cardinality|Z−|>n−r such that every v j∈Z−is larger than k vertices of Y−and r−k−2k vertices preceding Y−,i.e.,v j is larger than at least r−2k vertices of D.Since|Z−|+|Z+|>n,we can choose a vertex w∈Z−∩Z+;this w=v i satisfies the requirements of the lemma.2We now turn to the proof of Theorem1,locating the acyclic orientation to be found,by applying an inductive algorithm.Let v be an arbitrary vertex of the random graph G=G n,p.Assuming that we have complete information about the orientation of G−v,we are going to show that the orientations of all edges incident to v can be determined by O(log n)questions(provided that G satisfies(1)and(2) above).If the orientation of G−v is not transitive,wefirst take its transitive closure, denoted D∗.Let D =(V ,E )be the subdigraph of D∗induced by the neighbors of v.Denoting n =|V |,let v1v2...v n be a linear extension of D .Tofind the orientations of all edges from v to V ,we are going to apply binary search on an appropriately chosen restricted set V ⊆V ,and then complete the algorithm with a few further questions.As we already know,by the properties(1)and(2),Lemma3implies that for every r(1≤r≤n )there is a vertex v i which is larger than r−2c log n vertices of V and smaller than n −r−2c log n vertices of V ,for some appropriately chosen constant c(we have taken k =c log n here;note that if G satisfies(1)and(2),so does its induced subgraph on the neighbors of v).Define V as the set of those i satisfying the above requirements for at least one value of r.Note that the gap between any two consecutive members of V is smaller than4c log n.Now,by a binary search on V we can locate a pair v i,v j∈V of vertices in log|V |<log n steps,such that v i is smaller than v,v is smaller than v j,and moreover i<j<i+4c log n.Since i and j belong to some initial values r=r i,r j of Lemma3with|r i−i|<2c log n and|r j−j|<2c log n,we can immediately conclude that v is larger than at least i−4c log n vertices of V ,and smaller than at least n −j−4c log n vertices of V .Thus,with at most12c log n further questions we can detect all orientations between v and V not known so far.Since the number of steps involving v is less than13c log n,the total number of questions required for G n,p does not exceed O(n log n).23Sparse random graphsIn this section we prove Theorem2.Given a graph G=(V,E),let the random strategy be the following strategy of player A:pick a random permutation e1,e2,...,e m of the edges of G and ask for the orientation of the edges in this order,where the orientation of the edge e i is probed if and only if it does not follow from the orientations of the edges e1,...,e i−1 (and the assumption that the orientation is acyclic).We claim that for every edge probability p,if player A applies this strategy on the random graph G=G n,p,then4almost surely he will not have to ask more than O(n log3n)questions even if hetells the order in which he is going to ask the questions to the Strategist already atthe beginning.This clearly implies the assertion of Theorem2.The advantage inconsidering this variation of the game is that since thefirst player A announces hisfull strategy already at the beginning,the second player S does not have to decidestep by step;instead,he can create his strategy at once,by choosing an acyclicorientation of G.Therefore,the version of the game we consider now is as follows.Player Achooses a random permutation e1,e2,...of the edges of G=G n,p and reports it tothe Strategist.The Strategist next chooses a linear order on the vertices of G andorients its edges according to this order(by orienting each edge from its smaller endto its larger end).The value of the game is the number of edges e i in the orientedgraph G that do not lie in the transitive closure of the oriented edges e1,...,e i−1,asthis is the number of questions A will actually have to ask.Therefore,our objectiveis to prove the following.Proposition4For any edge probability p and for a random ordering e1,e2,...ofthe set of edges of the random graph G n,p,the following holds almost surely.Forevery linear order of the vertices of G and for the associated acyclic orientation ofG,the number of oriented edges e i that do not lie in the transitive closure of theoriented edges e1,...,e i−1does not exceed O(n log3n).Notice that the subgraph of G n,p=(V,E)consisting of itsfirst i randomlychosen edges e1,...,e i—denoted by G i—is simply a random graph with i edges andn vertices.This fact plays a crucial role in our proof.It is worth noting that inview of this fact it suffices to prove the above proposition for the case p=1,i.e.,for the case that G is the complete graph.However,since this does not simplify theargument,we consider the general case G=G n,p.The proof relies on some of the ideas applied in the study of parallel comparisonalgorithms for approximation problems(see[2],[9],[3],[4]).In particular,we needthe following known result implicit in[2](cf.[9],[3]).Lemma5There exists an absolute constant b>0with the following property.LetG be a graph on n vertices in which there is at least one edge between any two disjointsets of q vertices each.Then,the number of edges in the transitive closure of anyacyclic orientation of G is at least n2 −bnq log n.2 The next lemma can be proved by a straightforward calculation which we omit. Lemma6There exists an absolute constant c so that for every i,n log n≤i≤ n2 , if G i is a random graph with n vertices and i edges,then the probability that G i hasat least one edge between any two disjoint sets of(cn2log n)/i vertices each is atleast1−1/n log n.2 Proof of Proposition 4.Throughout the proof we assume,whenever this is needed,that n is sufficiently large.To simplify the presentation,we make no attempt5to optimize the various multiplicative constants appearing here.Recall that for eachadmissible i≥1,G i denotes the subgraph of G=G n,p consisting of the edgese1,...,e i.By Lemma6,and since each G i is a random graph with i edges,thefollowing event denoted by E occurs almost surely:for every i≥n log n there is anedge of G i between any two disjoint sets of(cn2log n)/i vertices each.Fix a linear order L on the vertices of G,and let E L denote the event that thenumber of edges e i that do not lie in the transitive closure of the edges e1,...e i−1once these are oriented according to L exceeds32bcn log3n,where b and c are theconstants from Lemmas5and6,respectively.We next show that for eachfixedL,the conditional probability P rob[E L|E]is much smaller than1/n!.To do so,let us split the choice of the edges of G n,p and the random permutation on them intophases as follows.For each power of2,i.e.2j≥1,phase j consists of the choice of the edges e r for all2j≤r<2j+1of G(assuming G has at least that many edges). An equivalent,more precise,description of the random procedure of choosing the edges e i in the various phases is as follows.First choose the number m of edges of G according to a binomial distribution:P rob[m=s]= N s p s(1−p)N−s,where N= n2 .Next,starting with j=0,in phase j choose2j edges at random among the ones not chosen so far,as long as2j+1−1≤m.In the last phase,the one corresponding to the largest j for which2j≤m,we choose only m−2j+1random edges.Let E L,j denote the event that during phase j the number of edges e r that do not lie in the transitive closure of thefirst2j−1oriented edges exceeds16bcn log2n. Since E L is contained in the union∪j≥0E L,j(as the number of phases is less than 2log n),we haveP rob[E L|E]≤ j≥0P rob[E L,j|E].If2j≤16bcn log2n,then clearly P rob[E L,j|E]=0.For any larger j,observe thatP rob[E L,j|E]=P rob[E L,j∧E]P rob[E]≤2P rob[E L,j∧E].(Here we used the fact that P rob[E]≥1/2;in fact this probability is1−o(1).)However,if E happens then,by Lemma5,the transitive closure of the graph G2j−1 (oriented according to L)contains at least n2 −bcn3log2n j edges.If2j−1≥n2/16, then certainly the event E L,j will not occur,as the total number of edges which arenot in the transitive closure we consider is at most16bcn log2n.Otherwise,in phasej we are choosing2j(≤n2/16+1)edges at random among the n2 −2j+1≥(1+o(1))716n2remaining ones,and the number of edges among those which are notin the transitive closure of G2j−1is at most bcn3log2nj,i.e.,a fraction of at most(1+o(1))16bcn log2n7(2j−1)<3bcn log2n/2jof the remaining edges(here we assumed that n is large enough).Therefore,the expected number of edges chosen in the j th phase which are not in the transitive6closure of G2j−1is smaller than3bcn log2n.By standard estimates(see,e.g.,[5],Ap-pendix A,Theorem A.12)it follows that the probability that more than16bcn log2n such edges are chosen(i.e,that E L,j happens)is at most exp{−Ω(n log2n)}.This bounds P rob[E L,j∧E]and hence P rob[E L,j|E]as well,and implies that for every fixed L,P rob[E L|E]≤2log n exp{−Ω(n log2n)}.To complete the proof of the proposition,observe now that the probability that there exists a linear order L for which there are more than32bcn log3n edges e i that do not lie in the transitive closure of the previous edges is at mostP rob[E]+ L P rob[E L|E]·P rob[E]≤o(1)+2n!log n exp{−Ω(n log2n)},which tends to zero as n tends to infinity.This completes the proof of Proposition 4,and implies the assertion of Theorem2.24Exhaustive graphsTrivially,any(acyclic)orientation of a graph G=(V,E)can be identified by|E| questions.Call G exhaustive if it admits nothing better than this trivial algorithm, i.e.,if c(G)=|E|.We do not know too much about the structure of exhaustive graphs.It is observed in[1]that every bipartite graph is exhaustive,and it is alsoshown there that exhaustive graphs on n vertices have at most14n2edges(for alln≥6).Using arguments similar to those used in the proof of Theorem2we can show that a random graph with n vertices and more than n log n log log n edges is almost surely non-exhaustive.Similar techniques can be used to show that there are non-exhaustive graphs of arbitrarily high girth.A couple of small non-exhaustive graphs are mentioned in[1].The next proposition exhibits a further explicit example and answers a question raised in[1],where the authors wonder if there are line graphs of triangle-free cubic graphs which are non-exhaustive.Proposition7The line graph L(K3,3)of the complete bipartite graph K3,3is non-exhaustive.Proof.If three vertices x,y,z induce a triangle in an exhaustive graph and the orientation of precisely one edge,say x→z,is known,then the next answer concerning the edge xy or yz is determined,namely if xy(yz)is probed next then the answer must be x→y(y→z),for otherwise the orientation of the third edge of the triangle were determined by the other two.For such situations we shall use the shorthand“x→z forces x→y”or“x→z forces y→z”which will also mean that the next edge asked is xy or yz,respectively.Suppose now on the contrary that L(K3,3)is exhaustive.Assuming that the vertex classes of K3,3are{x1,x2,x3}and{y1,y2,y3},we denote by v ij the vertex of L(K3,3)that represents the edge x i y j;hence,v ij and v i j are adjacent if and only if i=i or j=j .At the beginning we ask about the orientations of v11v12and v13v23. By symmetry,we may assume without loss of generality that these two orientations7are v11→v12and v13→v23.Then we ask about v21v31and prove that either answer will allow us to save at least one question.Supposefirst v21→v31.Then v21→v31forces v21→v11and v11→v12 forces v11→v13,therefore the directed path v21→v11→v13→v23determines the orientation of v21→v23and this question need not be asked.Hence,suppose v31→v21.Then v31→v21forces v31→v11,v11→v12forces v11→v13,and v13→v23forces v13→v33.Thus,the directed path v31→v11→v13→v33 determines the orientation of v31→v33.2 We note that apart from the density-type results,so far the non-exhaustiveness of particular graphs has been proved by ad hoc arguments.It would be interesting to know more about the structural reasons that make a graph non-exhaustive.References[1]M.Aigner,E.Triesch and Zs.Tuza,Searching for acyclic orientations of graphs,to appear.[2]M.Ajtai,J.Koml´o s,W.L.Steiger and E.Szemer´e di,Almost sorting in one round,Advances in Computing Research,Vol.5,1989,JAI Press,117-126.[3]N.Alon and Y.Azar,Sorting,approximate sorting and searching in rounds,SIAMJ.Discrete Math.1(1988),269-280.[4]N.Alon and Y.Azar,Parallel comparison algorithms for approximation problems,Proc.29th IEEE FOCS,Yorktown Heights,NY,1988,194-203.Also:Combina-torica11(1991),97-122.[5]N.Alon and J.H.Spencer,“The Probabilistic Method”,Wiley,1991.[6] B.Bollob´a s,“Random Graphs”,Academic Press,1985.[7]N.Kahale and L.Schulman,Bounds on the chromatic polynomial and on thenumber of acyclic orientations of a graph,to appear.[8]U.Manber and M.Tompa,The effect of the number of Hamiltonian paths on thecomplexity of a vertex coloring problem,Proc.25th IEEE FOCS,Singer Island, Florida1984,220-227.[9]N.Pippenger,Sorting and selecting in rounds,SIAM put.6(1987),1032-1038.8。