排序方式: 共有8条查询结果,搜索用时 15 毫秒
1
1.
Alon Noga; Bollobas Bela; Kim Jeong Han; Vu Van H. 《Proceedings London Mathematical Society》2003,86(2):273-301
A cover of a hypergraph is a collection of edges whose unioncontains all vertices. Let H = (V, E) be a k-uniform, D-regularhypergraph on n vertices, in which no two vertices are containedin more than o(D/e2k log D) edges as D tends to infinity. Ourresults include the fact that if k = o(log D), then there isa cover of (1 + o(1))n/k edges, extending the known result thatthis holds for fixed k. On the other hand, if k 4 log D thenthere are k-uniform, D-regular hypergraphs on n vertices inwhich no two vertices are contained in more than one edge, andyet the smallest cover has at least (nk) log (k log D)) edges.Several extensions and variants are also obtained, as well asthe following geometric application. The minimum number of linesrequired to separate n random points in the unit square is,almost surely, (n2/3 / (log n)1/3). 2000 Mathematical SubjectClassification: 05C65, 05D15, 60D05. 相似文献
2.
Given a graph G, denote by tcl(G) the largest integer r for which G contains a TKr, a toplogical complete r-graph. We show that for every ? > 0 almost every graph G of order n satisfies 相似文献
3.
A convex corner is a compact convex down-set of full dimensionin Rn. Convex corners arise in graph theory, for instance asstable set polytopes of graphs. They are also natural objects of study in geometry, as they correspond to 1-unconditionalnorms in an obvious way. In this paper, we study a parameterof convex corners, which we call the content, that is relatedto the volume. This parameter has appeared implicitly before:both in geometry, chiefly in a paper of Meyer (Israel J. Math.} 55 (1986) 317327) effectively using content to givea proof of Saint-Raymond's Inequality on the volume product of a convex corner, and in combinatorics, especially in apaper of Sidorenko (Order} 8 (1991) 331340) relatingcontent to the number of linear extensions of a partial order.One of our main aims is to expose connections between workin these two areas. We prove many new results, giving in particular various generalizations of Saint-Raymond's Inequality. Contentalso behaves well under the operation of pointwise product oftwo convex corners; our results enable us to give counter-examplesto two conjectures of Bollobás and Leader Oper. TheoryAdv. Appl. 77 (1995) 1324) on pointwise products. 1991Mathematics Subject Classification: 52C07, 51M25, 52B11, 05C60,06A07. 相似文献
4.
Bollobas B.; Kohayakawa Y.; Rodl V.; Schacht M.; Taraz A. 《Proceedings London Mathematical Society》2007,95(3):709-734
We consider edge colourings of the complete r-uniform hypergraphKn(r)on n vertices. How many colours may such a colouring haveif we restrict the number of colours locally? The local restrictionis formulated as follows: for a fixed hypergraph H and an integerk we call a colouring (H, k)-local if every copy of H in thecomplete hypergraph Kn(r) receives at most k different colours. We investigate the threshold for k that guarantees that every(H, k)-local colouring of Kn(r) must have a globally boundednumber of colours as n , and we establish this threshold exactly.The following phenomenon is also observed: for many H (at leastin the case of graphs), if k is a little over this threshold,the unbounded (H, k)-local colourings exhibit their colourfulnessin a sparse way; more precisely, a bounded numberof colours are dominant while all other colours are rare. Hencewe study the threshold k0 for k that guarantees that every (H,k)-local colouring n of Kn(r) with k k0 must have a globallybounded number of colours after the deletion of up to nr edgesfor any fixed > 0 (the bound on the number of colours isallowed to depend on H and only); we think of such colouringsn as essentially finite. As it turns out, everyessentially infinite colouring is closely related to a non-monochromaticcanonical Ramsey colouring of Erdös and Rado. This secondthreshold is determined up to an additive error of 1 for everyhypergraph H. Our results extend earlier work for graphs byClapsadle and Schelp [Local edge colorings that are global,J. Graph Theory 18 (1994) 389–399] and by the first twoauthors and Schelp [Essentially infinite colourings ofgraphs, J. London Math. Soc. (2) 61 (2000) 658–670].We also consider a related question for colourings of the integersand arithmetic progressions.
2000 Mathematics Subject Classification 05D10 (primary), 05C35(secondary). The first author was partially supported by NSF grants CCR 0225610and DMS 0505550. The second author was partially supported byFAPESP and CNPq through a Temático–ProNEx project(Proc. FAPESP 2003/09925–5) and by CNPq (Proc. 306334/2004–6and 479882/2004–5). The third author was partially supportedby NSF grant DMS 0300529. The fourth author was partly supportedby the DFG within the European graduate program Combinatorics,Geometry, and Computation (No. GRK 588/2) and by DFGgrant SCHA 1263/1–1. This work was supported in part bya CAPES/DAAD collaboration grant. 相似文献
2000 Mathematics Subject Classification 05D10 (primary), 05C35(secondary). The first author was partially supported by NSF grants CCR 0225610and DMS 0505550. The second author was partially supported byFAPESP and CNPq through a Temático–ProNEx project(Proc. FAPESP 2003/09925–5) and by CNPq (Proc. 306334/2004–6and 479882/2004–5). The third author was partially supportedby NSF grant DMS 0300529. The fourth author was partly supportedby the DFG within the European graduate program Combinatorics,Geometry, and Computation (No. GRK 588/2) and by DFGgrant SCHA 1263/1–1. This work was supported in part bya CAPES/DAAD collaboration grant. 相似文献
5.
We give a short proof of the fundamental result that the criticalprobability for bond percolation in the planar square latticeZ2 is equal to 1/2. The lower bound was proved by Harris, whoshowed in 1960 that percolation does not occur at p = 1/2. Theother, more difficult, bound was proved by Kesten, who showedin 1980 that percolation does occur for any p > 1/2. 2000Mathematics Subject Classification 60K35, 82B43. 相似文献
6.
Béla Bollobas 《Journal of Combinatorial Theory, Series B》1978,25(3):363-366
Mader [Arch. Math. 23 (1972), 219–224] determined the minimal number of 1-factors in a 2k-connected graph having at least one 1-factor. We give a simple proof of this result and slightly extend it. 相似文献
7.
Projections of Bodies and Hereditary Properties of Hypergraphs 总被引:2,自引:0,他引:2
We prove that for every n-dimensional body K, there is a rectangularparallelepiped B of the same volume as K, such that the projectionof B onto any coordinate subspace is at most as large as thatof the corresponding projection of K. We apply this theorem to projections of finite set systems andto hereditary properties. In particular, we show that everyhereditary property of uniform hypergraphs has a limiting density. 相似文献
8.
We consider cyclic graphs, that is, graphs with cyclic ordersat the vertices, corresponding to 2-cell embeddings of graphsinto orientable surfaces, or combinatorial maps. We constructa three variable polynomial invariant of these objects, thecyclic graph polynomial, which has many of the useful propertiesof the Tutte polynomial. Although the cyclic graph polynomialgeneralizes the Tutte polynomial, its definition is very different,and it depends on the embedding in an essential way. 2000 MathematicalSubject Classification: 05C10. 相似文献
1