共查询到20条相似文献,搜索用时 15 毫秒
1.
M. Lorea 《Discrete Mathematics》1978,22(3):281-285
Let α(H) be the stability number of a hypergraph H = (X, ). T(n, k, α) is the smallest q such that there exists a k-uniform hypergraph H with n vertices, q edges and with α(H) ? α. A k-uniform hypergraph H, with n vertices, T(n, k, α) edges and α(H) ?α is a Turan hypergraph. The value of T(n, 2, α) is given by a theorem of Turan. In this paper new lower bounds to T(n, k, α) are obtained and it is proved that an infinity of affine spaces are Turan hypergraphs. 相似文献
2.
A r-uniform hypergraph H (or a r-graph, for short) is a collection E = E(H) of r-element subsets (called edges) of a set V = V(H) (called vertices). We say a r-graph H is (n, e)-unavoidable if every r-graph with n vertices and e edges must contain H. In this paper we investigate the largest possible number of edges in an (n, e)-unavoidable 3-graph for fixed n and e. We also study the structure of such unavoidable 3-graphs. 相似文献
3.
J. Beck 《Discrete Mathematics》1978,24(2):127-137
Let be uniform hypergraph. In the present paper I prove that of then the chromatic number of is equal to 2. I have a result in the general (not necessarily uniform) case too. 相似文献
4.
5.
6.
Sergei L. Bezrukov 《Discrete Mathematics》2007,307(14):1737-1753
We study edge-isoperimetric problems (EIP) for hypergraphs and extend some technique in this area from graphs to hypergraphs. In particular, we establish some new results on a relationship between the EIP and some extremal poset problems, and apply them to obtain an exact solution of the EIP for certain hypergraph families. We also show how to solve the EIP on hypergraphs in some cases when the link to posets does not work. Another outcome of our results is a new series of hypergraphs admitting nested solutions in the EIP. 相似文献
7.
Sebastian M. Cioab Andr Kündgen Jacques Verstraëte 《Journal of Combinatorial Theory, Series A》2009,116(7):1232-1234
We study the minimum number of complete r-partite r-uniform hypergraphs needed to partition the edges of the complete r-uniform hypergraph on n vertices and we improve previous results of Alon. 相似文献
8.
9.
Alexandr Kostochka Dhruv Mubayi Jacques Verstraëte 《Random Structures and Algorithms》2014,44(2):224-239
The independence number of a hypergraph H is the size of a largest set of vertices containing no edge of H. In this paper, we prove that if Hn is an n‐vertex ‐uniform hypergraph in which every r‐element set is contained in at most d edges, where , then where satisfies as . The value of cr improves and generalizes several earlier results that all use a theorem of Ajtai, Komlós, Pintz, Spencer and Szemerédi (J Comb Theory Ser A 32 (1982), 321–335). Our relatively short proof extends a method due to Shearer (Random Struct Algorithms 7 (1995), 269–271) and Alon (Random Struct Algorithms 9 (1996), 271–278). The above statement is close to best possible, in the sense that for each and all values of , there are infinitely many Hn such that where depends only on r. In addition, for many values of d we show as , so the result is almost sharp for large r. We give an application to hypergraph Ramsey numbers involving independent neighborhoods.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 224‐239, 2014 相似文献
10.
11.
Mordechai Lewin 《Journal of Combinatorial Theory, Series B》1983,34(2):229-232
The sum of the cardinalities of all the edges of a hypergraph is computed in two different ways. This result is used to treat the generalisation of the notion of cyclomatic number for hypergraphs. Among others the following result is obtained: The cyclomatic number of the hypergraph H vanishes if and only if some maximum forest of the weighted intersection graph of H has the property that for every vertex of H the subgraph of the forest induced by those edges containing that vertex is connected. 相似文献
12.
Recently, Mubayi and Wang showed that for and , the number of -vertex -graphs that do not contain any loose cycle of length is at most . We improve this bound to . 相似文献
13.
This paper deals with an extremal problem concerning hypergraph colorings. Let k be an integer. The problem is to find the value m
k
(n) equal to the minimum number of edges in an n-uniform hypergraph not admitting two-colorings of the vertex set such that every edge of the hypergraph contains k vertices of each color. In this paper, we obtain the exact values of m
2(5) and m
2(4), and the upper bounds for m
3(7) and m
4(9). 相似文献
14.
Mordechai Lewin 《Journal of Combinatorial Theory, Series B》1976,20(1):80-83
A property of the intersection multigraph of a hypergraph is displayed. This property is then used to obtain an equality connecting the order of the hypergraph, the sizes of its edges and the number of edges of its intersection multigraph. At the end a generalization by Las Vergnas of a result of Lovász is given another proof. 相似文献
15.
Let be a k-uniform hypergraph on [n] where k−1 is a power of some prime p and n≥ n
0(k). Our main result says that if , then there exists E
0∊ such that {E∩ E
0: E∊ } contains all subsets of E
0. This improves a longstanding bound of due to Frankl and Pach [7].Research supported in part by NSF grants DMS-0400812 and an Alfred P. Sloan Research Fellowship.Research supported in part by NSA grant H98230-05-1-0079. Part of this research was done while working at University of Illinois at Chicago. 相似文献
16.
Yanna Wang 《Linear and Multilinear Algebra》2018,66(11):2232-2246
17.
18.
19.
We denote byK
k
,k, 2, the set of allk-uniform hypergraphsK which have the property that every element subset of the base ofK is a subset of one of the hyperedges ofK. So, the only element inK
2
2
are the complete graphs. If is a subset ofK
k
then there is exactly one homogeneous hypergraphH
whose age is the set of all finite hypergraphs which do not embed any element of . We callH
-free homogeneous graphsH
n
have been shown to be indivisible, that is, for any partition ofH
n
into two classes, oue of the classes embeds an isomorphic copy ofH
n
. [5]. Here we will investigate this question of indivisibility in the more general context of-free homogeneous hypergraphs. We will derive a general necessary condition for a homogeneous structure to be indivisible and prove that all-free hypergraphs for K
k
with 3 are indivisible. The-free hypergraphs with K
k
2
satisfy a weaker form of indivisibility which was first shown by Henson [2] to hold forH
n
. The general necessary condition for homogeneous structures to be indivisible will then be used to show that not all-free homogeneous hypergraphs are indivisible.This research has been supported by NSERC grant 69–1325. 相似文献
20.
We study sufficient conditions for Hamiltonian cycles in hypergraphs, and obtain both Turán- and Dirac-type results. While the Turán-type result gives an exact threshold for the appearance of a Hamiltonian cycle in a hypergraph depending only on the extremal number of a certain path, the Dirac-type result yields a sufficient condition relying solely on the minimum vertex degree. 相似文献