RECORD
Bounds on the Game Transversal Number in Hypergraphs
Combinatorics · Submitted 19 Jan 2016
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We prove that if $H$ is a $3$-uniform hypergraph, then $\tau_g(H) \le \frac{5}{16}(\nH + \mH)$, and if $H$ is $4$-uniform, then $\tau_g(H) \le \frac{71}{252}(\nH + \mH)$.
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
Let $H = (V,E)$ be a hypergraph with vertex set $V$ and edge set $E$ of order $\nH = |V|$ and size $\mH = |E|$. A transversal in $H$ is a subset of vertices in $H$ that has a nonempty intersection with every edge of $H$. A vertex hits an edge if it belongs to that edge. The transversal game played on $H$ involves of two players, \emph{Edge-hitter} and \emph{Staller}, who take turns choosing a vertex from $H$. Each vertex chosen must hit at least one edge not hit by the vertices previously chosen. The game ends when the set of vertices chosen becomes a transversal in $H$. Edge-hitter wishes to minimize the number of vertices chosen in the game, while Staller wishes to maximize it. The \emph{game transversal number}, $\tau_g(H)$, of $H$ is the number of vertices chosen when Edge-hitter starts the game and both players play optimally. We compare the game transversal number of a hypergraph with its transversal number, and also present an important fact concerning the monotonicity of $\tau_g$, that we call the Transversal Continuation Principle. It is known that if $H$ is a hypergraph with all edges of size at least~$2$, and $H$ is not a $4$-cycle, then $\tau_g(H) \le \frac{4}{11}(\nH+\mH)$; and if $H$ is a (loopless) graph, then $\tau_g(H) \le \frac{1}{3}(\nH + \mH + 1)$. We prove that if $H$ is a $3$-uniform hypergraph, then $\tau_g(H) \le \frac{5}{16}(\nH + \mH)$, and if $H$ is $4$-uniform, then $\tau_g(H) \le \frac{71}{252}(\nH + \mH)$.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Let $H = (V,E)$ be a hypergraph with vertex set $V$ and edge set $E$ of order $\nH = |V|$ and size $\mH = |E|$. | background 1.00 | 0.08 | 0.02 | asserted 0.84 |
| s1 | A transversal in $H$ is a subset of vertices in $H$ that has a nonempty intersection with every edge of $H$. | background 1.00 | 0.05 | 0.02 | asserted 1.00 |
| s2 | A vertex hits an edge if it belongs to that edge. | background 1.00 | 0.05 | 0.01 | asserted 0.99 |
| s3 | The transversal game played on $H$ involves of two players, \emph{Edge-hitter} and \emph{Staller}, who take turns choosing a vertex from $H$. | background 0.87 | 0.12 | 0.02 | asserted 0.99 |
| s4 | Each vertex chosen must hit at least one edge not hit by the vertices previously chosen. | background 0.77 | 0.10 | 0.02 | asserted 1.00 |
| s5 | The game ends when the set of vertices chosen becomes a transversal in $H$. | background 0.78 | 0.10 | 0.02 | asserted 1.00 |
| s6 | Edge-hitter wishes to minimize the number of vertices chosen in the game, while Staller wishes to maximize it. | background 0.91 | 0.08 | 0.03 | asserted 0.99 |
| s7 | The \emph{game transversal number}, $\tau_g(H)$, of $H$ is the number of vertices chosen when Edge-hitter starts the game and both players play optimally. | background 0.92 | 0.20 | 0.06 | asserted 1.00 |
| s8 | We compare the game transversal number of a hypergraph with its transversal number, and also present an important fact concerning the monotonicity of $\tau_g$, that we call the Transversal Continuation Principle. | contribution 1.00 | 0.87 | 0.12 | asserted 0.96 |
| s9 | It is known that if $H$ is a hypergraph with all edges of size at least~$2$, and $H$ is not a $4$-cycle, then $\tau_g(H) \le \frac{4}{11}(\nH+\mH)$; and if $H$ is a (loopless) graph, then $\tau_g(H) \le \frac{1}{3}(\nH + \mH + 1)$. | background 1.00 | 0.05 | 0.08 | asserted 1.00 |
| s10 | We prove that if $H$ is a $3$-uniform hypergraph, then $\tau_g(H) \le \frac{5}{16}(\nH + \mH)$, and if $H$ is $4$-uniform, then $\tau_g(H) \le \frac{71}{252}(\nH + \mH)$. | result 0.94 | 0.95 | 0.81 | 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
Let $H = (V,E)$ be a hypergraph with vertex set $V$ and edge set $E$ of order $\nH = |V|$ and size $\mH = |E|$. A transversal in $H$ is a subset of vertices in $H$ that has a nonempty intersection with every edge of $H$. A vertex hits an edge if it belongs to that edge. The transversal game played on $H$ involves of two players, \emph{Edge-hitter} and \emph{Staller}, who take turns choosing a vertex from $H$. Each vertex chosen must hit at least one edge not hit by the vertices previously chosen. The game ends when the set of vertices chosen becomes a transversal in $H$. Edge-hitter wishes to minimize the number of vertices chosen in the game, while Staller wishes to maximize it. The \emph{game transversal number}, $\tau_g(H)$, of $H$ is the number of vertices chosen when Edge-hitter starts the game and both players play optimally. We compare the game transversal number of a hypergraph with its transversal number, and also present an important fact concerning the monotonicity of $\tau_g$, that we call the Transversal Continuation Principle. It is known that if $H$ is a hypergraph with all edges of size at least~$2$, and $H$ is not a $4$-cycle, then $\tau_g(H) \le \frac{4}{11}(\nH+\mH)$; and if $H$ is a (loopless) graph, then $\tau_g(H) \le \frac{1}{3}(\nH + \mH + 1)$. We prove that if $H$ is a $3$-uniform hypergraph, then $\tau_g(H) \le \frac{5}{16}(\nH + \mH)$, and if $H$ is $4$-uniform, then $\tau_g(H) \le \frac{71}{252}(\nH + \mH)$.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.