Journal: Random Structures & Algorithms

Abbreviation

Random struct. algorithms

Publisher

Wiley

Journal Volumes

ISSN

1042-9832
1098-2418

Description

Filters

Reset filters

Search Results

Publications 1 - 10 of 69
  • The random k-matching-free process
    Item type: Conference Paper
    Krivelevich, Michael; Kwan, Matthew; Loh, Po-Shen; et al. (2018)
    Random Structures & Algorithms
  • The size‐Ramsey number of short subdivisions
    Item type: Journal Article
    Draganić, Nemanja; Krivelevich, Michael; Nenadov, Rajko (2021)
    Random Structures & Algorithms
    The r-size-Ramsey number (R) over cap (r)(H) of a graph H is the smallest number of edges a graph G can have such that for every edge-coloring of G with r colors there exists a monochromatic copy of H in G. For a graph H, we denote by H-q the graph obtained from H by subdividing its edges with q - 1 vertices each. In a recent paper of Kohayakawa, Retter and Rodl, it is shown that for all constant integers q, r >= 2 and every graph H on n vertices and of bounded maximum degree, the r-size-Ramsey number of H-q is at most (log n)(20(q-1))n(1+1/q), for n large enough. We improve upon this result using a significantly shorter argument by showing that (R) over cap (r)(H-q) <= O(n(1+1/q)) for any such graph H.
  • Covering cycles in sparse graphs
    Item type: Journal Article
    Mousset, Frank; Škorić, Nemanja; Trujić, Miloš (2022)
    Random Structures & Algorithms
    Let k ≥ 2 be integer. Kouider and Lonc proved that the vertex set of every graph G with n ≥ n0(k) verticles and minimum degree at least n/k can be covered by k-1 cycles. Our main result states that for every α > 0 and p = p(n) ϵ (0,1], the same conclusion holds for graphs G with minimum degree (1/k+ α(np that are sparse in the sense that eG(X,Y)≤p|X||Y| + o(np√|X||Y/log3n) ꓯY ⊆ V(G). In particular, this allows us to determine the local resilience of random and pseudorandom graphs with respect to having a vertex cover by a fixed number of cycles. The proof uses a version of the absorbing method in sparse expander graphs.
  • Testing linear inequalities of subgraph statistics
    Item type: Journal Article
    Gishboliner, Lior; Shapira, Asaf; Stagni, Henrique (2021)
    Random Structures & Algorithms
  • K-5-free subgraphs of random graphs
    Item type: Journal Article
    Gerke, S.; Schickinger, T.; Steger, Angelika (2004)
    Random Structures & Algorithms
  • On connectivity in random graph models with limited dependencies
    Item type: Journal Article
    Lengler, Johannes; Martinsson, Anders; Petrova, Kalina; et al. (2024)
    Random Structures & Algorithms
  • Biased Games on Random Boards
    Item type: Journal Article
    Ferber, Asaf; Glebov, Roman; Krivelevich, Michael; et al. (2015)
    Random Structures & Algorithms
  • Bootstrap percolation with inhibition
    Item type: Journal Article
    Einarsson, Hafsteinn; Lengler, Johannes; Mousset, Frank; et al. (2019)
    Random Structures & Algorithms
  • Turán's theorem in sparse random graphs
    Item type: Journal Article
    Szabó, Tibor; Vu, Van H. (2003)
    Random Structures & Algorithms
  • Testing versus estimation of graph properties, revisited
    Item type: Journal Article
    Shapira, Asaf; Kushnir, Nick; Gishboliner, Lior (2024)
    Random Structures & Algorithms
Publications 1 - 10 of 69