首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 46 毫秒
1.
Let denote the graph obtained from Kr by deleting one edge. We show that for every integer r≥4 there exists an integer n0=n0(r) such that every graph G whose order nn0 is divisible by r and whose minimum degree is at least contains a perfect -packing, i.e. a collection of disjoint copies of which covers all vertices of G. Here is the critical chromatic number of . The bound on the minimum degree is best possible and confirms a conjecture of Kawarabayashi for large n.  相似文献   

2.
Kreweras’ conjecture [G. Kreweras, Matchings and hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl. 16 (1996) 87–91] asserts that every perfect matching of the hypercube Qd can be extended to a Hamiltonian cycle of Qd. We [Jiří Fink, Perfect matchings extend to hamilton cycles in hypercubes, J. Combin. Theory Ser. B, 97 (6) (2007) 1074–1076] proved this conjecture but here we present a simplified proof.The matching graph of a graph G has a vertex set of all perfect matchings of G, with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle of G. We show that the matching graph of a complete bipartite graph is bipartite if and only if n is even or n=1. We prove that is connected for n even and has two components for n odd, n≥3. We also compute distances between perfect matchings in .  相似文献   

3.
A random n-lift of a base-graph G is its cover graph H on the vertices [nV(G), where for each edge uv in G there is an independent uniform bijection π, and H has all edges of the form (i,u),(π(i),v). A main motivation for studying lifts is understanding Ramanujan graphs, and namely whether typical covers of such a graph are also Ramanujan.Let G be a graph with largest eigenvalue λ1 and let ρ be the spectral radius of its universal cover. Friedman (2003) [12] proved that every “new” eigenvalue of a random lift of G is with high probability, and conjectured a bound of ρ+o(1), which would be tight by results of Lubotzky and Greenberg (1995) [15]. Linial and Puder (2010) [17] improved Friedman?s bound to . For d-regular graphs, where λ1=d and , this translates to a bound of O(d2/3), compared to the conjectured .Here we analyze the spectrum of a random n-lift of a d-regular graph whose nontrivial eigenvalues are all at most λ in absolute value. We show that with high probability the absolute value of every nontrivial eigenvalue of the lift is . This result is tight up to a logarithmic factor, and for λ?d2/3−ε it substantially improves the above upper bounds of Friedman and of Linial and Puder. In particular, it implies that a typical n-lift of a Ramanujan graph is nearly Ramanujan.  相似文献   

4.
In recent years, sum–product estimates in Euclidean space and finite fields have received great attention. They can often be interpreted in terms of Erdős type incidence problems involving the distribution of distances, dot products, areas, and so on, which have been studied quite extensively by way of combinatorial and Fourier analytic techniques. We use both kinds of techniques to obtain sharp or near-sharp results on the distribution of volumes (as examples of d-linear homogeneous forms) determined by sufficiently large subsets of vector spaces over finite fields and the associated arithmetic expressions. Arithmetic–combinatorial techniques turn out to be optimal for dimension d≥4 to this end, while for d=3 they have failed to provide us with a result that follows from the analysis of exponential sums. To obtain the latter result we prove a relatively straightforward function version of an incidence results for points and planes previously established in [D. Hart, A. Iosevich, Sums and products in finite fields: An integral geometric viewpoint, in: Radon Transforms, Geometry, and Wavelets, Contemp. Math. 464 (2008); D. Hart, A. Iosevich, D. Koh, M. Rudnev, Averages over hyperplanes, sum–product theory in vector spaces over finite fields and the Erdős–Falconer distance conjecture, arXiv:math/0711.4427, preprint 2007].More specifically, we prove that if E=A××A is a product set in , d≥4, the d-dimensional vector space over a finite field , such that the size |E| of E exceeds (i.e. the size of the generating set A exceeds ) then the set of volumes of d-dimensional parallelepipeds determined by E covers . This result is sharp as can be seen by taking , a prime sub-field of its quadratic extension , with q=p2. For in three dimensions, however, we are able to establish the same result only if (i.e., , for some C; in fact, the bound can be justified for a slightly wider class of “Cartesian product-like” sets), and this uses Fourier methods. Yet we do prove a weaker near-optimal result in three dimensions: that the set of volumes generated by a product set E=A×A×A covers a positive proportion of if (so ). Besides, without any assumptions on the structure of E, we show that in three dimensions the set of volumes covers a positive proportion of if |E|≥Cq2, which is again sharp up to the constant C, as taking E to be a 2-plane through the origin shows.  相似文献   

5.
For convex bodies K with boundary in , we explore random polytopes with vertices chosen along the boundary of K. In particular, we determine asymptotic properties of the volume of these random polytopes. We provide results concerning the variance and higher moments of this functional, as well as an analogous central limit theorem.  相似文献   

6.
Two different constructions are given of a rank 8 arc-transitive graph with 165 vertices and valency 8, whose automorphism group is M11. One involves 3-subsets of an 11-set while the other involves 4-subsets of a 12-set, and the constructions are linked with the Witt designs on 11, 12 and 24 points. Four different constructions are given of a rank 9 arc-transitive graph with 55 vertices and valency 6 whose automorphism group is . This graph occurs as a subgraph of the M11 graph, and two of the constructions involve 2-subsets of an 11-set while the remaining two involve 3-subsets of an 11-set. The and M11 graphs occur as the second and third members of a tower of graphs defined on a conjugacy class of involutions of the simple groups A5, , M11 and M12 with two involutions adjacent if they generate a special S3. The first graph in the tower is the line graph of the Petersen graph while the fourth is the Johnson graph J(12,4). The graphs also arise as collineation graphs of rank 2 truncations of various residues of certain P-geometries.  相似文献   

7.
Let g(n,r) be the maximum possible cardinality of a family of subsets of {1,2,…,n} so that given a union of at most r members of , one can identify at least one of these members. The study of this function is motivated by questions in molecular biology. We show that , thus solving a problem of Csűrös and Ruszinkó.  相似文献   

8.
This paper investigates the automorphism group of a connected and undirected G-symmetric graph Γ where G is an almost simple group with socle T. First we prove that, for an arbitrary subgroup M of containing G, either T is normal in M or T is a subgroup of the alternating group Ak of degree . Then we describe the structure of the full automorphism group of G-locally primitive graphs of valency d, where d≤20 or is a prime. Finally, as one of the applications of our results, we determine the structure of the automorphism group for cubic symmetric graph Γ admitting a finite almost simple group.  相似文献   

9.
Let n3 and let F be a 2-regular graph of order n. The Oberwolfach problem OP(F) asks for a 2-factorisation of Kn if n is odd, or of KnI if n is even, in which each 2-factor is isomorphic to F. We show that there is an infinite set of primes congruent to such that OP(F) has a solution for any 2-regular graph F of order . We also show that for each of the infinitely many with prime, OP(F) has a solution for any 2-regular graph F of order n.  相似文献   

10.
In this paper we present two different results dealing with the number of (≤k)-facets of a set of points:
1. We give structural properties of sets in the plane that achieve the optimal lower bound of (≤k)-edges for a fixed 0≤kn/3−1; and
2. we show that, for k<n/(d+1), the number of (≤k)-facets of a set of n points in general position in is at least , and that this bound is tight in the given range of k.

Article Outline

1. Introduction
2. Optimal sets for (≤k)-edge vectors
3. A lower bound for (≤k)-facets in
4. Conclusions and open problems
Acknowledgements
References

1. Introduction

In this paper we deal with the problem of giving lower bounds to the number of (≤k)-facets of a set of points S. An oriented simplex with vertices at points of S is said to be a k-facet of S if it has exactly k points in the positive side of its affine hull. Similarly, the simplex is said to be an (≤k)-facet if it has at most k points in the positive side of its affine hull. If , a k-facet of S is usually named a k-edge.The number of k-facets of S is denoted by ek(S), and is the number of (≤k)-facets (the set S will be omitted when it is clear from the context). Giving bounds on these quantities, and on the number of the companion concept of k-sets, is one of the central problems in Discrete and Computational Geometry, and has a long history that we will not try to summarize here. Chapter 8.3 in [4] is a complete and up to date survey of results and open problems in the area.Regarding lower bounds for Ek(S), which is the main topic of this paper, the problem was first studied by Edelsbrunner et al. [6] due to its connections with the complexity of higher order Voronoi diagrams. In that paper it was stated that, in ,
(1)
and there was given an example showing tightness for 0≤kn/3−1. The proof used circular sequences but, unfortunately, contained an unpluggable gap, as pointed out by Lovász et al. [8]. A correct proof, also using circular sequences, was independently found by Ábrego and Fernández-Merchant [1] and Lovász et al. [8]. In both papers a strong connection was discovered between the number of (≤k)-edges and the number of convex quadrilaterals in a point set S. Specifically, if (S) denotes the number of convex quadrilaterals in S, in [8] it was shown that
(2)
where
Giving lower bounds for (S) is in turn equivalent to determining the rectilinear crossing number of the complete graph: if we draw Kn on top of a set of points S, then the number of intersections in the drawing is exactly the number of convex quadrilaterals in S. The interested reader can go through the extensive online bibliography by Vrt’o [9], where the focus is on the problem of crossing numbers of graphs.The lower bound in Eq. (1) was slightly improved for by Balogh and Salazar [3], again using circular sequences. Using different techniques, and based on the observation that it suffices to prove the bound for sets with triangular convex hull, we have recently shown [2] that, in ,
(3)
If n is divisible by 3, this expression can be written as
In this paper we deal with two different problems related to lower bounds for Ek. In Section 2, we study the structural properties of those sets in  that achieve the lower bound in Eq. (1) for a fixed 0≤kn/3−1. The main result of this section is that, if Ek(S) is minimum for a given k, then Ej(S) is also minimum for every 0≤j<k. In Section 3 we study the d-dimensional version of the problem and show that, for a set of n points in general position in ,
(4)
and that this bound is tight in that range. To the best of our knowledge, this is the first result of this kind in .

2. Optimal sets for (≤k)-edge vectors

Given , let us denote by  the set of all (≤k)-edges of S; hence Ek(S) is the cardinality of . Throughout this section we consider . Recall that for a fixed such k, Ek(S) is optimal if . Recall also that, by definition, a j-edge has exactly j points of S in the positive side of its affine hull, which in this case is the open half-plane to the right of its supporting line.We start by giving a new, simple, and self-contained proof of the bound in Eq. (1), using a new technique which will be useful in the rest of the section. Although in this section they will be used in , the following notions are presented in  for the sake of generality and in view of Section 3.Definition 1 [7] Let S be a set of n points and a family of sets in . A subset NS is called an -net of S (with respect to ) if for every such that |HS|>n we have that HN≠.Definition 2 A simplicial -net of is a set of d+1 vertices of the convex hull of S that are an -net of S with respect to closed half-spaces. A simplicial -net will be called a simplicial half-net.Lemma 3 Every set of n points has a simplicial half-net.Proof Let T be a triangle spanned by three vertices of the convex hull of S. An edge e of T is called good if the closed half-plane of its supporting line which contains the third vertex of T contains at least points from S. T is called good if it consists of three good edges. Clearly, the vertices of a good triangle T are a simplicial half-net of S; the vertices of T being of the convex hull implies that the intersection of S with a half-plane not containing any vertex of T lies in the complement of some of the three half-planes defined by the good edges.Let T be an arbitrary triangle spanned by vertices of the convex hull of S and assume that T is not good. Then observe that only one edge e of T is not good and let v be the vertex of T not incident to e. Choose a point v of the convex hull of S opposite to v with respect to e. Then e and v induce a triangle T in which e is a good edge. If T is a good triangle we are done. Otherwise we iterate this process. As the cardinalities of the subsets of vertices of S considered are strictly decreasing (the subsets being restricted by the half-plane induced by e), the process terminates with a good triangle. □Theorem 4 For every set S of n points and we have .Proof The proof goes by induction on n. From Lemma 3, we can guarantee the existence of T={a,b,c}S, an -net made up with vertices of the convex hull.Let S=ST and consider an edge . We observe that T cannot be to the right of e: there are at least points on the closed half-plane to the left of e and that would contradict the definition of -net. Therefore, .If we denote by the set of (≤k)-edges of S incident to points in T, we have that
(5)
There are 2(k+1)(≤k)-edges incident to each of the convex hull vertices a,b,c (which can be obtained rotating a ray based on that vertex). We observe that at most three edges of might be incident to two points of T (those of the triangle T) and that the union in Eq. (5) is disjoint. Therefore, using the induction hypothesis we have
(6)
 □Corollary 5 Let S be a set of n points, T={a,b,c} a simplicial half-net of S , and S=ST . If , then:
(a) .
(b) A k-edge of S is either a (k−2)-edge of S or is incident to a point in T .
Proof If , both inequalities in Eq. (6) are tight. Therefore , and Eq. (5) becomes (disjoint union), which trivially implies part (b). □Theorem 6 If , then S has a triangular convex hull.Proof We prove the statement by induction over k. For k=0 nothing has to be proven, so let k=1, assume that E1=9, and let h=|CH(S)|. We have h 0-edges and at least h 1-edges (two per convex hull vertex, but each edge might be counted twice). Thus E1=9≥2h, and therefore h≤4. Assume now h=4. Then at most two 1-edges can be counted twice, namely the two diagonals of the convex hull. Thus we have 4+8−2=10(≤1)-edges, and we conclude that, if E1=9, then S has a triangular convex hull.For the general case, consider k≥2, let T={a,b,c} be the simplicial half-net guaranteed by Lemma 3, and let S=ST. From Corollary 5, part (a), we know that and, by induction, we may assume that S has a triangular convex hull. Moreover, from part (b), no (k−1)-edge of S can be an (≤k)-edge of S and, therefore, any (k−1)-edge of S must have two vertices of T on its positive side. Consider the six (k−1)-edges of S incident to the three convex hull vertices of S: see Fig. 1, where the supporting lines of these (k−1)-edges are drawn as dashed lines and S is depicted as the central triangle. Each cell outside S in the arrangement of the supporting lines contains a number counting the (k−1)-edges considered which have that cell on their positive side. A simple counting argument shows that the only way of placing the three vertices a,b,c of T such that each (k−1)-edge of S drawn has two of them on its positive side is to place one in each cell labeled with a 4. We conclude that no vertex of S can be on the convex hull of S, and the theorem follows. □  相似文献   

11.
Mixing 3-colourings in bipartite graphs   总被引:1,自引:0,他引:1  
For a 3-colourable graph G, the 3-colour graph of G, denoted , is the graph with node set the proper vertex 3-colourings of G, and two nodes adjacent whenever the corresponding colourings differ on precisely one vertex of G. We consider the following question: given G, how easily can one decide whether or not is connected? We show that the 3-colour graph of a 3-chromatic graph is never connected, and characterise the bipartite graphs for which is connected. We also show that the problem of deciding the connectedness of the 3-colour graph of a bipartite graph is coNP-complete, but that restricted to planar bipartite graphs, the question is answerable in polynomial time.  相似文献   

12.
In this paper we investigate how certain results related to the Hanani–Tutte theorem can be extended from the plane to surfaces. We give a simple topological proof that the weak Hanani–Tutte theorem is true on arbitrary surfaces, both orientable and non-orientable. We apply these results and the proof techniques to obtain new and old results about generalized thrackles, including that every bipartite generalized thrackle on a surface S can be embedded on S. We also extend to arbitrary surfaces a result of Pach and Tóth that allows the redrawing of a graph so as to remove all crossings with even edges. From this we can conclude that , the crossing number of a graph G on surface S, is bounded by , where is the odd crossing number of G on surface S. Finally, we prove that whenever , for any surface S.  相似文献   

13.
14.
In this paper, we prove that a set of q5+q4+q3+q2+q+1 lines of with the properties that (1) every point of is incident with either 0 or q+1 elements of , (2) every plane of is incident with either 0, 1 or q+1 elements of , (3) every solid of is incident with either 0, 1, q+1 or 2q+1 elements of , and (4) every hyperplane of is incident with at most q3+3q2+3q members of , is necessarily the set of lines of a regularly embedded split Cayley generalized hexagon in .  相似文献   

15.
Let f be a function from a finite field with a prime number p of elements, to . In this article we consider those functions f(X) for which there is a positive integer with the property that f(X)i, when considered as an element of , has degree at most p−2−n+i, for all i=1,…,n. We prove that every line is incident with at most t−1 points of the graph of f, or at least n+4−t points, where t is a positive integer satisfying n>(p−1)/t+t−3 if n is even and n>(p−3)/t+t−2 if n is odd. With the additional hypothesis that there are t−1 lines that are incident with at least t points of the graph of f, we prove that the graph of f is contained in these t−1 lines. We conjecture that the graph of f is contained in an algebraic curve of degree t−1 and prove the conjecture for t=2 and t=3. These results apply to functions that determine less than directions. In particular, the proof of the conjecture for t=2 and t=3 gives new proofs of the result of Lovász and Schrijver [L. Lovász, A. Schrijver, Remarks on a theorem of Rédei, Studia Sci. Math. Hungar. 16 (1981) 449–454] and the result in [A. Gács, On a generalization of Rédei’s theorem, Combinatorica 23 (2003) 585–598] respectively, which classify all functions which determine at most 2(p−1)/3 directions.  相似文献   

16.
In this paper we study random induced subgraphs of Cayley graphs of the symmetric group induced by an arbitrary minimal generating set of transpositions. A random induced subgraph of this Cayley graph is obtained by selecting permutations with independent probability, λn. Our main result is that for any minimal generating set of transpositions, for probabilities where and δ>0, a random induced subgraph has a.s. a unique largest component of size . Here x(?n) is the survival probability of a Poisson branching process with parameter λ=1+?n.  相似文献   

17.
We consider a new type of extremal hypergraph problem: given an r-graph and an integer k≥2 determine the maximum number of edges in an -free, k-colourable r-graph on n vertices.Our motivation for studying such problems is that it allows us to give a new upper bound for an old Turán problem. We show that a 3-graph in which any four points span at most two edges has density less than , improving previous bounds of due to de Caen [D. de Caen, Extension of a theorem of Moon and Moser on complete subgraphs, Ars Combin. 16 (1983) 5–10], and due to Mubayi [D. Mubayi, On hypergraphs with every four points spanning at most two triples, Electron. J. Combin. 10 (10) (2003)].  相似文献   

18.
Let be a class of graphs on n vertices. For an integer c, let be the smallest integer such that if G is a graph in with more than edges, then G contains a cycle of length more than c. A classical result of Erdös and Gallai is that if is the class of all simple graphs on n vertices, then . The result is best possible when n-1 is divisible by c-1, in view of the graph consisting of copies of Kc all having exactly one vertex in common. Woodall improved the result by giving best possible bounds for the remaining cases when n-1 is not divisible by c-1, and conjectured that if is the class of all 2-connected simple graphs on n vertices, thenwhere , 2tc/2, is the number of edges in the graph obtained from Kc+1-t by adding n-(c+1-t) isolated vertices each joined to the same t vertices of Kc+1-t. By using a result of Woodall together with an edge-switching technique, we confirm Woodall's conjecture in this paper.  相似文献   

19.
Let hp, 1<p<∞, be the best ℓp-approximation of the element from a proper affine subspace K of , hK, and let denote the strict uniform approximation of h from K. We prove that there are a vector and a real number a, 0a1, such that
for all p>1, where with γp=o(ap/p).  相似文献   

20.
A fresh look is taken at the fractional Helly theorem for line transversals to families of convex sets in the plane. This theorem was first proved in 1980 by Katchalski and Liu [M. Katchalski, A. Liu, Symmetric twins and common transversals, Pacific J. Math. 86 (1980) 513–515]. It asserts that for every integer k≥3, there exists a real number ρ(k)(0,1) such that the following holds: If is a family of n compact convex sets in the plane, and any k or fewer members of have a line transversal, then some subfamily of of size at least has a line transversal. A lower bound on ρ(k) is obtained which is stronger than the one obtained in [M. Katchalski, A. Liu, Symmetric twins and common transversals, Pacific J. Math. 86 (1980) 513–515]. Also, examples are given to show that a conjecture of Katchalski concerning the value of ρ(3), if true, is the best possible.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号