Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThreshold Progressions in a Variety of Covering and Packing Contexts
147
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 asked by Tuza, the analogous statement has recently been proven, however, the factor 2 is not optimal. In this paper, we show that if an $n$-vertex directed graph has at most $t$ pairwise arc-disjoint directed triangles, then there exists a set of at most $1.8t+o(n^2)$ arcs that meets all directed triangles. We complement our result by presenting two constructions of large directed graphs with $tinOmega(n^2)$ whose smallest such set has $1.5t-o(n^2)$ arcs.
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 $B$ by the intervals in $mathcal{I}$) by moving $tau$ intervals and keeping the other $sigma = n - tau$ intervals unmoved? We show that both packing and covering are W[1]-hard with any one of $kappa$, $tau$, and $sigma$ as single parameter, but are FPT with combined parameters $kappa$ and $tau$. We also obtain improved polynomial-time algorithms for packing and covering, including an $O(nlog^2 n)$ time algorithm for covering, when all intervals in $mathcal{I}$ have the same length.
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 asymptotically determine the logarithm of the discrepancy of arithmetic progressions in $mathbb{Z}_n$ for all positive integer $n$. We further determine up to a constant factor the discrepancy of arithmetic progressions in $mathbb{Z}_n$ for many $n$. For example, if $n=p^k$ is a prime power, then the discrepancy of arithmetic progressions in $mathbb{Z}_n$ is $Theta(n^{1/3+r_k/(6k)})$, where $r_k in {0,1,2}$ is the remainder when $k$ is divided by $3$. This solves a problem of Hebbinghaus and Srivastav.
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 ${1,ldots,n}$ can be colored and still guarantee there is a rainbow arithmetic progression of length $k$. We establish that $aw([n],3)=Theta(log n)$ and $aw([n],k)=n^{1-o(1)}$ for $kgeq 4$. For positive integers $n$ and $k$, the expression $aw(Z_n,k)$ denotes the smallest number of colors with which elements of the cyclic group of order $n$ can be colored and still guarantee there is a rainbow arithmetic progression of length $k$. In this setting, arithmetic progressions can wrap around, and $aw(Z_n,3)$ behaves quite differently from $aw([n],3)$, depending on the divisibility of $n$. As shown in [Jungic et al., textit{Combin. Probab. Comput.}, 2003], $aw(Z_{2^m},3) = 3$ for any positive integer $m$. We establish that $aw(Z_n,3)$ can be computed from knowledge of $aw(Z_p,3)$ for all of the prime factors $p$ of $n$. However, for $kgeq 4$, the behavior is similar to the previous case, that is, $aw(Z_n,k)=n^{1-o(1)}$.
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 any constraint. Special cases include Covering Mixed Integer Linear Programs (CMIP), and Weighted Vertex Cover (with D=2). Via duality, the paper also gives poly-logarithmic-round, distributed D-approximation algorithms for Fractional Packing linear programs (where D is the maximum number of constraints in which any variable occurs), and for Max Weighted c-Matching in hypergraphs (where D is the maximum size of any of the hyperedges; for graphs D=2). The paper also gives parallel (RNC) 2-approximation algorithms for CMIP with two variables per constraint and Weighted Vertex Cover. The algorithms are randomized. All of the approximation ratios exactly match those of comparable centralized algorithms.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
