Let $𝒢ₙ^{(k)}$ be a family of random independent k-element subsets of [n] = {1,2,...,n} and let $𝓗 (𝒢ₙ^{(k)},ℓ) = 𝓗 ₙ^{(k)}(ℓ)$ denote a family of ℓ-element subsets of [n] such that the event that S belongs to $𝓗 ₙ^{(k)}(ℓ)$ depends only on the edges of $𝒢ₙ^{(k)}$ contained in S. Then, the edges of $𝓗 ₙ^{(k)}(ℓ)$ are 'weakly dependent', say, the events that two given subsets S and T are in $𝓗 ₙ^{(k)}(ℓ)$ are independent for vast majority of pairs S and T. In the paper we present some results on the structure of weakly dependent families of subsets obtained in this way. We also list some questions which, despite the progress which has been made for the last few years, remain to puzzle researchers who work in the area of probabilistic combinatorics.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In his book on unsolved problems in number theory [1] R. K. Guy asks whether for every natural l there exists $n_0 = n_0(l)$ with the following property: for every $n ≥ n_0$ and any n elements $a_1,...,a_n$ of a group such that the product of any two of them is different from the unit element of the group, there exist l of the $a_i$ such that $a_{i_j}a_{i_k} ≠ a_m$ for $1 ≤ j < k ≤ l$ and $1 ≤ m ≤ n$. In this note we answer this question in the affirmative in the first non-trivial case when l=3 and the group is abelian, proving the following result.
5
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In 1968 Erdős and Hajnal introduced shift graphs as graphs whose vertices are the k-element subsets of [n] = {1,...,n} (or of an infinite cardinal κ ) and with two k-sets $A = {a₁,...,a_{k}}$ and $B = {b₁,...,b_{k}}$ joined if $a₁ < a₂ = b₁ < a₃ = b₂ < ⋯ < a_k = b_{k-1} < b_k$. They determined the chromatic number of these graphs. In this paper we extend this definition and study the chromatic number of graphs defined similarly for other types of mutual position with respect to the underlying ordering. As a consequence of our result, we show the existence of a graph with interesting disparity of chromatic behavior of finite and infinite subgraphs. For any cardinal κ and integer l, there exists a graph G with |V(G)| = χ(G) = κ but such that, for any finite subgraph F ⊂ G, $χ(F)≤ log_{(l)}|V(F|$, where $log_{(l)}$ is the l-iterated logarithm. This answers a question raised by Erdős, Hajnal and Shelah.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.