27 citations · 63 across the 12 of their papers we have counts for
14 papers
Short Point Lists for CNFs and Stronger Constant-Depth Circuit Hardness
Xin Li, Yan Zhong
We give a short-description decomposition of bounded-width CNFs. For every fixed , every width- CNF on variables is an exact disjoint union of at most $2^{\va…
Subgraph probabilities in random intersection graphs
Katarzyna Rybarczyk, Grzegorz Serafin
Since their introduction by Karoński, Scheinerman, and Singer-Cohen in 90's, random intersection graphs have attracted much attention, mostly due to their various applications. In…
Arrangements of Consecutive Numbers in Mallows Permutations
Katarzyna Rybarczyk
We study the random variable that counts the number of specific arrangements of clustered consecutive numbers in permutations under the Mallows distribution. We provide an asymptot…
Note on edge expansion and modularity in preferential attachment graphs
Colin McDiarmid, Katarzyna Rybarczyk, Fiona Skerman +1
Edge expansion is a parameter indicating how well-connected a graph is. It is useful for designing robust networks, analysing random walks or information flow through a network and…
New bounds on the modularity of
Katarzyna Rybarczyk, Małgorzata Sulkowska
Modularity is a parameter indicating the presence of community structure in the graph. Nowadays it lies at the core of widely used clustering algorithms. We study the modularity of…
Normal approximation for subgraph counts in random intersection graphs: the case of edges
Katarzyna Rybarczyk, Grzegorz Serafin
We investigate the subgraph count in the random intersection graph model . Due to substantial edge dependencies, studying even such fundamental statistics is sig…
Modularity of random intersection graphs
Katarzyna Rybarczyk
Modularity was introduced by Newman and Girvan in 2004 and is used as a measure of community structure of networks represented by graphs. In our work we study modularity of the ran…
Modularity of preferential attachment graphs
Katarzyna Rybarczyk, Małgorzata Sulkowska
We study the preferential attachment model . A graph is generated from a finite initial graph by adding new vertices one at a time. Each new vertex connects to $h\ge…
The cover time of a sparse random intersection graph
Mindaugas Bloznelis, Jerzy Jaworski, Katarzyna Rybarczyk
Many known networks have structure of affiliation networks, where each of network's nodes (actors) selects an attribute set from a given collection of attributes and two no…
Finding Hamilton cycles in random intersection graphs
Katarzyna Rybarczyk
The construction of the random intersection graph model is based on a random family of sets. Such structures, which are derived from intersections of sets, appear in a natural mann…
Poisson approximation of counts of subgraphs in random intersection graphs
Katarzyna Rybarczyk, Dudley Stark
Random intersection graphs are characterized by three parameters: , and , where is the number of vertices, is the number of objects, and is the probability th…
The coupling method for inhomogeneous random intersection graphs
K. Rybarczyk
We present new results concerning threshold functions for a wide family of random intersection graphs. To this end we apply the coupling method used for establishing threshold func…
Sharp threshold functions for the random intersection graph via coupling method?
Katarzyna Rybarczyk
We will present a new method, which enables us to find threshold functions for many properties in random intersection graphs. This method will be used to establish sharp threshold…
Equivalence of the random intersection graph and G(n,p)
Katarzyna Rybarczyk
We solve the conjecture posed by Fill, Scheinerman and Singer-Cohen and show the equivalence of the sharp threshold functions of the random intersection graph G(n,m,p) with $m >= n…