V. Gurvich

activity

20082025

most citedOn CIS Circulants

18 citations · 42 across the 38 of their papers we have counts for

collaborators

Showing math.COShow all

31 papers · 1 filter

math.CO2024★ 1 cited

Conformality of Minimal Transversals of Maximal Cliques

Endre Boros, Vladimir Gurvich, Martin Milanič +2

Given a hypergraph $H$ , the dual hypergraph of $H$ is the hypergraph of all minimal transversals of $H$ . A hypergraph is conformal if it is the family of maximal cliques of a graph…

math.CO2023

Computing Remoteness Functions of Moore, Wythoff, and Euclid's games

Endre Boros, Vladimir Gurvich, Kazuhisa Makino +1

We study remoteness function $R$ of impartial games introduced by Smith in 1966. The player who moves from a position $x$ can win if and only if $R (x)$ is odd. Th…

math.CO2023

Conformal Hypergraphs: Duality and Implications for the Upper Clique Transversal Problem

Endre Boros, Vladimir Gurvich, Martin Milanič +1

Given a hypergraph $H$ , the dual hypergraph of $H$ is the hypergraph of all minimal transversals of $H$ . The dual hypergraph is always Sperner, that i…

math.CO2023

More on discrete convexity

Vladimir Gurvich, Mariya Naumova

In several recent papers some concepts of convex analysis were extended to discrete sets. This paper is one more step in this direction. It is well known that a local minimum of a…

math.CO2022

Avoidability beyond paths

Vladimir Gurvich, Matjaž Krnc, Martin Milanič +1

The concept of avoidable paths in graphs was introduced by Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius in 2019 as a common generalization of avoidable vertices and simpli…

math.CO2022★ 1 cited

Lexicographically maximal edges of dual hypergraphs and Nash-solvability of tight game forms

Vladimir Gurvich, Mariya Naumova

Let $A = {A_{1}, \dots, A_{m}}$ and $B = {B_{1}, \dots, B_{n}}$ be a pair of dual multi-hypergraphs on the common ground set $O = {o_{1}, \dots, o_{k}}$ . Note that…

math.CO2021

On Nash-solvability of n-person graphical games under Markov's and a priori realizations

Vladimir Gurvich, Mariya Naumova

We consider graphical $n$ -person games with perfect information that have no Nash equilibria in pure stationary strategies. Solving these games in mixed strategies, we introduce pr…

math.CO2021★ 3 cited

More about Exact Slow $k$ -Nim

Nikolay Chikin, Vladimir Gurvich, Konstantin Knop +2

Given $n$ piles of tokens and a positive integer $k \leq n$ , the game Nim $_{n, = k}^{1}$ of exact slow $k$ -Nim is played as follows. Two players move alternately. In each move, a play…

math.CO2020

Balanced flows for transshipment problems

Vladimir Gurvich

A transshipment problem (G, d, λ) is modeled by a directed graph G = (V, E) with weighted vertices d = (d_v | v \in V) and directed edges λ= (λ_e | e \in E) interpreted as follows:…

math.CO2020

Recognizing distributed approval voting forms and correspondences

Endre Boros, Ondrej Cepek, Vladimir Gurvich +1

Each voter $i \in I$ has $α_{i}$ cards that (s)he distributes among the candidates $a \in A$ as a measure of approval. One (or several) candidate(s) who received the maximum number o…

math.CO2020★ 1 cited

Metric and ultrametric inequalities for resistances in directed graphs

Vladimir Gurvich

Consider an electrical circuit $G$ each directed edge $e$ of which is a semiconductor with a monomial conductance function $y_{e}^{*} = f_{e} (y_{e}) = y_{e}^{s} / μ_{e}^{r}$ if $y_{e} \geq 0$ and $y…

math.CO2020

On the degree sequences of dual graphs on surfaces

Endre Boros, Vladimir Gurvich, Martin Milanič +1

Given two graphs $G$ and $G^{*}$ with a one-to-one correspondence between their edges, when do $G$ and $G^{*}$ form a pair of dual graphs realizing the vertices and countries of a map…

math.CO2020

Shifting paths to avoidable ones

Vladimir Gurvich, Matjaž Krnc, Martin Milanič +1

An extension of an induced path $P$ in a graph $G$ is an induced path $P^{'}$ such that deleting the endpoints of $P^{'}$ results in $P$ . An induced path in a graph is said to be avoidab…

math.CO2019★ 1 cited

Avoidable Vertices and Edges in Graphs

Jesse Beisegel, Maria Chudnovsky, Vladimir Gurvich +2

A vertex in a graph is simplicial if its neighborhood forms a clique. We consider three generalizations of the concept of simplicial vertices: avoidable vertices (also known as \te…

math.CO2019

On the Sprague-Grundy function of compound games

Endre Boros, Vladimir Gurvich, Levi Kitrossky +1

The classical game of {\sc Nim} can be naturally extended and played on an arbitrary hypergraph $\cH \subseteq 2^V \setminus \{\emptyset\}$ whose vertices $V = {1, \dots, n}$ co…

math.CO2018

Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs

Endre Boros, Vladimir Gurvich, Martin Milanič

A hypergraph is said to be $1$ -Sperner if for every two hyperedges the smallest of their two set differences is of size one. We present several applications of $1$ -Sperner hypergra…

math.CO2018

Sprague-Grundy Function of Matroids and Related Hypergraphs

Endre Boros, Vladimir Gurvich, Nhan Bao Ho +2

We consider a generalization of the classical game of $N I M$ called hypergraph $N I M$ . Given a hypergraph $\cH$ on the ground set $V = {1, \dots, n}$ of $n$ piles of stones, two p…

math.CO2018

Sprague-Grundy Function of Symmetric Hypergraphs

Endre Boros, Vladimir Gurvich, Nhan Bao Ho +2

We consider a generalization of the classical game of $N I M$ called hypergraph $N I M$ . Given a hypergraph $\cH$ on the ground set $V = {1, \dots, n}$ of $n$ piles of stones, two p…

math.CO2017

Monotone bargaining is Nash-solvable

Vladimir Gurvich, Gleb Koshevoy

Given two finite ordered sets $A = {a_{1}, \dots, a_{m}}$ and $B = {b_{1}, \dots, b_{n}}$ , introduce the set of $mn$ outcomes of the game $O = \{(a, b) \mid a \in A, b \in B\} = \{(…

math.CO2017★ 1 cited

Generalizing Gale's theorem on backward induction and domination of strategies

Vladimir Gurvich

In 1953 Gale noticed that for every n-person game in extensive form with perfect information modeled by a rooted treesome special Nash equilibrium in pure strategies can be found b…

math.CO2017

Separable discrete functions: recognition and sufficient conditions

Endre Boros, Ondrej Cepek, Vladimir Gurvich

A discrete function of $n$ variables is a mapping $g : X_{1} \times \dots \times X_{n} \to A$ , where $X_{1}, \dots, X_{n}$ , and $A$ are arbitrary finite sets. Function $g$ is cal…

math.CO2017

Backward induction in presence of cycles

Vladimir Gurvich

For the classical backward induction algorithm, the input is an arbitrary $n$ -person positional game with perfect information modeled by a finite acyclic directed graph (digraph) a…

math.CO2017★ 6 cited

Tetris Hypergraphs and Combinations of Impartial Games

Endre Boros, Vladimir Gurvich, Nhan Bao Ho +2

The Sprague-Grundy (SG) theory reduces the sum of impartial games to the classical game of $N I M$ . We generalize the concept of sum and introduce $\cH$-combinations of impartial gam…

math.CO2015

Decomposing 1-Sperner hypergraphs

Endre Boros, Vladimir Gurvich, Martin Milanič

A hypergraph is Sperner if no hyperedge contains another one. A Sperner hypergraph is equilizable (resp., threshold) if the characteristic vectors of its hyperedges are the (minima…

Conformality of Minimal Transversals of Maximal Cliques

Computing Remoteness Functions of Moore, Wythoff, and Euclid's games

Conformal Hypergraphs: Duality and Implications for the Upper Clique Transversal Problem

More on discrete convexity

Avoidability beyond paths

Lexicographically maximal edges of dual hypergraphs and Nash-solvability of tight game forms

On Nash-solvability of n-person graphical games under Markov's and a priori realizations

More about Exact Slow k-Nim

Balanced flows for transshipment problems

Recognizing distributed approval voting forms and correspondences

Metric and ultrametric inequalities for resistances in directed graphs

On the degree sequences of dual graphs on surfaces

Shifting paths to avoidable ones

Avoidable Vertices and Edges in Graphs

On the Sprague-Grundy function of compound games

Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs

Sprague-Grundy Function of Matroids and Related Hypergraphs

Sprague-Grundy Function of Symmetric Hypergraphs

Monotone bargaining is Nash-solvable

Generalizing Gale's theorem on backward induction and domination of strategies

Separable discrete functions: recognition and sufficient conditions

Backward induction in presence of cycles

Tetris Hypergraphs and Combinations of Impartial Games

Decomposing 1-Sperner hypergraphs

More about Exact Slow $k$ -Nim