2016/01/19 by Csilla Bujtás, Bujtás, Csilla, Michael A. Henning +3
Mathematics · #05C65 #05C69 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C65 #msc:05C69
paper · pdf · doi:10.48550/arxiv.1601.04856
23 pagess
arxiv created 2016/01/19 · arxiv updated 2016/01/20
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, Edge-hitter and 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 game transversal number, τ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 τ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 τg(H) ≤ (4)/(11)(\nH+\mH); and if H is a (loopless) graph, then τg(H) ≤ (1)/(3)(\nH + \mH + 1). We prove that if H is a 3-uniform hypergraph, then τg(H) ≤ (5)/(16)(\nH + \mH), and if H is 4-uniform, then τg(H) ≤ (71)/(252)(\nH + \mH).