第４回研究会

講演者１： Nhan Bao Ho (La Trobe University)

題目： The Sprague-Grundy function for Star Silver Dollar game

We examine a generalization of the game Silver Dollar that we call Star Silver Dollar played with multiple strips sharing the same square labeled zero. We prove that computing Sprague-Grundy function can be simpli ed to that of a simpler game with at most two tokens in each strip. We analyze the simplest form, called Star Nim, of this generalization in which each strip has exactly one token. We give an algorithm that, for each Sprague-Grundy value g, computes the positions of two-token Star Nim whose Sprague-Grundy values are g. We prove a periodicity of the sequence of these positions.

講演者２： Endre Boros (Rutgers University)

題目： Generating maximal irredundant and minimal redundant subfamilies of a hypergraph

A hypergraph is called irredundant is every hyperedge contains a vertex with degree =1, that is a so called private vertex. A non-irredundant hypergraph is called redundant. The problem of generating all maximal irredundant subfamilies -- MaxIRR (or minimal redundant ones -- MinRED) of a given hypergraph was raised recently by Takeaki Uno (Workshop on Enumeration Algorithms and Structure, Lorentz Center, August, 2015), who also pointed out that MinRED is not easier than monotone dualization. Problem MaxIRR is also strongly related to the problem of generating minimal dominating sets in graphs.

In this talk we present a number of related results. Among others we show that (1) problems MaxIRR and MinRED are both NP-hard, even if the input is restricted to hypergraphs of maximal degree 3; (2) when restricted for hypergraphs of maximum degree 2, then MinRED is trivial, while MaxIRR is polynomially equivalent with monotone dualization; (3) if the input is restricted to hypergraphs with bounded edge sizes, then MinRED is solvable in polynomially time, while MaxIRR can be solved in polynomial incremental time; (4) finally, under a mild technical condition on the input hypergraphs, MaxIRR becomes solvable in quasi-polynomial incremental time.

講演者３： Vladimir Gurvich (Rutgers University)

題目： Metric and ultrametric spaces of resistances

Consider an electrical circuit each edge \(e\) of which is an isotropic conductor with a monomial conductivity function \(y_e^* = y_e^ r/ \mu_e^s\). In this formula, \(y_e\) is the potential difference and \(y_e^∗\) current in \(e\), while \(\mu_e\) is the resistance of \(e\); furthermore, \(r\) and \(s\) are two strictly positive real parameters common for all edges. In particular, the case \(r = s = 1\) corresponds to the standard Ohm law, while \(r = 0.5\) is the standard square law of resistance typical for hydraulics or gas dynamics.

For every two nodes \(a\) and \(b\) of the circuit, the effective resistance \(\mu(a,b)\) is well-defined and for every three nodes \(a\), \(b\), and \(c\) it holds that \(\mu^{s/r}(a,b) ≤ \mu^{s/r}(a,c) + \mu^{s/r}(c,b)\). It obviously implies the standard triangle inequality \(\mu(a,b) \leq \mu(a,c) + \mu(c,b)\) whenever \(s \geq r\). The equality takes place if and only if each path between \(a\) and \(b\) contains \(c\). One gets several examples of metric and ultrametric spaces playing with parameters \(r\) and \(s\); in particular,

(i) the effective Ohm resistance for \(r(t) = s(t) \equiv 1\);

(ii) the length of a shortest path for \(r(t) = s(t) \rightarrow \infty\);

(iii) the inverse width of a bottleneck path for \(r(t) \equiv 1, s(t) \rightarrow \infty\);

(iv) the inverse capacity (maximum flow per unit time) for \(r(t) \rightarrow 0, s(t) \equiv 1\);

between any pair of terminals \(a\) and \(b\), as \(t \rightarrow \infty\). In all four cases the limits \(\mu(a,b) = \lim_{t \rightarrow \infty} \mu(a,b)(t)\) exist for all pairs \(a\), \(b\) and the metric inequality \(\mu(a,b) \leq \mu(a,c) + \mu(c,b)\) holds for all triplets \(a\), \(b\), and \(c\), since \(s(t) \geq r(t)\) for any sufficiently large \(t\). Moreover, a stronger ultrametric inequality \(\mu(a,b) \leq \max(\mu(a,c), \mu(c,b))\) holds for all triplets \(a\), \(b\), and \(c\) in examples (iii) and (iv), since in these two cases \(s(t)/r(t) \rightarrow \infty\), as \(t \rightarrow \infty\).