Source author record

Alexander V. Karzanov

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.RT Discrete Mathematics math.OC math.QA

Catalog footprint

Research overview

18works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

A poset representation for stable contracts in a two-sided market generated by integer choice functions

Generalizing a variety of earlier problems on stable contracts in two-sided markets, Alkan and Gale introduced in 2003 a general stability model on a bipartite graph $G=(V,E)$ in which the vertices are interpreted as ``agents'', and the edges as possible ``contract'' between pairs of ``agents''. The edges are endowed with nonnegative capacities $b$ giving upper bounds on ``contract intensities'', and the preferencies of each ``agent'' $v\in V$ depend on a \emph{choice function} (CFs) that acts on the set of ``contracts'' involving $v$ , obeying three well motivated axioms of \it{consistence}, \it{substitutability} and \it{cardinal monotonicity}. In their model, the capacities and choice functions can take reals or discrete values and, extending well-known earlier results on particular cases, they proved that systems of \it{stable} contracts always exist and, moreover, their set $\cal S$ constitutes a distributive lattice under a natural comparison relation $\prec$ . In this paper, we study Alkan--Gale's model when all capacities and choice functions take integer values. We characterize the set of rotations -- augmenting cycles linking neighboring stable assignments in the lattice $(\cal S,\prec)$ , explain how to construct the rotations efficiently, and devise a weighted poset in which the lattice of closed functions is isomorphic to $(\cal S,\prec)$ , thus obtaining an explicit representation for the latter. We show that in general the size of the poset is at most $b^{\rm max}|E|$ , where $b^{\rm max}$ is the maximal capacity, and the poset can be constructed in pseudo polynomial time. Then we explain that by imposing an additional condition on CFs, the size of the poset becomes polynomial in $|V|$ , and the total time reduces to a polynomial in $|V|,\log b^{\rm max}$ .

preprint2023arXiv

On the set of stable matchings of a bipartite graph

The topic of stable matchings (marriages) in a bipartite graph has become widely popular, starting with the appearance of the classical work by Gale and Shapley. We give a detailed survey on selected known results in this field that demonstrate structural, polyhedral and algorithmic properties of such matchings and their sets, providing our description with relatively short proofs.

preprint2022arXiv

Flips in symmetric separated set-systems

For a positive integer $n$ , a collection $S$ of subsets of $[n]=\{1,\ldots,n\}$ is called symmetric if $X\in S$ implies $X^\ast\in S$ , where $X^\ast:=\{i\in [n]\colon n-i+1\notin X\}$ (the involution $\ast$ was introduced by Karpman). Leclerc and Zelevinsky showed that the set of maximal strongly (resp. weakly) separated collections in $2^{[n]}$ is connected via flips, or mutations, ``in the presence of six (resp. four) witnesses''. We give a symmetric analog of those results, by showing that each maximal symmetric strongly (weakly) separated collection in $2^{[n]}$ can be obtained from any other one by a series of special symmetric local transformations, so-called symmetric flips. Also we establish the connectedness via symmetric flips for the class of maximal symmetric $r$ -separated collections in $2^{[n]}$ when $n,r$ are even (where sets $A,B\subseteq [n]$ are called $r$ -separated if there are no elements $i_0<i_1< \cdots <i_{r+1}$ in $[n]$ which alternate in $A\setminus B$ and $B\setminus A$ ). This is related to a symmetric version of higher Bruhat orders. These results are obtained as consequences of our study of related geometric objects: symmetric rhombus and combined tilings and symmetric cubillages.

preprint2022arXiv

Higher Bruhat orders of types B and C

We propose versions of higher Bruhat orders for types $B$ and $C$ . This is based on a theory of higher Bruhat orders of type~A and their geometric interpretations (due to Manin--Shekhtman, Voevodskii--Kapranov, and Ziegler), and on our study of the so-called symmetric cubillages of cyclic zonotopes.

preprint2016arXiv

Combined tilings and separated set-systems

In 1998, Leclerc and Zelevinsky introduced the notion of weakly separated collections of subsets of the ordered $n$ -element set $[n]$ (using this notion to give a combinatorial characterization for quasi-commuting minors of a quantum matrix). They conjectured the purity of certain natural domains $D\subseteq 2^{[n]}$ (in particular, of the hypercube $2^{[n]}$ itself, and the hyper-simplex $\{X\subseteq[n]\colon |X|=m\}$ for $m$ fixed), where $D$ is called pure if all maximal weakly separated collections in $D$ have the same cardinality. These conjectures have been answered affirmatively. In this paper, generalizing those earlier results, we reveal wider classes of pure domains in $2^{[n]}$ . This is obtained as a consequence of our study of a novel geometric--combinatorial model for weakly separated set-systems, so-called \emph{combined (polygonal) tilings} on a zonogon, which yields a new insight in the area.

preprint2016arXiv

Two statements on path systems related to quantum minors

In ArXiv:1604.00338[math.QA] we gave a complete combinatorial characterization of homogeneous quadratic identities for minors of quantum matrices. It was obtained as a consequence of results on minors of matrices of a special sort, the so-called path matrices $Path_G$ generated by paths in special planar directed graphs $G$ . In this paper we prove two assertions that were stated but left unproved in ArXiv:1604.00338[math.QA]. The first one says that any minor of $Path_G$ is determined by a system of disjoint paths, called a flow, in $G$ (generalizing a similar result of Lindström's type for the path matrices of Cauchon graphs by Casteels). The second, more sophisticated, assertion concerns certain transformations of pairs of flows in $G$ .

preprint2014arXiv

A combinatorial algorithm for the planar multiflow problem with demands located on three holes

We consider an undirected multi(commodity)flow demand problem in which a supply graph is planar, each source-sink pair is located on one of three specified faces of the graph, and the capacities and demands are integer-valued and Eulerian. It is known that such a problem has a solution if the cut and (2,3)-metric conditions hold, and that the solvability implies the existence of an integer solution. We develop a purely combinatorial strongly polynomial solution algorithm.

preprint2012arXiv

Assembling crystals of type A

Regular $A_n$ -crystals are certain edge-colored directed graphs which are related to representations of the quantized universal enveloping algebra $U_q(\mathfrak{sl}_{n+1})$ . For such a crystal $K$ with colors $1,2,...,n$ , we consider its maximal connected subcrystals with colors $1,...,n-1$ and with colors $2,...,n$ and characterize the interlacing structure for all pairs of these subcrystals. This is used to give a recursive description of the combinatorial structure of $K$ and develop an efficient procedure of assembling $K$ .

preprint2012arXiv

On Weighted Multicommodity Flows in Directed Networks

Let $G = (VG, AG)$ be a directed graph with a set $S \subseteq VG$ of terminals and nonnegative integer arc capacities $c$ . A feasible multiflow is a nonnegative real function $F(P)$ of "flows" on paths $P$ connecting distinct terminals such that the sum of flows through each arc $a$ does not exceed $c(a)$ . Given $μ\colon S \times S \to \R_+$ , the \emph{ $μ$ -value} of $F$ is $\sum_P F(P) μ(s_P, t_P)$ , where $s_P$ and $t_P$ are the start and end vertices of a path $P$ , respectively. Using a sophisticated topological approach, Hirai and Koichi showed that the maximum $μ$ -value multiflow problem has an integer optimal solution when $μ$ is the distance generated by subtrees of a weighted directed tree and $(G,S,c)$ satisfies certain Eulerian conditions. We give a combinatorial proof of that result and devise a strongly polynomial combinatorial algorithm.

preprint2012arXiv

Planar flows and quadratic relations over semirings

Adapting Lindström's well-known construction, we consider a wide class of functions which are generated by flows in a planar acyclic directed graph whose vertices (or edges) take weights in an arbitrary commutative semiring. We give a combinatorial description for the set of "universal" quadratic relations valid for such functions. Their specializations to particular semirings involve plenty of known quadratic relations for minors of matrices (e.g., Plücker relations) and the tropical counterparts of such relations. Also some applications and related topics are discussed.

preprint2011arXiv

Condorcet domains of tiling type

A Condorcet domain (CD) is a collection of linear orders on a set of candidates satisfying the following property: for any choice of preferences of voters from this collection, a simple majority rule does not yield cycles. We propose a method of constructing "large" CDs by use of rhombus tiling diagrams and explain that this method unifies several constructions of CDs known earlier. Finally, we show that three conjectures on the maximal sizes of those CDs are, in fact, equivalent and provide a counterexample to them.

preprint2011arXiv

On Min-Cost Multiflow Problem in Node-Capacitated Undirected Networks

We consider an undirected graph $G = (VG, EG)$ with a set $T \subseteq VG$ of terminals, and with nonnegative integer capacities $c(v)$ and costs $a(v)$ of nodes $v\in VG$ . A path in $G$ is a \emph{ $T$ -path} if its ends are distinct terminals. By a \emph{multiflow} we mean a function $F$ assigning to each $T$ -path $P$ a nonnegative rational \emph{weight} $F(P)$ , and a multiflow is called \emph{feasible} if the sum of weights of $T$ -paths through each node $v$ does not exceed $c(v)$ . The \emph{value} of $F$ is the sum of weights $F(P)$ , and the \emph{cost} of $F$ is the sum of $F(P)$ times the cost of $P$ w.r.t. $a$ , over all $T$ -paths $P$ . Generalizing known results on edge-capacitated multiflows, we show that the problem of finding a minimum cost multiflow among the feasible multiflows of maximum possible value admits \emph{half-integer} optimal primal and dual solutions. Moreover, we devise a strongly polynomial algorithm for finding such optimal solutions.

preprint2010arXiv

On maximal weakly separated set-systems

For a permutation $ω\in S_n$ , Leclerc and Zelevinsky \cite{LZ} introduced a concept of $ω$ -{\em chamber weakly separated collection} of subsets of $\{1,2,...,n\}$ and conjectured that all inclusion-wise maximal collections of this sort have the same cardinality $\ell(ω)+n+1$ , where $\ell(ω)$ is the length of $ω$ . We answer affirmatively this conjecture and present a generalization and additional results.

preprint2010arXiv

Planar flows and Plücker's type quadratic relations over semirings

It is well known, due to Lindström, that the minors of a (real or complex) matrix can be expressed in terms of weights of flows in a planar directed graph. Another classical fact is that there are plenty of homogeneous quadratic relations involving flag minors, or Plücker coordinates of the corresponding flag manifold. Generalizing and unifying these facts and their tropical counterparts, we consider a wide class of functions on $2^{[n]}$ that are generated by flows in a planar graph and take values in an arbitrary commutative semiring, where $[n]=\{1,2,\ldots,n\}$ . We show that the ``universal'' homogeneous quadratic relations fulfilled by such functions can be described in terms of certain matchings, and as a consequence, give combinatorial necessary and sufficient conditions on the collections of subsets of $[n]$ determining these relations.

preprint2009arXiv

Plücker environments, wiring and tiling diagrams, and weakly separated set-systems

For the ordered set $[n]$ of $n$ elements, we consider the class $\Bscr_n$ of bases $B$ of tropical Plücker functions on $2^{[n]}$ such that $B$ can be obtained by a series of mutations (flips) from the basis formed by the intervals in $[n]$ . We show that these bases are representable by special wiring diagrams and by certain arrangements generalizing rhombus tilings on the $n$ -zonogon. Based on the generalized tiling representation, we then prove that each weakly separated set-system in $2^{[n]}$ having maximum possible size belongs to $\Bscr_n$, thus answering affirmatively a conjecture due to Leclerc and Zelevinsky. We also prove an analogous result for a hyper-simplex $Δ_n^m=\{S\subseteq[n]\colon |S|=m\}$ .

preprint2004arXiv

Integer concave cocirculations and honeycombs

A convex triangular grid is represented by a planar digraph $G$ embedded in the plane so that (a) each bounded face is surrounded by three edges and forms an equilateral triangle, and (b) the union $\Rscr$ of bounded faces is a convex polygon. A real-valued function $h$ on the edges of $G$ is called a concave cocirculation if $h(e)=g(v)-g(u)$ for each edge $e=(u,v)$ , where $g$ is a concave function on $\Rscr$ which is affinely linear within each bounded face of $G$ . Knutson and Tao [J. Amer. Math. Soc. 12 (4) (1999) 1055--1090] proved an integrality theorem for so-called honeycombs, which is equivalent to the assertion that an integer-valued function on the boundary edges of $G$ is extendable to an integer concave cocirculation if it is extendable to a concave cocirculation at all. In this paper we show a sharper property: for any concave cocirculation $h$ in $G$ , there exists an integer concave cocirculation $h'$ satisfying $h'(e)=h(e)$ for each boundary edge $e$ with $h(e)$ integer and for each edge $e$ contained in a bounded face where $h$ takes integer values on all edges. On the other hand, we explain that for a 3-side grid $G$ of size $n$ , the polytope of concave cocirculations with fixed integer values on two sides of $G$ can have a vertex $h$ whose entries are integers on the third side but $h(e)$ has denominator $Ω(n)$ for some interior edge $e$ . Also some algorithmic aspects and related results on honeycombs are discussed.

preprint2004arXiv

Maximum Skew-Symmetric Flows and Matchings

The maximum integer skew-symmetric flow problem (MSFP) generalizes both the maximum flow and maximum matching problems. It was introduced by Tutte in terms of self-conjugate flows in antisymmetrical digraphs. He showed that for these objects there are natural analogs of classical theoretical results on usual network flows, such as the flow decomposition, augmenting path, and max-flow min-cut theorems. We give unified and shorter proofs for those theoretical results. We then extend to MSFP the shortest augmenting path method of Edmonds and Karp and the blocking flow method of Dinits, obtaining algorithms with similar time bounds in general case. Moreover, in the cases of unit arc capacities and unit ``node capacities'' the blocking skew-symmetric flow algorithm has time bounds similar to those established in Even and Tarjan (1975) and Karzanov (1973) for Dinits' algorithm. In particular, this implies an algorithm for finding a maximum matching in a nonbipartite graph in $O(\sqrt{n}m)$ time, which matches the time bound for the algorithm of Micali and Vazirani. Finally, extending a clique compression technique of Feder and Motwani to particular skew-symmetric graphs, we speed up the implied maximum matching algorithm to run in $O(\sqrt{n}m\log(n^2/m)/\log{n})$ time, improving the best known bound for dense nonbipartite graphs. Also other theoretical and algorithmic results on skew-symmetric flows and their applications are presented.

preprint2003arXiv

Concave cocirculations in a triangular grid

Let $G=(V(G),E(G))$ be a planar digraph embedded in the plane in which all inner faces are equilateral triangles (with three edges in each), and let the union $\Rscr$ of these faces forms a convex polygon. The question is: given a function $σ$ on the boundary edges of $G$ , does there exist a concave function $f$ on $\Rscr$ which is affinely linear within each bounded face and satisfies $f(v)-f(u)=σ(e)$ for each boundary edge $e=(u,v)$ ? The functions $σ$ admitting such an $f$ form a polyhedral cone $C$ , and when the region $\Rscr$ is a triangle, $C$ turns out to be exactly the cone of boundary data of honeycombs. Studing honeycombs in connection with a problem on spectra of triples of zero-sum Hermitian matrices, Knutson, Tao, and Woodward \cite{KTW} showed that $C$ is described by linear inequalities of Horn's type with respect to so-called {\em puzzles}, along with obvious linear constraints. The purpose of this paper is to give an alternative proof of that result, working in terms of discrete concave finctions, rather than honeycombs, and using only linear programming and combinatorial tools. Moreover, we extend the result to an arbitrary convex polygon $\Rscr$.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Alexander V. Karzanov

Research overview

Is this your work?

18 publications

A poset representation for stable contracts in a two-sided market generated by integer choice functions

On the set of stable matchings of a bipartite graph

Flips in symmetric separated set-systems

Higher Bruhat orders of types B and C

Combined tilings and separated set-systems

Two statements on path systems related to quantum minors

A combinatorial algorithm for the planar multiflow problem with demands located on three holes

Assembling crystals of type A

On Weighted Multicommodity Flows in Directed Networks

Planar flows and quadratic relations over semirings

Condorcet domains of tiling type

On Min-Cost Multiflow Problem in Node-Capacitated Undirected Networks

On maximal weakly separated set-systems

Planar flows and Plücker's type quadratic relations over semirings

Plücker environments, wiring and tiling diagrams, and weakly separated set-systems

Integer concave cocirculations and honeycombs

Maximum Skew-Symmetric Flows and Matchings

Concave cocirculations in a triangular grid

See the researcher in context

Building this map preview