共查询到20条相似文献,搜索用时 0 毫秒
1.
Michele Conforti Gérard Cornuéjols Grigor Gasparyan Kristina Vušković 《Combinatorica》2002,22(1):19-33
We prove a theorem about cutsets in partitionable graphs that generalizes earlier results on amalgams, 2-amalgams and homogeneous
pairs.
Received December 13, 1999
RID="*"
ID="*" This work was supported in part by the Fields Institute for Research in Mathematical Sciences, Toronto, Canada, and
by NSF grants DMI-0098427 and DMI-9802773 and ONR grant N00014-97-1-0196. 相似文献
2.
Michael Capalbo 《Combinatorica》2002,22(3):345-359
For all positive integers N and k, let denote the family of planar graphs on N or fewer vertices, and with maximum degree k. For all positive integers N and k, we construct a -universal graph of size . This construction answers with an explicit construction the previously open question of the existence of such a graph.
Received July 8, 1998
RID="*"
ID="*" Supported by NSF grant CCR98210-58 and ARO grant DAAH04-96-1-0013. 相似文献
3.
Given two graphs A and G, we write if there is a homomorphism of A to G and if there is no such homomorphism. The graph G is -free if, whenever both a and c are adjacent to b and d, then a = c or b = d. We will prove that if A and B are connected graphs, each containing a triangle and if G is a -free graph with and , then (here " denotes the categorical product).
Received August 31, 1998/Revised April 19, 2000
RID="†"
ID="†" Supported by NSERC of Canada Grant #691325. 相似文献
4.
Christian Houdré 《Combinatorica》2001,21(4):489-513
Two types of lower bounds are obtained on the log-Sobolev constants of graphs and Markov chains. The first is a mixture of
spectral gap and logarithmic isoperimetric constant, the second involves the Gaussian isoperimetric constant. The sharpness
of both types of bounds is tested on some examples. Product generalizations of some of these results are also briefly given.
Received March 1, 1999/Revised July 17, 2000
RID="*"
ID="*" Research supported in part by the NSF Grant No. DMS–9803239. The author greatly enjoyed the hospitality of CIMAT, Gto,
Mexico, where part of this work was done. 相似文献
5.
6.
We show that if a language has an interactive proof of logarithmic statistical knowledge-complexity, then it belongs to the
class . Thus, if the polynomial time hierarchy does not collapse, then -complete languages do not have logarithmic knowledge complexity. Prior to this work, there was no indication that would contradict
languages being proven with even one bit of knowledge. Our result is a common generalization of two previous results: The
first asserts that statistical zero knowledge is contained in [11, 2], while the second asserts that the languages recognizable in logarithmic statistical knowledge complexity are in
[19].
Next, we consider the relation between the error probability and the knowledge complexity of an interactive proof. Note that
reducing the error probability via repetition is not free: it may increase the knowledge complexity. We show that if the negligible
error probability is less than (where k(n) is the knowledge complexity) then the language proven is in the third level of the polynomial time hierarchy (specifically,
it is in ). In the standard setting of negligible error probability, there exist PSPACE-complete languages which have sub-linear knowledge
complexity. However, if we insist, for example, that the error probability is less than , then PSPACE-complete languages do not have sub-quadratic knowledge complexity, unless .
In order to prove our main result, we develop an AM protocol for checking that a samplable distribution D has a given entropy h. For any fractions , the verifier runs in time polynomial in and and fails with probability at most to detect an additive error in the entropy. We believe that this protocol is of independent interest. Subsequent to our work Goldreich and Vadhan [16]
established that the problem of comparing the entropies of two samplable distributions if they are noticeably different is
a natural complete promise problem for the class of statistical zero knowledge ().
Received January 6, 2000
RID=" "
ID=" " This research was performed while the authors were visiting the Computer Science Department at the University of Toronto,
preliminary version of this paper appeared in [27]
RID="*"
ID="*" Partially supported by Technion V. P. R. Found––N. Haar and R. Zinn Research Fund.
RID="†"
ID="†" Partially supported by the grants OTKA T-029255, T-030059, FKFP 0607/1999, and AKP 2000-78 2.1. 相似文献
7.
Dedicated to the memory of Paul Erdős
A graph is called -free if it contains no cycle of length four as an induced subgraph. We prove that if a -free graph has n vertices and at least edges then it has a complete subgraph of vertices, where depends only on . We also give estimates on and show that a similar result does not hold for H-free graphs––unless H is an induced subgraph of . The best value of is determined for chordal graphs.
Received October 25, 1999
RID="*"
ID="*" Supported by OTKA grant T029074.
RID="**"
ID="**" Supported by TKI grant stochastics@TUB and by OTKA grant T026203. 相似文献
8.
d , and the testing algorithm can perform queries of the form: ``who is the ith neighbor of vertex v'. The tester should determine with high probability whether the graph is bipartite or ε-far from bipartite for any given
distance parameter ε. Distance between graphs is defined to be the fraction of entries on which the graphs differ in their
incidence-lists representation. Our testing algorithm has query complexity and running time where N is the number of graph vertices. It was shown before that queries are necessary (for constant ε), and hence the performance of our algorithm is tight (in its dependence on N), up to polylogarithmic factors.
In our analysis we use techniques that were previously applied to prove fast convergence of random walks on expander graphs.
Here we use the contrapositive statement by which slow convergence implies small cuts in the graph, and further show that
these cuts have certain additional properties. This implication is applied in showing that for any graph, the graph vertices
can be divided into disjoint subsets such that: (1) the total number of edges between the different subsets is small; and
(2) each subset itself exhibits a certain mixing property that is useful in our analysis.
Received: February 6, 1998 相似文献
9.
Carsten Thomassen 《Combinatorica》2001,21(3):417-443
We prove the conjecture made by Bjarne Toft in 1975 that every 4-chromatic graph contains a subdivision of in which each edge of corresponds to a path of odd length. As an auxiliary result we characterize completely the subspace of the cycle space generated by all cycles through two fixed edges. Toft's conjecture was proved independently in 1995 by Wenan Zang. Received May 26, 1998 相似文献
10.
Let be any fixed graph. For a graph G we define to be the maximum size of a set of pairwise edge-disjoint copies of in G. We say a function from the set of copies of in G to [0, 1] is a fractional -packing of G if for every edge e of G. Then is defined to be the maximum value of over all fractional -packings of G. We show that for all graphs G. Received July 27, 1998 / Revised December 3, 1999 相似文献
11.
Oleg Pikhurko 《Combinatorica》2001,21(3):403-412
Let be the star with n edges, be the triangle, and be the family of odd cycles. We establish the following bounds on the corresponding size Ramsey numbers.
The upper (constructive) bound disproves a conjecture of Erdős.
Also we show that provided is an odd cycle of length o(n) or is a 3-chromatic graph of order o(log n).
Received May 28, 1999
RID="*"
ID="*" Supported by an External Research Studentship, Trinity College, Cambridge, UK. 相似文献
12.
Superpolynomial Size Set-systems with Restricted Intersections mod 6 and Explicit Ramsey Graphs 总被引:1,自引:0,他引:1
Vince Grolmusz 《Combinatorica》2000,20(1):71-86
Dedicated to the memory of Paul Erdős
We construct a system of subsets of a set of n elements such that the size of each set is divisible by 6 but their pairwise intersections are not divisible by 6. The result
generalizes to all non-prime-power moduli m in place of m=6. This result is in sharp contrast with results of Frankl and Wilson (1981) for prime power moduli and gives strong negative answers to questions by Frankl and Wilson (1981) and Babai and Frankl (1992). We use our set-system to give an explicit Ramsey-graph construction, reproducing the logarithmic order of magnitude of the best previously known
construction due to Frankl and Wilson (1981). Our construction uses certain mod m polynomials, discovered by Barrington, Beigel and Rudich (1994).
Received January 15, 1996/Revised August 2, 1999 相似文献
13.
In this paper, we prove the following result:
Let G be a connected graph of order n, and minimum degree . Let a and b two integers such that 2a <= b. Suppose and .
Then G has a connected [a,b]-factor.
Received February 10, 1998/Revised July 31, 2000 相似文献
14.
The Kneser graph K(n,k) has as vertices the k-subsets of {1, 2, ..., n}. Two vertices are adjacent if the corresponding k-subsets are disjoint. It was recently proved by the first author [2] that Kneser graphs have Hamilton cycles for n >= 3k. In this note, we give a short proof for the case when k divides n.
Received September 14, 1999 相似文献
15.
Received: August 22, 1996 相似文献
16.
W. Mader 《Combinatorica》2001,21(2):251-265
Dedicated to the memory of Paul Erdős
It is proved that for every finite graph H of maximal degree and every , there is an integer such that every finite graph of average degree at least and of girth at least contains a subdivision of H.
Received May 5, 1999 相似文献
17.
G , H, and lists , a list homomorphism of G to H
with respect to the lists
L is a mapping , such that for all , and for all . The list homomorphism problem for a fixed graph H asks whether or not an input graph G together with lists , , admits a list homomorphism with respect to L. We have introduced the list homomorphism problem in an earlier paper, and proved there that for reflexive graphs H (that is, for graphs H in which every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP-complete otherwise. Here we consider graphs H without loops, and find that the problem is closely related to circular arc graphs. We show that the list homomorphism problem
is polynomial time solvable if the complement of H is a circular arc graph of clique covering number two, and is NP-complete otherwise. For the purposes of the proof we give
a new characterization of circular arc graphs of clique covering number two, by the absence of a structure analogous to Gallai's
asteroids. Both results point to a surprising similarity between interval graphs and the complements of circular arc graphs
of clique covering number two.
Received: July 22, 1996/Revised: Revised June 10, 1998 相似文献
18.
Amnon Ta-Shma 《Combinatorica》2002,22(1):123-145
A disperser is a bipartite graph with the property that every subset A of of cardinality at least K, has at least fraction of the vertices of as neighbors. Such graphs have many applications in derandomization. Saks, Srinivasan and Zhou presented an explicit construction
of a disperser with an almost optimal degree , for every . We extend their result for every parameter .
Received November 12, 1998/Revised June 20, 2000
RID="*"
ID="*" This work was partially done while the author was at the Department of Computer Science, Weizmann Institute of Science,
Rehovot, Israel. This work was supported by a Phil Zacharia postdoctoral fellowship. 相似文献
19.
Dedicated to the memory of Paul Erdős
We provide an elementary proof of the fact that the ramsey number of every bipartite graph H with maximum degree at most is less than . This improves an old upper bound on the ramsey number of the n-cube due to Beck, and brings us closer toward the bound conjectured by Burr and Erdős. Applying the probabilistic method
we also show that for all and there exists a bipartite graph with n vertices and maximum degree at most whose ramsey number is greater than for some absolute constant c>1.
Received December 1, 1999
RID="*"
ID="*" Supported by NSF grant DMS-9704114
RID="**"
ID="**" Supported by KBN grant 2 P03A 032 16 相似文献
20.
Y. Katznelson 《Combinatorica》2001,21(2):211-219
Dedicated to the memory of Paul Erdős In 1987 Paul Erdős asked me if the Cayley graph defined on Z by a lacunary sequence has necessarily a finite chromatic number. Below is my answer, delivered to him on the spot but never published, and some additional remarks. The key is the interpretation of the question in terms of return times of dynamical systems. Received February 7, 2000 相似文献