On the radius and the attachment number of tetravalent half-arc-transitive graphs

In this paper, we study the relationship between the radius $r$ and the attachment number $a$ of a tetravalent graph admitting a half-arc-transitive group of automorphisms. These two parameters were first introduced in Maru?i? (1998), where among other things it was proved that $a$ always divides $2r$. Intrigued by the empirical data from the census (Poto?nik et al., 2015) of all such graphs of order up to 1000 we pose the question of whether all examples for which $a$ does not divide $r$ are arc-transitive. We prove that the answer to this question is positive in the case when $a$ is twice an odd number. In addition, we completely characterise the tetravalent graphs admitting a half-arc-transitive group with $r=3$ and $a=2$, and prove that they arise as non-sectional split $2$-fold covers of line graphs of $2$-arc-transitive cubic graphs.     

A family of surfaces with and Albanese map of degree 3

We study a family of surfaces of general type with and , originally constructed by Cancian and Frapporti by using the Computer Algebra System MAGMA . We provide an alternative, computer‐free construction of these surfaces, that allows us to describe their Albanese map and their moduli space.     

Brieskorn manifolds as contact branched covers of spheres

We show that Brieskorn manifolds with their standard contact structures are contact branched coverings of spheres. This covering maps a contact open book decomposition of the Brieskorn manifold onto a Milnor open book of the sphere.      

A derandomization using min-wise independent permutations

Min-wise independence is a recently introduced notion of limited independence, similar in spirit to pairwise independence. The latter has proven essential for the derandomization of many algorithms. Here we show that approximate min-wise independence allows similar uses, by presenting a derandomization of the RNC algorithm for approximate set cover due to S. Rajagopalan and V. Vazirani. We also discuss how to derandomize their set multi-cover and multi-set multi-cover algorithms in restricted cases. The multi-cover case leads us to discuss the concept of k-minima-wise independence, a natural counterpart to k-wise independence.     

Graphs with equal eternal vertex cover and eternal domination numbers

Mobile guards on the vertices of a graph are used to defend it against an infinite sequence of attacks on either its vertices or its edges. If attacks occur at vertices, this is known at the eternal domination problem. If attacks occur at edges, this is known as the eternal vertex cover problem. We focus on the model in which all guards can move to neighboring vertices in response to an attack. Motivated by the question of which graphs have equal eternal vertex cover and eternal domination numbers, a number of results are presented; one of the main results of the paper is that the eternal vertex cover number is greater than the eternal domination number (in the all-guards move model) in all graphs of minimum degree at least two.     

Domination by second countable spaces and Lindelöf Σ-property

Given a space M, a family of sets A of a space X is ordered by M if A={AK:K is a compact subset of M} and K⊂L implies AK⊂AL. We study the class M of spaces which have compact covers ordered by a second countable space. We prove that a space Cp(X) belongs to M if and only if it is a Lindelöf Σ-space. Under MA(ω₁), if X is compact and (X×X)\Δ has a compact cover ordered by a Polish space then X is metrizable; here Δ={(x,x):x∈X} is the diagonal of the space X. Besides, if X is a compact space of countable tightness and X²\Δ belongs to M then X is metrizable in ZFC.We also consider the class M^? of spaces X which have a compact cover F ordered by a second countable space with the additional property that, for every compact set P⊂X there exists F∈F with P⊂F. It is a ZFC result that if X is a compact space and (X×X)\Δ belongs to M^? then X is metrizable. We also establish that, under CH, if X is compact and Cp(X) belongs to M^? then X is countable.     

The most vital nodes with respect to independent set and vertex cover

Given an undirected graph with weights on its vertices, the k most vital nodes independent set (k most vital nodes vertex cover) problem consists of determining a set of k vertices whose removal results in the greatest decrease in the maximum weight of independent sets (minimum weight of vertex covers, respectively). We also consider the complementary problems, minimum node blocker independent set (minimum node blocker vertex cover) that consists of removing a subset of vertices of minimum size such that the maximum weight of independent sets (minimum weight of vertex covers, respectively) in the remaining graph is at most a specified value. We show that these problems are NP-hard on bipartite graphs but polynomial-time solvable on unweighted bipartite graphs. Furthermore, these problems are polynomial also on cographs and graphs of bounded treewidth. Results on the non-existence of ptas are presented, too.     

Buchsbaum Stanley–Reisner Rings and Cohen–Macaulay Covers

First, we give a new criterion for Buchsbaum Stanley–Reisner rings to have linear resolutions. Next, we prove that every (d ? 1)-dimensional complex Δ of initial degree d is contained in the same dimensional Cohen–Macaulay complex whose (d ? 1)th reduced homology is isomorphic to that of Δ. We call such a simplicial complex a Cohen–Macaulay cover of Δ. And we also show that all the intermediate complexes between Δ and its Cohen–Macaulay cover are Buchsbaum provided that Δ is Buchsbaum. As an application, we determine the h-vectors of the 3-dimensional Buchsbaum Stanley–Reisner rings with initial degree 3.     

A Note on a Generalization of the Multiple Cover Formula and the Simple Flop

We prove a closed formula for an excess integral over the moduli space of stable maps from genus one, unmarked curves to the projective space ? ^r of degree d for any positive integers r and d. The result generalizes the multiple cover formula for ?¹. We also show that any simple ? ^r flop preserves the theory of arbitrary-genus Gromov-Witten invariants in exceptional curve classes.