排序方式: 共有134条查询结果,搜索用时 15 毫秒
1.
2.
Fabrício S. Benevides Dániel Gerbner Cory T. Palmer Dominik K. Vu 《Discrete Mathematics》2018,341(1):143-150
We examine the following version of a classic combinatorial search problem introduced by Rényi: Given a finite set of elements we want to identify an unknown subset of , which is known to have exactly elements, by means of testing, for as few as possible subsets of , whether intersects or not. We are primarily concerned with the non-adaptive model, where the family of test sets is specified in advance, in the case where each test set is of size at most some given natural number . Our main results are nearly tight bounds on the minimum number of tests necessary when and are fixed and is large enough. 相似文献
3.
András Gyárfás 《组合设计杂志》2015,23(8):321-327
A cross‐free set of size m in a Steiner triple system is three pairwise disjoint m‐element subsets such that no intersects all the three ‐s. We conjecture that for every admissible n there is an STS(n) with a cross‐free set of size which if true, is best possible. We prove this conjecture for the case , constructing an STS containing a cross‐free set of size 6k. We note that some of the 3‐bichromatic STSs, constructed by Colbourn, Dinitz, and Rosa, have cross‐free sets of size close to 6k (but cannot have size exactly 6k). The constructed STS shows that equality is possible for in the following result: in every 3‐coloring of the blocks of any Steiner triple system STS(n) there is a monochromatic connected component of size at least (we conjecture that equality holds for every admissible n). The analog problem can be asked for r‐colorings as well, if and is a prime power, we show that the answer is the same as in case of complete graphs: in every r‐coloring of the blocks of any STS(n), there is a monochromatic connected component with at least points, and this is sharp for infinitely many n. 相似文献
4.
Mengyao Sun 《代数通讯》2018,46(11):4830-4843
In this paper, we study the regularity and projective dimension of edge ideals. We provide two upper bounds for the regularity of edge ideals of vertex decomposable graphs in terms of the induced matching number and the number of cycles. Also, we generalize one of the upper bounds given by Dao and Schweig for the projective dimension of hypergraphs. 相似文献
5.
《Random Structures and Algorithms》2018,53(2):238-288
The phase transition in the size of the giant component in random graphs is one of the most well‐studied phenomena in random graph theory. For hypergraphs, there are many possible generalizations of the notion of a connected component. We consider the following: two j‐sets (sets of j vertices) are j‐connected if there is a walk of edges between them such that two consecutive edges intersect in at least j vertices. A hypergraph is j‐connected if all j‐sets are pairwise j‐connected. In this paper, we determine the asymptotic size of the unique giant j‐connected component in random k‐uniform hypergraphs for any and . 相似文献
6.
In this paper we study the family of oriented transitive 3-hypergraphs that arise from cyclic permutations and intervals in the circle, in order to search for the notion of perfection on hypergraphs. 相似文献
7.
In this paper we show that e/n is the sharp threshold for the existence of tight Hamilton cycles in random k ‐uniform hypergraphs, for all k ≥ 4. When k = 3 we show that 1/n is an asymptotic threshold. We also determine thresholds for the existence of other types of Hamilton cycles. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013 相似文献
8.
In this paper, we study lower bounds on the size of a maximum independent set and a maximum matching in a hypergraph of rank three. The rank in a hypergraph is the size of a maximum edge in the hypergraph. A hypergraph is simple if no two edges contain exactly the same vertices. Let H be a hypergraph and let and be the size of a maximum independent set and a maximum matching, respectively, in H, where a set of vertices in H is independent (also called strongly independent in the literature) if no two vertices in the set belong to a common edge. Let H be a hypergraph of rank at most three and maximum degree at most three. We show that with equality if and only if H is the Fano plane. In fact, we show that if H is connected and different from the Fano plane, then and we characterize the hypergraphs achieving equality in this bound. Using this result, we show that that if H is a simple connected 3‐uniform hypergraph of order at least 8 and with maximum degree at most three, then and there is a connected 3‐uniform hypergraph H of order 19 achieving this lower bound. Finally, we show that if H is a connected hypergraph of rank at most three that is not a complete hypergraph on vertices, where denotes the maximum degree in H, then and this bound is asymptotically best possible. © 2012 Wiley Periodicals, Inc. J. Graph Theory 相似文献
9.
在本文,我们研究谱半径至多为$\sqrt[r]{2+\sqrt{5}}$的超图.我们得到此种超图必须具有一个基普结构,这与Woo-Neumaier在2007年对谱半径至多为$\frac{3}{2}\sqrt{2}$的图的分类结果类似. 相似文献
10.
Klas Markström 《Journal of Graph Theory》2014,76(2):101-105
For ordinary graphs it is known that any graph G with more edges than the Turán number of must contain several copies of , and a copy of , the complete graph on vertices with one missing edge. Erd?s asked if the same result is true for , the complete 3‐uniform hypergraph on s vertices. In this note, we show that for small values of n, the number of vertices in G, the answer is negative for . For the second property, that of containing a , we show that for the answer is negative for all large n as well, by proving that the Turán density of is greater than that of . 相似文献