RECORD
Strong $(r,p)$ Cover for Hypergraphs
Discrete Mathematics · Submitted 11 Jul 2015
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We prove that a { \it strong $(r,p)$ cover} of size $x$ can be computed in randomized polynomial time if $d(G)\leq \frac{1}{e}({\frac{r^k}{(p-1)^k \binom{r}{p-1}}})^x-1$.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
We introduce the notion of the { \it strong $(r,p)$ cover} number $\chi^c(G,k,r,p)$ for $k$-uniform hypergraphs $G(V,E)$, where $\chi^c(G,k,r,p)$ denotes the minimum number of $r$-colorings of vertices in $V$ such that each hyperedge in $E$ contains at least $min(p,k)$ vertices of distinct colors in at least one of the $\chi^c(G,k,r,p)$ $r$-colorings. We derive the exact values of $\chi^c(K_n^k,k,r,p)$ for small values of $n$, $k$, $r$ and $p$, where $K_n^k$ denotes the complete $k$-uniform hypergraph of $n$ vertices. We study the variation of $\chi^c(G,k,r,p)$ with respect to changes in $k$, $r$, $p$ and $n$; we show that $\chi^c(G,k,r,p)$ is at least (i) $\chi^c(G,k,r-1,p-1)$, and, (ii) $\chi^c(G',k-1,r,p-1)$, where $G'$ is any $(n-1)$-vertex induced sub-hypergraph of $G$. We establish a general upper bound for $\chi^c(K_n^k,k,r,p)$ for complete $k$-uniform hypergraphs using a divide-and-conquer strategy for arbitrary values of $k$, $r$ and $p$. We also relate $\chi^c(G,k,r,p)$ to the number $|E|$ of hyperedges, and the maximum {\it hyperedge degree (dependency)} $d(G)$, as follows. We show that $\chi^c(G,k,r,p)\leq x$ for integer $x>0$, if $|E|\leq \frac{1}{2}({\frac{r^k}{(t-1)^k \binom{r}{t-1}}})^x $, for any $k$-uniform hypergraph. We prove that a { \it strong $(r,p)$ cover} of size $x$ can be computed in randomized polynomial time if $d(G)\leq \frac{1}{e}({\frac{r^k}{(p-1)^k \binom{r}{p-1}}})^x-1$.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We introduce the notion of the { \it strong $(r,p)$ cover} number $\chi^c(G,k,r,p)$ for $k$-uniform hypergraphs $G(V,E)$, where $\chi^c(G,k,r,p)$ denotes the minimum number of $r$-colorings of vertices in $V$ such that each hyperedge in $E$ contains at least $min(p,k)$ vertices of distinct colors in at least one of the $\chi^c(G,k,r,p)$ $r$-colorings. | contribution 0.99 | 0.86 | 0.11 | asserted 0.97 |
| s1 | We derive the exact values of $\chi^c(K_n^k,k,r,p)$ for small values of $n$, $k$, $r$ and $p$, where $K_n^k$ denotes the complete $k$-uniform hypergraph of $n$ vertices. | result 0.84 | 0.97 | 0.11 | asserted 1.00 |
| s2 | We study the variation of $\chi^c(G,k,r,p)$ with respect to changes in $k$, $r$, $p$ and $n$; we show that $\chi^c(G,k,r,p)$ is at least (i) $\chi^c(G,k,r-1,p-1)$, and, (ii) $\chi^c(G',k-1,r,p-1)$, where $G'$ is any $(n-1)$-vertex induced sub-hypergraph of $G$. | result 0.85 | 0.95 | 0.11 | asserted 1.00 |
| s3 | We establish a general upper bound for $\chi^c(K_n^k,k,r,p)$ for complete $k$-uniform hypergraphs using a divide-and-conquer strategy for arbitrary values of $k$, $r$ and $p$. | contribution 0.50 | 0.96 | 0.19 | asserted 1.00 |
| s4 | We also relate $\chi^c(G,k,r,p)$ to the number $|E|$ of hyperedges, and the maximum {\it hyperedge degree (dependency)} $d(G)$, as follows. | contribution 0.93 | 0.81 | 0.04 | unclear 0.60 |
| s5 | We show that $\chi^c(G,k,r,p)\leq x$ for integer $x>0$, if $|E|\leq \frac{1}{2}({\frac{r^k}{(t-1)^k \binom{r}{t-1}}})^x $, for any $k$-uniform hypergraph. | result 0.99 | 0.92 | 0.15 | asserted 1.00 |
| s6 | We prove that a { \it strong $(r,p)$ cover} of size $x$ can be computed in randomized polynomial time if $d(G)\leq \frac{1}{e}({\frac{r^k}{(p-1)^k \binom{r}{p-1}}})^x-1$. | result 0.84 | 0.93 | 0.18 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
We introduce the notion of the { \it strong $(r,p)$ cover} number $\chi^c(G,k,r,p)$ for $k$-uniform hypergraphs $G(V,E)$, where $\chi^c(G,k,r,p)$ denotes the minimum number of $r$-colorings of vertices in $V$ such that each hyperedge in $E$ contains at least $min(p,k)$ vertices of distinct colors in at least one of the $\chi^c(G,k,r,p)$ $r$-colorings. We derive the exact values of $\chi^c(K_n^k,k,r,p)$ for small values of $n$, $k$, $r$ and $p$, where $K_n^k$ denotes the complete $k$-uniform hypergraph of $n$ vertices. We study the variation of $\chi^c(G,k,r,p)$ with respect to changes in $k$, $r$, $p$ and $n$; we show that $\chi^c(G,k,r,p)$ is at least (i) $\chi^c(G,k,r-1,p-1)$, and, (ii) $\chi^c(G',k-1,r,p-1)$, where $G'$ is any $(n-1)$-vertex induced sub-hypergraph of $G$. We establish a general upper bound for $\chi^c(K_n^k,k,r,p)$ for complete $k$-uniform hypergraphs using a divide-and-conquer strategy for arbitrary values of $k$, $r$ and $p$. We also relate $\chi^c(G,k,r,p)$ to the number $|E|$ of hyperedges, and the maximum {\it hyperedge degree (dependency)} $d(G)$, as follows. We show that $\chi^c(G,k,r,p)\leq x$ for integer $x>0$, if $|E|\leq \frac{1}{2}({\frac{r^k}{(t-1)^k \binom{r}{t-1}}})^x $, for any $k$-uniform hypergraph. We prove that a { \it strong $(r,p)$ cover} of size $x$ can be computed in randomized polynomial time if $d(G)\leq \frac{1}{e}({\frac{r^k}{(p-1)^k \binom{r}{p-1}}})^x-1$.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites · 8 sentences without a confident label
Compares with 1 paper
-
For any arbitrary $n$ vertex $k$-uniform hypergraph $G$, $χ^c(G,k,3,3) ≤χ^c(K_n^k,k,3,3) ≤ 1/3(n/k-1)^2.71 + log_3/2n/k-1-1, if $k$ is odd, 1/3(n/k-2)^2.71 + log_3/2n/k-2-1 , if $k$ is even.$ Observe that there is a large variation in upper bounds of $χ^c(K_n^k,k,3,3)$ and $χ^c_3(K_n^k)$ [ref] .
Bicoloring covers for graphs and hypergraphs · General upper bounds · 0.82
Cites as background 2 papers
-
[ref] A set of bicolorings $C={X_1,...,X_t}$ is called a bicoloring cover for a $k$-uniform hypergraph $G(V,E)$ if every hyperedge $e ∈E$ is properly colored in at least one bicoloring $X_i$, $X_i ∈C$.
Bicoloring covers for graphs and hypergraphs · Introduction · 0.93
-
[ref] proposed a notion of semi-strong colorings of hypergraphs.
Semi-Strong Coloring of Intersecting Hypergraphs · Introduction · 0.95
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.