M. Karoński, Andrzej Ruciński,
... Poland.Search for more papers by this authorANDRZEJ RUCIŃSKI, ANDRZEJ RUCIŃSKI Department of Statistics University of Florida, Gainesville, ... Poland.Search for more papers by this authorANDRZEJ RUCIŃSKI, ANDRZEJ RUCIŃSKI Department of Statistics University of Florida, Gainesville, Florida ...
Tópico(s): Advanced Combinatorial Mathematics
1989 - Wiley | Annals of the New York Academy of Sciences
Agnieska Ziolkowska, Marcin Ruciński, Andrzej Pucher, Cinzia Tortorella, Gastone G. Nussdorfer, Ludwick K. Malendowicz,
Compelling evidence indicates that some endocrine disrupters (EDs), acting as selective estrogen-receptor modulators, interfere with osteoblast differentiation and function. Hence, we investigated whether four EDs [bisphenol-A (BSP), benzophenone-3 (BP3), resveratrol and silymarin] affect differentiation and growth of rat calvarial osteoblast-like (ROB) cells in primary in vitro culture. ROB cells were cultured for up 30 days in a medium supplemented with fetal calf serum (FCS), and conventional RT-PCR ...
Tópico(s): Animal testing and alternatives
2006 - Elsevier BV | Chemico-Biological Interactions
Michał Karoński, Andrzej Ruciński,
Barbour [l] invented an ingenious method of establishing the asymptotic distribution of the number X of specified subgraphs of a random graph. The novelty of his method relies on using the first two moments of X only, despite the traditional method of moments that involves all moments of X (compare [ 8, 10, 11, 14 ]). He also adjusted that new method for counting isolated trees of a given size in a random graph. (For further applications of Barbour's method see [ 4 ] and [ 10 ].) The main goal of this paper is to ...
Tópico(s): Bayesian Methods and Mixture Models
1987 - Cambridge University Press | Mathematical Proceedings of the Cambridge Philosophical Society
Zbigniew Pałka, Andrzej Ruciński,
Consider a random graph K ( n , p ) with n labeled vertices in which the edges are chosen independently and with a probability p . Let T n ( p ) be the order of the largest induced tree in K ( n , p ). Among other results it is shown, using an algorithmic approach, that if p =( c log n )/ n , where c ≥ e is a constant, then for any fixed ε > 0 1 c −ε log log n log n n<T n (p)< 2 c +ε log log n log n almost surely.
Tópico(s): Computational Geometry and Mesh Generation
1986 - Elsevier BV | Discrete Applied Mathematics
Andrzej Ruciński, Andrew Vince,
Abstract The concept of strongly balanced graph is introduced. It is shown that there exists a strongly balanced graph with v vertices and e edges if and only if I ν – 1 ⩽ e ⩽( ). This result is applied to a classic question of Erdös and Rényi: What is the probability that a random graph on n vertices contains a given graph? A rooted version of this problem is also solved.
Tópico(s): Stochastic processes and statistical mechanics
1986 - Wiley | Journal of Graph Theory
A. D. Barbour, Michał Karoński, Andrzej Ruciński,
The application of Stein's method of obtaining rates of convergence to the normal distribution is illustrated in the context of random graph theory. Problems which exhibit a dissociated structure and problems which do not are considered. Results are obtained for the number of copies of a given graph G in K(n, p), for the number of induced copies of G, for the number of isolated trees of order k ≥ 2, for the number of vertices of degree d ≥ 1, and for the number of isolated vertices.
Tópico(s): Bayesian Methods and Mixture Models
1989 - Elsevier BV | Journal of Combinatorial Theory Series B
Tópico(s): Complex Network Analysis Techniques
1988 - Springer Science+Business Media | Probability Theory and Related Fields
Penny Haxell, Tomasz Łuczak, Yuejian Peng, V. Rödl, Andrzej Ruciński, Jozef Skokan,
Let C (3) n denote the 3-uniform tight cycle , that is, the hypergraph with vertices v 1 , .–.–., v n and edges v 1 v 2 v 3 , v 2 v 3 v 4 , .–.–., v n −1 v n v 1 , v n v 1 v 2 . We prove that the smallest integer N = N ( n ) for which every red–blue colouring of the edges of the complete 3-uniform hypergraph with N vertices contains a monochromatic copy of C (3) n is asymptotically equal to 4 n /3 if n is divisible by 3, and 2 n otherwise. The proof uses the regularity lemma for hypergraphs of Frankl and Rödl.
Tópico(s): Advanced Graph Theory Research
2009 - Cambridge University Press | Combinatorics Probability Computing
Vojtěch Rödl, Andrzej Ruciński, Endre Szemerédi,
We define a perfect matching in a k-uniform hypergraph H on n vertices as a set of ⌊n/k⌋ disjoint edges. Let δk−1(H) be the largest integer d such that every (k−1)-element set of vertices of H belongs to at least d edges of H. In this paper we study the relation between δk−1(H) and the presence of a perfect matching in H for k⩾3. Let t(k,n) be the smallest integer t such that every k-uniform hypergraph on n vertices and with δk−1(H)⩾t contains a perfect matching. For large n divisible by k, we completely ...
Tópico(s): Graph theory and applications
2008 - Elsevier BV | Journal of Combinatorial Theory Series A
Vojtěch Rödl, Andrzej Ruciński, Mathias Schacht, Endre Szemerédi,
Tópico(s): Random Matrices and Applications
2008 - | Commentationes Mathematicae Universitatis Carolinae
Vojtěch Rödl, Andrzej Ruciński,
Dedicated to Endre Szemerédi on the occasion of his 70th birthday In 1952 Dirac [8] proved a celebrated theorem stating that if the minimum degree δ(G) in an n-vertex graph G is at least n/2 then G contains a Hamiltonian cycle. In 1999, Katona and Kierstead initiated a new stream of research devoted to studying similar questions for hypergraphs, and subsequently, for perfect matchings. A pivotal role in achieving some of the most important results in both these areas was played by Endre Szemerédi. ...
Tópico(s): Advanced Graph Theory Research
2010 - Springer Nature | Bolyai Society mathematical studies
Marek Karpiński, Andrzej Ruciński, Edyta Szymańska,
In this paper we consider the computational complexity of deciding the existence of a perfect matching in certain classes of dense k-uniform hypergraphs. It has been known that the perfect matching problem for the classes of hypergraphs H with minimum ((k - 1)–wise) vertex degreeδ(H) at least c|V(H)| is NP-complete for [Formula: see text] and trivial for c ≥ ½, leaving the status of the problem with c in the interval [Formula: see text] widely open. In this paper we show, somehow surprisingly, that ½ is ...
Tópico(s): Limits and Structures in Graph Theory
2010 - World Scientific | International Journal of Foundations of Computer Science
Catherine Greenhill, Svante Janson, Andrzej Ruciński,
Let G be a fixed connected multigraph with no loops. A random n -lift of G is obtained by replacing each vertex of G by a set of n vertices (where these sets are pairwise disjoint) and replacing each edge by a randomly chosen perfect matching between the n -sets corresponding to the endpoints of the edge. Let X G be the number of perfect matchings in a random lift of G . We study the distribution of X G in the limit as n tends to infinity, using the small subgraph conditioning method. We present several ...
Tópico(s): Markov Chains and Monte Carlo Methods
2010 - Cambridge University Press | Combinatorics Probability Computing
Svante Janson, Andrzej Ruciński,
General upper tail estimates are given for counting edges in a random induced subhypergraph of a fixed hypergraph H, with an easy proof by estimating the moments. As an application we consider the numbers of arithmetic progressions and Schur triples in random subsets of integers. In the second part of the paper we return to the subgraph counts in random graphs and provide upper tail estimates in the rooted case.
Tópico(s): Markov Chains and Monte Carlo Methods
2010 - Mittag-Leffler Institute | Arkiv för matematik
Vojtěch Rödl, Andrzej Ruciński, Mathias Schacht,
We investigate the threshold probability for the property that every r-coloring of the edges of a random binomial k-uniform hypergraph ${\mathbb G }^{(k)}(n,p)$ yields a monochromatic copy of some fixed hypergraph G. In this paper we solve the problem for arbitrary $k\geq 3$ and k-partite, k-uniform hypergraphs G.
Tópico(s): Mathematical Dynamics and Fractals
2007 - Society for Industrial and Applied Mathematics | SIAM Journal on Discrete Mathematics
Vojtěch Rödl, Andrzej Ruciński, Endre Szemerédi,
A hamiltonian path (cycle) in an n-vertex 3-uniform hypergraph is a (cyclic) ordering of the vertices in which every three consecutive vertices form an edge. For large n, we prove an analog of the celebrated Dirac theorem for graphs: there exists n0 such that every n-vertex 3-uniform hypergraph H, n⩾n0, in which each pair of vertices belongs to at least n/2−1 (⌊n/2⌋) edges, contains a hamiltonian path (cycle, respectively). Both results are easily seen to be optimal.
Tópico(s): Finite Group Theory Research
2011 - Elsevier BV | Advances in Mathematics
Péter Frankl, Vojtěch Rödl, Andrzej Ruciński,
In 1965 Erdős conjectured a formula for the maximum number of edges in a k -uniform n -vertex hypergraph without a matching of size s . We prove this conjecture for k = 3 and all s ≥ 1 and n ≥ 4 s .
Tópico(s): graph theory and CDMA systems
2012 - Cambridge University Press | Combinatorics Probability Computing
Produção Nacional
Revisado por pares
Penny Haxell, Tomasz Łuczak, Yuejian Peng, V. Rödl, Andrzej Ruciński, Miklós Simonovits, Jozef Skokan,
Let Cn denote the 3-uniform hypergraph loose cycle, that is the hypergraph with vertices v1,…,vn and edges v1v2v3, v3v4v5, v5v6v7,…,vn-1vnv1. We prove that every red-blue colouring of the edges of the complete 3-uniform hypergraph with N vertices contains a monochromatic copy of Cn, where N is asymptotically equal to 5n/4. Moreover this result is (asymptotically) best possible.
Tópico(s): Advanced Graph Theory Research
2005 - Elsevier BV | Journal of Combinatorial Theory Series A
Andrzej Kurek, Andrzej Ruciński,
Tópico(s): Advanced Graph Theory Research
2005 - De Gruyter Open | Discussiones Mathematicae Graph Theory
Ronald Graham, Vojtěch Rödl, Andrzej Ruciński,
A classic result of I. Schur [9] asserts that for everyr⩾2 and fornsufficiently large, if the set [n]={1, 2, …, n} is partitioned intorclasses, then at least one of the classes contains a solution to the equationx+y=z. Any such solution withx≠ywill be called aSchur triple. Let us say thatA⊆[n] has theSchur propertyif for every partition (or 2-coloring) ofA=R∪B(forredandblue), there must always be formed somemonochromaticSchur triple, i.e., belonging entirely to eitherRorB. Our goal here is to show thatn1/ ...
Tópico(s): Advanced Graph Theory Research
1996 - Elsevier BV | Journal of Number Theory
Svante Janson, Krzysztof Oleszkiewicz, Andrzej Ruciński,
LetG be a fixed graph and letX G be the number of copies ofG contained in the random graphG(n, p). We prove exponential bounds on the upper tail ofX G which are best possible up to a logarithmic factor in the exponent. Our argument relies on an extension of Alon’s result about the maximum number of copies ofG in a graph with a given number of edges. Similar bounds are proved for the random graphG(n, M) too.
Tópico(s): Graph theory and applications
2004 - Hebrew University of Jerusalem | Israel Journal of Mathematics
Andrzej Dudek, Alan Frieze, Andrzej Ruciński, Matas Šileikis,
In this paper we asymptotically count d-regular k-uniform hypergraphs on n vertices, provided k is fixed and d=d(n)=o(n1/2). In doing so, we extend to hypergraphs a switching technique of McKay and Wormald.
Tópico(s): Advanced Graph Theory Research
2013 - Elsevier BV | Information Processing Letters
Vojtěch Rödl, Andrzej Ruciński,
Tópico(s): Computability, Logic, AI Algorithms
1995 - American Mathematical Society | Journal of the American Mathematical Society
Vojtěch Rödl, Andrzej Ruciński,
Probabilistic methods have been used to approach many problems of Ramsey theory. In this paper we study Ramsey type questions from the point of view of random structures. Let K ( n , N ) K(n,N) be the random graph chosen uniformly from among all graphs with n n vertices and N N edges. For a fixed graph G G and an integer r r we address the question what is the minimum N = N ( G , r , n ) N = N(G,r,n) such that the random graph K ( n , N ) K(n,N) contains, almost surely, a monochromatic copy of G G in every r r -coloring ...
Tópico(s): Advanced Graph Theory Research
1995 - American Mathematical Society | Journal of the American Mathematical Society
Ron Graham, V. Rödl, Andrzej Ruciński,
Tópico(s): Graph Labeling and Dimension Problems
2001 - Springer Science+Business Media | COMBINATORICA
Tomasz Łuczak, Andrzej Ruciński, Sebastian Urbański,
Following the arrow notation, for a graph G and natural numbers a1,a2,…,ar we write G→(a1,a2,…,ar)v if for every coloring of the vertices of G with r colors there exists a copy of the complete graph Kai of color i for some i=1,2,…,r. We present some constructions of small graphs with this Ramsey property, but not containing large cliques. We also set bounds on the order of the smallest such graphs.
Tópico(s): Advanced Graph Theory Research
2001 - Elsevier BV | Discrete Mathematics
Produção Nacional
Revisado por pares
Noga Alon, Michael Capalbo, Yoshiharu Kohayakawa, Vojtěch Rödl, Andrzej Ruciński, Endre Szemerédi,
Let $$ \mathcal{H} $$ be a family of graphs. We say that G is $$ \mathcal{H} $$ -universal if, for each H ∈ $$ \mathcal{H} $$ , the graph G contains a subgraph isomorphic to H. Let $$ \mathcal{H} $$ (k, n) denote the family of graphs on n vertices with maximum degree at most k. For each fixed k and each n sufficiently large, we explicitly construct an $$ \mathcal{H} $$ (k, n)-universal graph Γ(k, n) with O(n 2 - 2/k (log n)1+8/k ) edges. This is optimal up to a small polylogarithmic factor, as Ω(n 2-2/k ) is a lower bound for the number of edges ...
Tópico(s): Complexity and Algorithms in Graphs
2001 - Springer Science+Business Media | Lecture notes in computer science
Yuejian Peng, Vojtěch Rödl, Andrzej Ruciński,
The celebrated Regularity Lemma of Szemerédi asserts that every sufficiently large graph $G$ can be partitioned in such a way that most pairs of the partition sets span $\epsilon$-regular subgraphs. In applications, however, the graph $G$ has to be dense and the partition sets are typically very small. If only one $\epsilon$-regular pair is needed, a much bigger one can be found, even if the original graph is sparse. In this paper we show that every graph with density $d$ contains a large, relatively dense $\ ...
Tópico(s): Advanced Topology and Set Theory
2001 - Electronic Journal of Combinatorics | The Electronic Journal of Combinatorics
... and Optimization) By SVANTE JANSON, TOMASZ ŁUCZAK and ANDRZEJ RUCIŃSKI: 333 pp., US$48.50, ISBN 0-471- ...
Tópico(s): Algorithms and Data Compression
2001 - Wiley | Bulletin of the London Mathematical Society
Andrzej Dudek, Alan Frieze, Andrzej Ruciński, Matas Šileikis,
We establish an inclusion relation between two uniform models of random $k$-graphs (for constant $k \ge 2$) on $n$ labeled vertices: $\mathbb G^{(k)}(n,m)$, the random $k$-graph with $m$ edges, and $\mathbb R^{(k)}(n,d)$, the random $d$-regular $k$-graph. We show that if $n\log n\ll m\ll n^k$ we can choose $d = d(n) \sim {km}/n$ and couple $\mathbb G^{(k)}(n,m)$ and $\mathbb R^{(k)}(n,d)$ so that the latter contains the former with probability tending to one as $n\to\infty$. This extends an earlier result of Kim and Vu ...
Tópico(s): Topological and Geometric Data Analysis
2016 - Elsevier BV | Journal of Combinatorial Theory Series B