TAILIEUCHUNG - Báo cáo toán học: " On randomly generated non-trivially intersecting hypergraphs"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: On randomly generated non-trivially intersecting hypergraphs. | On randomly generated non-trivially intersecting hypergraphs Balazs Patkós Submitted May 25 2009 Accepted Feb 2 2010 Published Feb 8 2010 Mathematics Subject Classification 05C65 05D05 05D40 Abstract We propose two procedures to choose members of nt sequentially at random to form a non-trivially intersecting hypergraph. In both cases we show what is the limiting probability that if r cnn1 3 with cn c then the process results in a Hilton-Milner-type hypergraph. 1 Introduction In 1961 Erdos Ko and Rado 5 proved that if 2r n then the edge set E of an intersecting r-uniform hypergraph with vertex set V and V n cannot have larger size than 1-1 moreover if 2r n then the only hypergraphs with that many edges are of the form e G t v G e for some fixed v G V. In the past almost five decades the area of intersection theorems has been widely studied but randomized versions of the Erdos-Ko-Rado theorem have only attracted the attention of researchers recently. There are mainly two approaches to the randomized problem. Balogh Bohman and Mubayi 2 considered the problem of finding the largest intersecting hypergraph in the probability space Gr n p of all labeled r-uniform hypergraphs on n vertices where every hyperedge appears randomly and independently with probability p p n . In this paper we follow the approach of Bohman et al. 3 4 . They considered the following process to generate an intersecting hypergraph by selecting edges sequentially and randomly. Choose Random Intersecting System Choose e1 G nt uniformly at random. Given F e1 . ei let A Fi e G nt e G ii V1 c j c i e n ej 0 . Choose ei 1 uniformly at random from A Fi . The procedure halts when A Fi 0 and F F is then output by the procedure. Department of Computer Science The University of Memphis Memphis TN 38152 USA. Supported by NSF Grant CCF-0728928. E-mail bpatkos@ patkos@ the electronic journal of combinatorics 17 2010 R26 1 Theorem Bohman et al. 3 Let Er n denote the event that F n-ỉ . Then

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học