ﻻ يوجد ملخص باللغة العربية
Using standard methods (due to Janson, Stein-Chen, and Talagrand) from probabilistic combinatorics, we explore the following general theme: As one progresses from each member of a family of objects ${cal A}$ being covered by at most one object in a random collection ${cal C}$, to being covered at most $lambda$ times, to being covered at least once, to being covered at least $lambda$ times, a hierarchy of thresholds emerge. We will then see how such results vary according to the context, and level of dependence introduced. Examples will be from extremal set theory, combinatorics, and additive number theory.
A well-known conjecture of Tuza asserts that if a graph has at most $t$ pairwise edge-disjoint triangles, then it can be made triangle-free by removing at most $2t$ edges. If true, the factor 2 would be best possible. In the directed setting, also as
We study several problems on geometric packing and covering with movement. Given a family $mathcal{I}$ of $n$ intervals of $kappa$ distinct lengths, and another interval $B$, can we pack the intervals in $mathcal{I}$ inside $B$ (respectively, cover $
Celebrated theorems of Roth and of Matouv{s}ek and Spencer together show that the discrepancy of arithmetic progressions in the first $n$ positive integers is $Theta(n^{1/4})$. We study the analogous problem in the $mathbb{Z}_n$ setting. We asymptoti
In this paper, we investigate the anti-Ramsey (more precisely, anti-van der Waerden) properties of arithmetic progressions. For positive integers $n$ and $k$, the expression $aw([n],k)$ denotes the smallest number of colors with which the integers ${
This paper gives poly-logarithmic-round, distributed D-approximation algorithms for covering problems with submodular cost and monotone covering constraints (Submodular-cost Covering). The approximation ratio D is the maximum number of variables in a