본문 바로가기
HOME> 저널/프로시딩 > 저널/프로시딩 검색상세

저널/프로시딩 상세정보

권호별목차 / 소장처보기

H : 소장처정보

T : 목차정보

Combinatorics, probability & computing : CPC 10건

  1. [해외논문]   Diameter of the Stochastic Mean-Field Model of Distance   SCIE

    BHAMIDI, SHANKAR , VAN DER HOFSTAD, REMCO
    Combinatorics, probability & computing : CPC v.26 no.6 ,pp. 797 - 825 , 2017 , 0963-5483 ,

    초록

    We consider the complete graph 𝜅n on n vertices with exponential mean n edge lengths. Writing Cij for the weight of the smallest-weight path between vertices i, j ∈ [ n ], Janson [18] showed that max i,j ∈[ n ] C ij /log n converges in probability to 3. We extend these results by showing that max i,j ∈[ n ] Cij − 3 log n converges in distribution to some limiting random variable that can be identified via a maximization procedure on a limiting infinite random structure. Interestingly, this limiting random variable has also appeared as the weak limit of the re-centred graph diameter of the barely supercritical Erdős-REnyi random graph in [22].

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  2. [해외논문]   Maximal Steiner Trees in the Stochastic Mean-Field Model of Distance   SCIE

    DAVIDSON, A. , GANESH, A.
    Combinatorics, probability & computing : CPC v.26 no.6 ,pp. 826 - 838 , 2017 , 0963-5483 ,

    초록

    Consider the complete graph on n vertices, with edge weights drawn independently from the exponential distribution with unit mean. Janson showed that the typical distance between two vertices scales as log n/n , whereas the diameter (maximum distance between any two vertices) scales as 3 log n/n . BollobAs, Gamarnik, Riordan and Sudakov showed that, for any fixed k , the weight of the Steiner tree connecting k typical vertices scales as ( k − 1)log n/n , which recovers Janson's result for k = 2. We extend this to show that the worst case k -Steiner tree, over all choices of k vertices, has weight scaling as (2 k − 1)log n/n and finally, we generalize this result to Steiner trees with a mixture of typical and worst case vertices.

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  3. [해외논문]   Packing Loose Hamilton Cycles   SCIE

    FERBER, ASAF , LUH, KYLE , MONTEALEGRE, DANIEL , NGUYEN, OANH
    Combinatorics, probability & computing : CPC v.26 no.6 ,pp. 839 - 849 , 2017 , 0963-5483 ,

    초록

    A subset C of edges in a k -uniform hypergraph H is a loose Hamilton cycle if C covers all the vertices of H and there exists a cyclic ordering of these vertices such that the edges in C are segments of that order and such that every two consecutive edges share exactly one vertex. The binomial random k -uniform hypergraph H k n,p has vertex set [ n ] and an edge set E obtained by adding each k -tuple e ∈ ($\binom{[n]}{k}$) to E with probability p , independently at random. Here we consider the problem of finding edge-disjoint loose Hamilton cycles covering all but o (| E |) edges, referred to as the packing problem . While it is known that the threshold probability of the appearance of a loose Hamilton cycle in H k n,p is $p=\Theta\biggl(\frac{\log n}{n^{k-1}}\biggr),$ the best known bounds for the packing problem are around p = polylog( n )/ n . Here we make substantial progress and prove the following asymptotically (up to a polylog( n ) factor) best possible result: for p ≥ log C n / n k −1 , a random k -uniform hypergraph H k n,p with high probability contains $N:=(1-o(1))\frac{\binom{n}{k}p}{n/(k-1)}$ edge-disjoint loose Hamilton cycles. Our proof utilizes and modifies the idea of 'online sprinkling' recently introduced by Vu and the first author.

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  4. [해외논문]   Generalized Majority Colourings of Digraphs   SCIE

    GIRÃ , O, ANTÓ , NIO , KITTIPASSORN, TEERADEJ , POPIELARZ, KAMIL
    Combinatorics, probability & computing : CPC v.26 no.6 ,pp. 850 - 855 , 2017 , 0963-5483 ,

    초록

    We almost completely solve a number of problems related to a concept called majority colouring recently studied by Kreutzer, Oum, Seymour, van der Zypen and Wood. They raised the problem of determining, for a natural number k , the smallest number m = m ( k ) such that every digraph can be coloured with m colours where each vertex has the same colour as at most a 1/ k proportion of its out-neighbours. We show that m ( k ) ∈ {2 k − 1,2 k }. We also prove a result supporting the conjecture that m (2) = 3. Moreover, we prove similar results for a more general concept called majority choosability.

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  5. [해외논문]   Exact Minimum Codegree Threshold for K−4-Factors   SCIE

    HAN, JIE , LO, ALLAN , TREGLOWN, ANDREW , ZHAO, YI
    Combinatorics, probability & computing : CPC v.26 no.6 ,pp. 856 - 885 , 2017 , 0963-5483 ,

    초록

    Given hypergraphs F and H , an F -factor in H is a set of vertex-disjoint copies of F which cover all the vertices in H . Let K − 4 denote the 3-uniform hypergraph with four vertices and three edges. We show that for sufficiently large n ∈ 4ℕ, every 3-uniform hypergraph H on n vertices with minimum codegree at least n /2−1 contains a K − 4-factor. Our bound on the minimum codegree here is best possible. It resolves a conjecture of Lo and MarkstrOm [15] for large hypergraphs, who earlier proved an asymptotically exact version of this result. Our proof makes use of the absorbing method as well as a result of Keevash and Mycroft [11] concerning almost perfect matchings in hypergraphs.

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  6. [해외논문]   The Structure of Typical Eye-Free Graphs and a TurAn-Type Result for Two Weighted Colours   SCIE

    KEEVASH, PETER , LOCHET, WILLIAM
    Combinatorics, probability & computing : CPC v.26 no.6 ,pp. 886 - 910 , 2017 , 0963-5483 ,

    초록

    The ( a , b )-eye is the graph I a,b = < K a+b \ K b obtained by deleting the edges of a clique of size b from a clique of size a+b . We show that for any a,b ≥ 2 and p ∈ (0,1), if we condition the random graph G ~ G ( n,p ) on having no induced copy of I a,b , then with high probability G is close to an a -partite graph or the complement of a ( b −1)-partite graph. Our proof uses the recently developed theory of hypergraph containers, and a stability result for an extremal problem with two weighted colours. We also apply the stability method to obtain an exact TurAn-type result for this extremal problem.

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  7. [해외논문]   Fractional Clique Decompositions of Dense Partite Graphs   SCIE

    MONTGOMERY, RICHARD
    Combinatorics, probability & computing : CPC v.26 no.6 ,pp. 911 - 943 , 2017 , 0963-5483 ,

    초록

    We give a minimum degree condition sufficient to ensure the existence of a fractional Kr -decomposition in a balanced r -partite graph (subject to some further simple necessary conditions). This generalizes the non-partite problem studied recently by Barber, Lo, KUhn, Osthus and the author, and the 3-partite fractional K 3-decomposition problem studied recently by Bowditch and Dukes. Combining our result with recent work by Barber, KUhn, Lo, Osthus and Taylor, this gives a minimum degree condition sufficient to ensure the existence of a (non-fractional) Kr -decomposition in a balanced r -partite graph (subject to the same simple necessary conditions).

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  8. [해외논문]   Corners Over Quasirandom Groups   SCIE

    ZORIN-KRANICH, PAVEL
    Combinatorics, probability & computing : CPC v.26 no.6 ,pp. 944 - 951 , 2017 , 0963-5483 ,

    초록

    Let G be a finite D -quasirandom group and A ⊂ G k a δ-dense subset. Then the density of the set of side lengths g of corners $$ \{(a_{1},\dotsc,a_{k}),(ga_{1},a_{2},\dotsc,a_{k}),\dotsc,(ga_{1},\dotsc,ga_{k})\} \subset A $$ converges to 1 as D → ∞.

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  9. [해외논문]   Erratum For 'A Bound on the Number of Edges in Graphs Without an Even Cycle'   SCIE

    BUKH, BORIS , JIANG, ZILIN
    Combinatorics, probability & computing : CPC v.26 no.6 ,pp. 952 - 953 , 2017 , 0963-5483 ,

    초록

    Due to a calculation error, the constant in the main theorem is not $80 \sqrt{k\log k}$ but $80\sqrt{k} \log k$. The error was discovered by Xizhi Liu. For a new discussion on the limit of the method used in this paper see the revised arXiv version of the paper.

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  10. [해외논문]   Corrigendum to 'Mixing, Communication Complexity and Conjectures of Gowers and Viola'   SCIE

    SHALEV, ANER
    Combinatorics, probability & computing : CPC v.26 no.6 ,pp. 954 - 955 , 2017 , 0963-5483 ,

    초록

    In my paper [1], a normalization factor of | G | −1 was missing in the statements of Theorem 2.4, Theorem 2.6 and Corollary 2.7.

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지

논문관련 이미지