text:
# Critical thermodynamics of three-dimensional chiral model for 𝑁>3

## I Introduction

The critical behavior of three-dimensional frustrated spin models with noncollinear order has been the subject for intensive experimental and theoretical investigations, since they are expected to belong to a new universality class with unusual values of critical exponents . Physically, noncollinear or canted order is a consequence of frustration due to either the special geometry of the lattice or the competition of different kinds of interactions. Examples of the first kind are the three-dimensional stacked triangular antiferromagnets (STA) in which magnetic ions are located at each site of a stacked triangular lattice (e.g. CsMnBr3, VCl2, VBr2). The second case is represented by helimagnets like the rare-earth Ho, Dy, Tb, in which magnetic spirals are formed along certain directions of the lattice.

Although Monte Carlo simulations  and experimental studies  apparently give contradicting results (supporting either a continuous phase transition with new critical exponents or a weak first order one), a quite definite description of the critical behavior has been reached in the fixed dimension $`D=3`$ field-theoretical (FT) approach . In more detail, these and other relevant issues are reviewed in Ref. , where one can find a complete list of references; we mention here only the very recent studies.

Field-theoretical investigations of such systems are based on the O$`(N)\times `$O$`(M)`$ symmetric Landau-Ginzburg-Wilson Hamiltonian

$$=d^Dx\left\{\frac{1}{2}\underset{a}{}\left[(_\mu \varphi _a)^2+r\varphi _a^2\right]+\frac{1}{4!}u_0\left(\underset{a}{}\varphi _a^2\right)^2+\frac{1}{4!}v_0\underset{a,b}{}\left[(\varphi _a\varphi _b)^2\varphi _a^2\varphi _b^2\right]\right\},$$
(1)
where $`\varphi _a`$ ($`1aM`$) are $`M`$ sets of $`N`$-component vectors. Frustrated systems with noncollinear ordering are described by the Hamiltonian (1) with $`M=2`$ and $`v_0>0`$. Negative values of $`v_0`$ correspond to simple ferromagnetic or antiferromagnetic ordering and to magnets with sinusoidal spin structures . The case $`M=3`$ corresponds to frustrated antiferromagnets with nonplanar spin ordering . Moreover, recently the Hamiltonian (1) has received a lot of attentions because it describes also the quantum critical behavior in some Mott insulators .

Fixing $`M=2`$, the physically relevant cases of frustrated XY and Heisenberg models are described by the Hamiltonian (1) with $`N=2`$ and $`N=3`$ respectively. Field-theoretical studies in the framework of $`ϵ=4D`$ , $`1/N`$ , and $`\stackrel{~}{ϵ}=D2`$ expansions as well as in fixed dimensions $`D=2`$  and $`D=3`$  reveal that the existence and the stability properties of the fixed points depend on $`N`$ and on the spatial dimensionality. Within the $`ϵ`$ expansion, for sufficiently large values of $`N`$ the renormalization group (RG) equations possess four fixed points: the Gaussian fixed point ($`v_0=u_0=0`$), the O$`(2N)`$-symmetric ($`v_0=0`$) one and two anisotropic fixed points located in the region $`u_0,v_0>0`$ and usually named chiral and antichiral. The chiral fixed point is the only stable one. There is a critical dimensionality $`N_c`$ where the chiral and antichiral fixed points coalesce and disappear for $`N<N_c`$. In the last case, under the absence of any stable fixed point the system is expected to undergo a weak first-order phase transition, since the associated RG flows run away from the region of stability of the fourth-order form in the free-energy expansion. The three-loop estimate of $`N_c`$ obtained in the framework of the $`ϵ`$ expansion technique is

$$N_c=21.823.4ϵ+7.1ϵ^2+O(ϵ^3),$$
(2)
that, after an appropriate resummation, results in $`N_c>3`$ in three dimensions. This inequality leads to the conclusion that for the physical models with $`N=2,3`$ the three-dimensional chiral transition is first-order, as corroborated also by some other RG studies . To the contrary, both for $`N=2`$ and $`N=3`$ the highest-order six-loop calculations in three dimensions  reveal a strong evidence for a stable chiral fixed point that, however, is not related to its counterpart found earlier within the $`ϵ`$ expansion. Furthermore, in a recent work  we claimed that both in two and three dimensions the experimentally controversial situation may reflect the quite unusual mode of critical behavior of the $`N`$-vector chiral model under the physical values of $`N`$. In particular, it was shown that this critical behavior is governed by a stable fixed point which is a focus, attracting RG trajectories in a spiral-like manner.

For large enough $`N`$ all the field-theoretical methods are expected to be qualitatively and quantitatively correct. In fact, both $`ϵ`$ and $`1/N`$ expansions lead to the same structure of flow diagram and the fixed points location and to identical critical exponents  (see also the comparison between Monte Carlo data and the results of three-loop FT study made in Ref. ). However, no analysis of the three-dimensional six-loop series  for general $`N`$ is still available. For this reason, we calculate here all the fixed points of Hamiltonian (1) for various $`N`$ and analyze the critical behavior characterized by the stable fixed point, computing also the chiral exponents on the base of known RG series ). We show that the focus-driven critical behavior found previously for physical models in Ref.  ends, under increasing $`N`$, at some $`N_{c2}`$. Then a small zone of first order phase transition $`N_{c2}<N<N_{c1}`$ exists. Finally, for $`N>N_{c1}`$ the continuous transition recovers, being governed by a stable node that is generically related to the stable fixed point given by $`ϵ`$ and $`1/N`$ expansions.

The paper is organized as follows. In Sec. II we describe the method of our analysis. Sec. III contains all the results obtained along with their discussion. In Sec. IV we present a summary and concluding remarks.

## II Analysis method

We analyze the fixed dimensional ($`D=3`$) perturbative six-loop series computed for general $`N`$ in Refs.  by the same methods applied for the XY and Heisenberg frustrated models in Refs. . Within the fixed dimension approach  the perturbative series are obtained expanding the quantities of interest in powers of the quartic couplings and renormalizing the theory by introducing a set of zero-momentum conditions for two-point and four-point correlation functions . All perturbative series are expressed in terms of the renormalized couplings $`u`$ and $`v`$, normalized so that at the tree level they are proportional to the bare ones. The fixed points of the theory are given by the common zeros of the $`\beta `$ functions defined as

$$\beta _u(u,v)=m\frac{u}{m}|_{u_0,v_0},\beta _v(u,v)=m\frac{v}{m}|_{u_0,v_0}.$$
(3)
In the case of a continuous transition the coupling $`u,v`$ are driven toward an infrared-stable zero $`u^{},v^{}`$ of the $`\beta `$ functions. The absence of a stable fixed point is usually considered as an indication of a first-order phase transition. The series for the critical exponents (e.g. $`\nu (u,v)`$ and $`\eta (u,v)`$) are obtained considering the anomalous dimensions of two-point functions with the insertion of operator with the right symmetry (see e.g. Refs. ).

We adopt here the symmetric rescaling of the coupling constants

$$u\frac{16\pi }{3}R_{2N}\overline{u},v\frac{16\pi }{3}R_{2N}\overline{v},$$
(4)
with $`R_N=9/(8+N)`$ to obtain, as in two dimensions , finite fixed point coordinates in the limit of infinite dimension of the order parameter ($`N\mathrm{}`$). In the following we denote with $`\overline{\beta }_{\overline{u}}`$ and $`\overline{\beta }_{\overline{v}}`$ the $`\beta `$-functions corresponding to these rescaled couplings.

The obtained RG series are asymptotic and some resummation procedure is needed in order to extract accurate numerical values for the physical quantities. Exploiting the property of Borel summability of $`\varphi ^4`$ theories in two and three dimensions, we resum the divergent asymptotic series by a Borel transformation combined with a method for the analytic extension of the Borel transform. This last procedure can be obtained by a Padé extension or by a conformal mapping  which maps the domain of analyticity of the Borel transform (cut at the instanton singularity) onto a circle (see Refs.  for details).

The conformal mapping method takes advantage of the knowledge of the large order behavior of the perturbative series $`F(\overline{u},z)=_kf_k(z)\overline{u}^k`$

$$f_k(z)k!(a(z))^kk^b\left[1+O(k^1)\right]\mathrm{with}a(z)=1/\overline{u}_b(z),$$
(5)
where $`\overline{u}_b(z)`$ is the singularity of the Borel transform closest to the origin at fixed $`z=\overline{v}/\overline{u}`$, given by

$$\frac{1}{\overline{u}_b(z)}=aR_{2N}\text{ for }0<z<4,$$
(6)
where $`a=\mathrm{0.147\hspace{0.17em}774\hspace{0.17em}22}\mathrm{}`$. Moreover, it is known  that for $`z>2`$ the Borel transform has a singularity on the positive real axis, which, however, is not the closest one for $`z<4`$. Thus, for $`z>2`$ the series is not Borel summable.

For each perturbative series $`R(\overline{u},\overline{v})`$, we obtain the following approximants

$$E(R)_p(\alpha ,b;\overline{u},\overline{v})=\underset{k=0}{\overset{p}{}}B_k(\alpha ,b;\overline{v}/\overline{u})\times _0^{\mathrm{}}𝑑tt^be^t\frac{y(\overline{u}t;\overline{v}/\overline{u})^k}{[1y(\overline{u}t;\overline{v}/\overline{u})]^\alpha },$$
(7)
where

$$y(x;z)=\frac{\sqrt{1x/\overline{u}_b(z)}1}{\sqrt{1x/\overline{u}_b(z)}+1},$$
(8)
and the coefficients $`B_k`$ are determined by the condition that the expansion of $`E(R)_p(\alpha ,b;\overline{u},\overline{v})`$ in powers of $`\overline{u}`$ and $`\overline{v}`$ gives $`R(\overline{u},\overline{v})`$ to order $`p`$.

Within the second resummation procedure, the Borel transform is analytically extended by means of a generalized Padé-Borel-Leroy technique, using the resolvent series trick. Explicitly, once introduced the resolvent series of the perturbative one $`R(\overline{u},\overline{v})`$

$$\stackrel{~}{P}(R)(\overline{u},\overline{v},b,\lambda )=\underset{n}{}\lambda ^n\underset{k=0}{\overset{n}{}}\frac{\stackrel{~}{P}_{k,n}}{(n+b)!}\overline{u}^{nk}\overline{v}^k,$$
(9)
which is a series in powers of $`\lambda `$ with coefficients being uniform polynomials in $`\overline{u},\overline{v}`$, the analytical continuation of the Borel transform is the Padè approximant $`[N/M]`$ in $`\lambda `$ at $`\lambda =1`$. Obviously, the approximant for each perturbative series depends on the chosen Padé approximant and on the parameter $`b`$.

In order to evaluate the fixed point coordinates by the conformal mapping method, we resum the perturbative series for each $`\overline{\beta }`$ function within the whole plane of coupling constants $`(\overline{u},\overline{v})`$. For each $`\overline{\beta }`$ function we choose 18 approximants which were found to be stable, for small $`\overline{u}`$ and $`\overline{v}`$, under variation of the order of RG approximation (number of loops), i. e. $`\alpha =0,2,4`$ and $`b=3,6,9,12,15,18`$. We divide the domain $`0\overline{u}4`$, $`0\overline{v}6`$ in $`40^2`$ rectangles and we mark all the sites in which at least two approximants for $`\overline{\beta }_{\overline{u}}`$ and $`\overline{\beta }_{\overline{v}}`$ vanish. Analogously, with the Padé approximants we take all of them with integer $`b`$ in the range $`b[0,3]`$ and without dangerous poles; in this case the statistics is much less significant due to a large number of defective approximants.

Located the fixed points, the next step is to find the stable one which drives the system to criticality. The stability properties of the fixed points are determined by the eigenvalues $`\omega _1`$, $`\omega _2`$ of the $`\mathrm{\Omega }`$ matrix

$$\mathrm{\Omega }=\left(\begin{array}{cc}\frac{\beta _u(u,v)}{u}& \frac{\beta _u(u,v)}{v}\\ \frac{\beta _v(u,v)}{u}& \frac{\beta _v(u,v)}{v}\end{array}\right).$$
(10)
A stable fixed point must have two eigenvalues with positive real parts, while a fixed point possessing eigenvalues with non-vanishing imaginary parts is called focus.

We calculate $`\omega _1`$ and $`\omega _2`$ at a given fixed point considering the numerical derivatives of each pair of approximants of the two $`\overline{\beta }`$-functions at their common zero (there are 324 possible combinations with the conformal mapping method and 81, minus defective ones, with the Padé approximant technique). To obtain reliable numerical estimates for $`\omega _1`$ and $`\omega _2`$, we limit ourselves by the approximants which yield the fixed point coordinates compatible with their final, properly weighted values.

The critical exponents are finally evaluated at the stable fixed point by means of employing of the approximants which minimize the difference between the estimates given by different perturbative orders (see e.g.  for details).

## III Results

In this section we analyze the six-loop perturbative series of the RG functions for large number of components of the order parameter using the methods explained above. In Fig.1 we report our results for the zeros of the two $`\overline{\beta }`$ functions for $`N=32,\mathrm{\hspace{0.17em}16},\mathrm{\hspace{0.17em}8},\mathrm{\hspace{0.17em}7},\mathrm{\hspace{0.17em}6},\mathrm{\hspace{0.17em}5}`$, and $`4`$, obtained with the conformal mapping technique. It is seen from this figure that two branches of zeros of $`\overline{\beta }_{\overline{u}}`$ exist for all the considered values of $`N`$. These branches become closer to each other with decreasing $`N`$. The zeros of $`\overline{\beta }_{\overline{v}}`$ are represented by a curve which clearly intersects the upper branch of $`\overline{\beta }_{\overline{u}}`$ for $`N5`$ and the lower branch for $`N7`$. In the complement of these regions, i.e. for $`N=6`$ and close vicinity of this value, the presence or the absence of fixed points is less evident from Fig.1. However, looking at the single pair of approximants for two $`\overline{\beta }`$ functions, one can find that for all $`5<N<7`$ the majority of the approximants for $`\overline{\beta }_{\overline{u}}`$ gives rise to two branches of zeros separated in the plane $`(\overline{u},\overline{v})`$.

For each pair of approximants we find that two marginal values of $`N`$, $`N_{c1}`$ and $`N_{c2}`$, exist. For $`N>N_{c1}`$ the chiral and the antichiral fixed points are always present. They are located on the lower branch of $`\overline{\beta }_{\overline{u}}`$ and coalesce for $`N=N_{c1}`$. For $`N_{c2}<N<N_{c1}`$ only the unstable – Gaussian and O$`(2N)`$-symmetric (Heisenberg) – fixed points exist, while for $`NN_{c2}`$ the chiral and the antichiral fixed points appear again, being located, however, on the upper branch of $`\overline{\beta }_{\overline{u}}`$. With the precision of our calculation we can state that $`N_{c1}=6.4(4)`$ and $`N_{c2}=5.7(3)`$.

Let us now discuss the critical behavior in these three domains of $`N`$. For $`NN_{c1}`$ there are four fixed points: chiral, antichiral, Heisenberg and Gaussian. The location (reported in Table I) and the stability analysis (see Table II) of these fixed points reveal that the chiral one is a stable node and governs the critical regime, while the Heisenberg and the Antichiral are unstable with one negative eigenvalue of the $`\mathrm{\Omega }`$ matrix (cf. Table II). The critical exponents that characterize the second order phase transition are reported in Tab. II with the data of the large $`N`$ analysis . The results indicate that there is a reasonable agreement between the two perturbative methods. It implies that this domain of $`N`$ is generically related to those accessible in the framework of the $`1/N`$ and $`ϵ`$ expansions. So, we can conclude that $`N_{c1}`$ is nothing but a marginal value of $`N`$ introduced earlier within various approximations ($`N_{c3}`$ of Refs. , $`n_I(d)`$ of Ref. , $`n^+(m,d)`$ of Ref. , $`N_c`$ of Ref. , and $`N_+`$ of Ref. ).

For $`N_{c2}<N<N_{c1}`$ no stable fixed points exist in the region $`\overline{u}>0,\overline{v}>0`$ and the transition is expected to be first order (e.g. for $`N=6`$ we found, at the $`O(2N)`$-symmetric fixed point, $`\omega _{O(12)}=0.53(2)`$).

For $`N<N_{c2}`$, as seen from Fig. 1, the chiral fixed point lays on the upper branch of zeros of the $`\overline{\beta }_{\overline{u}}`$, so in principle there is no reason to obtain the results related to those of the large $`N`$ approach. In this domain, the transition is continuous and the eigenvalues of the $`\mathrm{\Omega }`$ matrix at the chiral fixed point possess nonvanishing imaginary parts in the majority of the cases. In Table III we report the estimates for $`\omega _1`$ and $`\omega _2`$ and the percentage of complex eigenvalues. Thus the critical behavior is driven by a stable focus. In Table III we report the critical exponents obtained in this article along with the already known values for $`N=2,3`$  in order to make visible all the trends of physical quantities with varying $`N`$. We also find that for almost all the working approximants, the antichiral fixed point is located in the region where the singularity of the Borel transform closest to the origin is on the real positive axis, leaving its existence doubtful. The fact that its position strongly oscillates with varying the approximants indicates that in this domain of $`(\overline{u},\overline{v})`$ plane the analysis is not robust. On the other hand, the presence of the stable focus chiral point does not imply the existence of the antichiral one. The unstable fixed point is not topologically needed on the separatrix dividing the regions of the first-order and second-order phase transitions.

In the Tables I, II, and III we report, along with the results given by the conformal mapping technique commented above, all the estimates obtained with the Padé-Borel resummation method. Using this method, we faced with a lot of defective Padé approximants which in some cases prevent us from finding estimates for physical quantities (e.g. the values of $`\nu `$ for $`N=16`$ and 32), while in other ones turn out to lead to underestimation of the apparent errors. Anyway, the data obtained with the two resummation techniques are found to be substantially equivalent.

In Figs. 2,3 we display two example of the RG flows given by typical working approximants for $`N=8`$ and $`N=4`$ respectively. These flows clearly demonstrate that for $`N=4`$ there is spiral-like approach to the stable fixed point. This is no longer true for $`N=8`$. Obviously, all the RG flows are quantitatively correct only within the regions where the singularity of the Borel transform closest to the origin is on the real negative axis ; in Figs. 2,3 they correspond to unshaded areas. Nevertheless, we report also the flows in other parts of the coupling constant plane to present a complete qualitative picture. The region that is outside the domain of attraction of the stable fixed point corresponds to the domain of the first-order phase transitions. Note, that saying “the domain of the first-order phase transitions” we mean, as usually, the region where the quartic form in free-energy expansion can acquire negative values. In fact, because of the presence of the higher-order terms in this expansion that make the system globally stable at any temperature, the true domains of the first-order transitions may be substantially more narrow than those predicted by the mean-field approximation.

## IV Conclusion

In this work, we have studied the critical thermodynamics of the O$`(N)\times `$O$`(2)`$ spin model for number of components of the order parameter $`N`$ greater than $`3`$ on the base of the six-loop RG series , giving a complete description of the evolution of critical behavior under varying $`N`$. We have found that for $`N>N_{c1}6.4(4)`$ the transition is continuous and governed by a stable chiral fixed point, that is generically related to the stable fixed point found earlier within the $`ϵ`$ expansion and $`1/N`$ expansion analyses. For $`N_{c2}<N<N_{c1}`$ with $`N_{c2}=5.7(3)`$ we have not detected any stable fixed point and the chiral transition is expected to be first order. The focus-like critical behavior, found previously for physical models ($`N=2,3`$) in Ref. , has been confirmed to exist for any $`N<N_{c2}`$. In this region of $`N`$, the character of crossover phenomena may be rather complicated leading to effective exponents which vary in a non-monotonic way. In analogy with dilute Ising systems, where the concentration-dependent critical exponents seem to violate the universality because of crossover effects near criticality , it looks plausible that the results of some simulations  and experiments , which yield negative values for the exponent $`\eta `$, reflect the peculiarities of the preasymptotic regimes.

Being the region $`N>N_{c1}`$ connected with that accessible by the large $`N`$ analysis, we expect that $`N_{c1}`$ coincides with $`N_c`$ usually introduced in $`ϵ`$ and $`1/N`$ expansions. Several estimates for $`N_c`$ exist. To quote the more recent ones, we have $`N_c=5.3(2)`$  and $`N_c3.39`$  from 3-loop $`ϵ`$ expansion, $`N_c5`$ from the exact renormalization group approach , and $`N_c=3.24`$  and $`N_c=5.3`$  from $`1/N`$ expansion. These scattered results clearly indicate that the extrapolation of $`1/N`$ and $`ϵ`$ expansion predictions up to the physical values of $`N`$ and $`ϵ`$ is a quite delicate matter.

To conclude, we believe that working with the highest-order, six-loop RG series and processing them by means of the advanced resummation techniques, we obtain a clear and definite understanding of the critical behavior of $`N`$-vector chiral model for all the integer values of $`N`$, including the physically relevant ones.

## ACKNOWLEDGMENTS

We would like to thank Ettore Vicari and Andrea Pelissetto for many useful discussions. The financial support of the Russian Foundation for Basic Research under Grant No. 01-02-17048 (A.I.S.) and the Ministry of Education of Russian Federation under Grant No. E02-3.2-266 (A.I.S.) is gratefully acknowledged. A.I.S. has benefited from the warm hospitality of Scuola Normale Superiore and Dipartimento di Fisica dell’Università di Pisa, where this research was done.


format: text

text:
# Concave Cocirculations in a Triangular Grid

## 1 Introduction

Let $`\xi _1,\xi _2,\xi _3`$ be three affinely independent vectors in the euclidean plane $`^2`$ whose sum is the zero vector. The triangular lattice generated by $`\xi _1,\xi _2,\xi _3`$ is associated with the infinite planar directed graph $``$ whose vertices are integer combinations of these vectors and whose edges are the ordered pairs $`(u,v)`$ of vertices such that $`vu\{\xi _1,\xi _2,\xi _3\}`$. An edge $`(u,v)`$ is identified with the straight-line segment between $`u,v`$ oriented from $`u`$ to $`v`$.

Consider a convex region $``$ in the plane formed by the union of a nonempty finite set of faces (little triangles) of $``$; it is a polygon with 3 to 6 sides. We refer to the subgraph $`G=(V(G),E(G))`$ of $``$ consisting of the vertices and edges occurring in $``$ as a convex (triangular) grid. The vertices and edges in the boundary $`b(G)`$ of $`G`$ are called outer and their sets are denoted by $`V_0(G)`$ and $`E_0(G)`$, respectively. A real-valued function $`f`$ on the vertices of $`G`$ is called discrete concave (convex) if it is the restriction to $`V(G)`$ of a concave (resp. convex) function on $``$ which is affinely linear within each bounded face of $`G`$. In this paper we prefer to deal with discrete concave functions; the corresponding results for discrete convex functions follow by symmetry.

We are interested in the functions on the set of outer vertices that can be extended to discrete concave functions on all vertices of $`G`$. Instead, one can consider the corresponding functions on edges. More precisely, a function $`h:E(G)`$ is said to be a cocirculation if it can be expressed via some function $`f:V(G)`$ as $`h(e):=f(v)f(u)`$ for each edge $`e=(u,v)`$. Such an $`h`$ determines $`f`$ up to a constant, and we refer to $`h`$ as a concave cocirculation if $`f`$ is discrete concave. We consider the problem:

1. given a function $`\sigma :E_0(G)`$, decide whether $`\sigma `$ is extendable to a concave cocirculation in $`G`$.

Let $`(G)`$ be the set of $`\sigma `$’s admitting such an extension. Obvious necessary (but far to be sufficient) conditions on $`\sigma `$ to belong to $`(G)`$ are that the sum of values of $`\sigma `$, taken with signs $`+`$ or $``$ depending on the direction of an edge in the boundary circuit, amounts to zero and that $`\sigma `$ is monotone nonincreasing along each side-path of $`b(G)`$.

When the region $``$ spanned by $`G`$ is a triangle, $`G`$ is called a 3-side (triangular) grid. Then the boundary of $`G`$ is the concatenation of three paths $`B_1,B_2,B_3`$ forming the sides of $``$, where the edges of $`B_i`$ are parallel to $`\xi _i`$. We say that $`G`$ is of size $`n`$ if $`|B_i|=n`$, where $`|P|`$ denotes the number of edges of a path $`P`$. In this special case $`(G)`$ coincides with the so-called Berenstein-Zelevinsky cone, which also arises in other interesting models. More precisely, relying on some earlier results, Knutson and Tao  showed that for a triple of monotone nonincreasing $`n`$-tuples $`(\lambda ,\mu ,\nu )(^n)^3`$, the following properties are equivalent:

* $`\lambda ,\mu ,\nu `$ are the spectra of three $`n\times n`$ Hermitian matrices whose sum is the zero matrix;
* there exists a honeycomb of size $`n`$ in which the three tuples of semiinfinite edges have the constant coordinates $`\lambda ,\mu ,\nu `$;
* let $`G`$ be the 3-side gride of size $`n`$ and let the function $`\sigma `$ on $`E_0(G)`$ take the value $`\lambda _j`$ (resp. $`\mu _j,\nu _j`$) on $`j`$th edge of the path $`B_1`$ (resp. $`B_2,B_3`$); then $`\sigma (G)`$.

For a survey on those earlier results, see , and for the definition of honeycomb, see . Note that while the equivalence of (P2) and (P3) is rather transparent (they are related via Fenchel’s duality), the equivalence of these to (P1) is quite sophisticated. In an earlier period of study of property (P1) Horn  recursively constructed a finite list of nontrivial necessary conditions on $`\lambda ,\nu ,\mu `$ to satisfy this property and conjectured the sufficiency of this list (which, in particular, implies that these $`(\lambda ,\mu ,\nu )`$’s constitute a polyhedral cone). Horn’s conditions are viewed as linear inequalities of the form

(1.2)
$$\lambda (I)+\mu (J)+\nu (K)0$$

for certain subsets $`I,J,K`$ of $`\{1,\mathrm{},n\}`$ with $`|I|=|J|=|K|`$, letting $`\alpha (S):=(\alpha _i:iS)`$ for $`\alpha =(\alpha _1,\mathrm{},\alpha _n)^n`$ and $`S\{1,\mathrm{},n\}`$. Subsequent efforts of several authors (where the breakthrough contribution was due to Klyachko ) have resulted in a proof of Horn’s conjecture; the obtained result is referred in  as the “H-R/T/K theorem”, abbreviating the names of Helmke, Rosenthal, Totaro, and Klyachko. Recently Knutson, Tao and Woodward  established a combinatorial existence criterion for honeycombs, obtaining another proof of that theorem via the above-mentioned relation to (P1). According to their criterion, each Horn’s triple $`\{I,J,K\}`$ is induced by a puzzle, a certain subdivision of a 3-side grid into little triangles and little rhombi endowed with a certain 0,1 weighting on the sides of these pieces. An alternative method of deducing the characterization of the $`(\lambda ,\mu ,\nu )`$’s in (P1) is suggested by Danilov and Koshevoy .

The purpose of this paper is to give a direct proof of the puzzle criterion of the solvability of problem ((1.1)), without using relationships to honeycombs. More precisely, we extend the notion of puzzle in a natural way to an arbitrary convex grid $`G`$ and show that $`\sigma :E_0(G)`$ is extendable to a concave cocirculation if and only if it obeys the linear inequalities of Horn’s type determined by puzzles and the above-mentioned obvious linear constraints. The proof uses only a linear programming approach and combinatorial techniques.

This paper is organized as follows. Section 2 contains basic definitions and facts and states problem ((1.1)) as a linear program. In Section 3 we explain the notion of puzzle for a convex grid (using a somewhat different, but equivalent, definition) and formulate the main theorem giving the puzzle criterion of the solvability of the problem (Theorem 3.1). The proof of the theorem is given in Section 6, based on a weaker, linear programming, criterion of the solvability of ((1.1)) established in Sections 4 and on a representation of some dual variables as flows in a certain dual graph, explained in Section 5. The concluding Section 7 considers a slightly more general problem. It also discusses a generalization to convex grids of results in  on the puzzles determining facets of the cone $`(G)`$ for a 3-side grid $`G`$, which characterize such puzzles combinatorially and in terms of rigidity.

Related and other aspects of discrete convex (concave) functions on triangular grids in the plane and some applications in analysis and algebra are studied in . For a survey on discrete convex functions on lattices of higher dimensions and their applications in combinatorics (in particular, in the theory of matroids and submodular functions), see, e.g., .

## 2 Preliminaries

We start with terminology, notation and conventions. Edges, faces, subgraphs, paths, circuits and other relevant objects in a convex grid $`G`$ or another graph in question are usually identified with their closed images in the plane. By a path (circuit) we usually mean a simple directed path (circuit) $`P=(v_0,e_1,v_1,\mathrm{},e_k,v_k)`$, where $`e_i=(v_{i1},v_i)`$; it may be abbreviately denoted as $`(e_1,e_2,\mathrm{},e_k)`$ (via edges). A path $`P`$ with beginning vertex $`u`$ and end vertex $`v`$ is called a $`uv`$ path; $`P`$ is called degenerate if $`u=v`$ (i.e., $`|P|=0`$). When $`P`$ forms a straight-line segment in the plane, $`P`$ is called a straight path, or a line of the graph. A $`k`$-circuit is a circuit with $`k`$ edges.

Since problem ((1.1)) does not depend, in essense, on the choice of vectors $`\xi _1,\xi _2,\xi _3`$ (subject to the condition in the Introduction), we fix these for convenience as $`\xi _1=(1,0)`$, $`\xi _2=(1,\sqrt{3})/2`$ and $`\xi _3=(1,\sqrt{3})/2`$. Then the little triangles of $`G`$ are equilateral triangles of size 1. Note that the boundary of any triangle in $`G`$ (formed by the union of some faces) is a circuit directed clockwise or counterclockwise around the triangle. The little triangle surrounded by a 3-circuit $`C`$ is denoted by $`\mathrm{\Delta }_C`$. We say that a triangle is normal if its boundary circuit is directed counterclockwise, and turned-over otherwise.

We denote the sets of outer edges directed counterclockwise and clockwise around $``$ by $`E_0^+(G)`$ and $`E_0^{}(G)`$, respectively. A maximal straight path in $`b(G)`$, or a side-path of $`G`$, whose edges are parallel to $`\xi _i`$ and belong to $`E_0^+(G)`$ (resp. $`E_0^{}(G)`$) is denoted by $`B_i^+`$ (resp. $`B_i^{}`$). One may assume that if $`G`$ is a 3-side grid, then the boundary of $`G`$ is formed by $`B_1^+,B_2^+,B_3^+`$.

For a function $`h`$ on $`E(G)`$, its restriction to the set of outer edges is called the border of $`h`$.

Next we explain how to write problem ((1.1)) as a linear program. Obviously, a function $`f:V(G)`$ is discrete concave if and only if

(2.1)
$$f(u)+f(u^{})f(v)+f(v^{})$$

holds for each little rhombus (the union of two little triangles sharing a common edge) $`\rho `$, where $`u,u^{}`$ are the acute vertices and $`v,v^{}`$ are the obtuse vertices of $`\rho `$:

Clearly $`h^{E(G)}`$ is a cocirculation if and only if the sum of its values on each 3-circuit is zero. (Hereinafter we do not distinguish between real-valued functions on a finite set $`E`$ and vectors in the Euclidean space $`^E`$ whose coordinates are indexed by the elements of $`E`$.) Linear constraints reflecting the property of a cocirculation $`h`$ to be concave are derived from (2.1). Let us say that an ordered pair $`\tau =(e,e^{})`$ of non-adjacent edges of $`G`$ is a tandem if they occur as opposite sides of a little rhombus $`\rho `$ and the head of $`e`$ is an obtuse vertex of $`\rho `$ (while the other obtuse vertex of $`\rho `$ is the tail of $`e^{}`$). We distinguish between two sorts of tandems by specifying $`\tau `$ as a normal tandem if the little triangle in $`\rho `$ containing $`e`$ is normal, and a turned-over tandem otherwise. Note that each little rhombus $`\rho `$ involves two tandems one of which is normal and the other is turned-over. The picture illustrates the case when $`e,e^{}`$ are parallel to $`\xi _1`$.

For the cocirculation $`h`$ generated by a function $`f`$ on the vertices, (2.1) is just equivalent to the condition $`h(e)h(e^{})`$ on the normal tandem $`(e,e^{})`$ in the little rhombus $`\rho `$. Thus, given $`\sigma ^{E_0(G)}`$, a concave cocirculation with the border $`\sigma `$ is a solution $`h^{E(G)}`$ of the system:

(2.2)
$$h(e)+h(e^{})+h(e^{\prime \prime })=0,C=(e,e^{},e^{\prime \prime })𝒞(G),$$

(2.3)
$$h(e^{})h(e)0,\tau =(e,e^{})𝒯(G),$$

(2.4)
$$h(e)=\sigma (e),eE_0(G),$$

where $`𝒞(G)`$ is the set of 3-circuits (considered up to cyclically shifting), and $`𝒯(G)`$ the set of normal tandems in $`G`$. When this system has a solution, we call $`\sigma `$ feasible.

As mentioned in the Introduction, there are two elementary conditions on $`\sigma `$ to be feasible. The first one (necessary for the border of any cocirculation) is the zero-sum condition:

(2.5)
$$\sigma (E_0^+(G))\sigma (E_0^{}(G))=0,$$

The second one is the monotone condition:

1. $`\sigma (e)\sigma (e^{})`$ for each straight path $`(e,e^{})`$ of $`b(G)`$.

Since the set of concave cocirculations on $`G`$ is described by a finite number of linear constraints, the set $`(G)`$ of feasible functions $`\sigma `$ (the borders of concave cocirculations in $`G`$) forms a convex polyhedral cone in $`^{E_0(G)}`$. To compute the dimension of this cone is easy (cf. ).

###### Statement 2.1

$`dim((G))=|E_0(G)|1`$.

Proof. In view of (2.5), $`dim((G))|E_0(G)|1=:r`$. To show the reverse inequality, we first construct a concave cocirculation $`h`$ for which all tandem inequalities in (2.3) are strict.

Take a maximal straight $`uv`$ path $`P`$ of $`G`$ not contained in $`b(G)`$. Let $`Z`$ be the set of edges of $`G`$ that lie in the region on the right from $`P`$ (when moving from $`u`$ to $`v`$) and are not parallel to $`P`$. Define $`h_P(e)`$ to be 1 if $`eZ`$ and $`e`$ points toward $`P`$, $`1`$ for the other edges $`e`$ in $`Z`$, and 0 for the remaining edges of $`G`$. One can check that $`h_P`$ is a concave cocirculation and that $`h(e)>h(e^{})`$ for each tandem $`(e,e^{})`$ where $`e`$ and $`e^{}`$ are separated by $`P`$. The sum of $`h_P`$’s over all such paths $`P`$ gives the desired concave cocirculation $`h`$. Let $`\sigma `$ be the border of $`h`$.

Now for each outer vertex $`v`$ and each edge $`e`$, define $`h_v(e)`$ to be 1 if $`v`$ is the head of $`e`$, $`1`$ if $`v`$ is the tail of $`e`$, and 0 otherwise. Then $`h_v`$ is a cocirculation; moreover, $`h+\frac{1}{2}h_v`$ is a concave cocirculation. Let $`\sigma _v`$ be the border of $`h_v`$. Clearly $`r`$ borders among these $`\sigma _v`$ are linearly independent. This implies that $`r`$ borders $`\sigma +\frac{1}{2}\sigma _v`$ of the concave cocirculations $`h+\frac{1}{2}h_v`$ are linearly independent.

## 3 Theorem

Linear programming (Farkas lemma) suggests a standard way to obtain a solvability criterion for system (2.2)–(2.4). Our aim, however, is to obtain a sharper, combinatorial, characterization for the borders of concave cocirculations on $`G`$.

First of all we construct a certain dual digraph $`H`$. For each edge $`eE(G)`$, take the median point $`v_e`$ on $`e`$, making it a vertex of $`H`$. For each normal tandem $`\tau =(e,e^{})`$, form (straight-line) edge $`a_\tau `$ from $`v_e`$ to $`v_e^{}`$, making it an edge of $`H`$. Note that when $`e,e^{}`$ are parallel to $`\xi _i`$, the edge $`a_\tau `$ is anti-parallel to $`\xi _{i1}`$, in the sense that $`a_\tau `$ is a parallel translate of the opposite vector $`\xi _{i1}`$. (Hereinafter the corresponding indices are taken modulo 3.) The resulting graph $`H`$ is the union of three disjoint digraphs $`H_1,H_2,H_3`$, where $`H_i`$ is induced by the introduced edges connecting points on edges of $`G`$ parallel to $`\xi _i`$. The three types of edges of $`H`$ are drawn in bold in the picture.

So the maximal paths in $`H_i`$ are straight, pairwise disjoint and anti-parallel to $`\xi _{i1}`$. If a path $`P`$ of $`H`$ begins at $`v_e`$ and ends at $`v_e^{}`$, we say that $`P`$ leaves the edge $`e`$ and enters the edge $`e^{}`$ (of $`G`$), admitting the case of degenerate $`P`$. We also say that $`P`$ leaves (enters) a little triangle $`\mathrm{\Delta }`$ if $`e\mathrm{\Delta }`$ (resp. $`e^{}\mathrm{\Delta }`$).

Definition. A puzzle is a pair $`\mathrm{\Pi }=(,𝒫)`$ consisting of a set $``$ of little triangles of $`G`$ and a set $`𝒫`$ of paths of $`H`$ such that:

1. * the interiors of triangles in $``$ and paths in $`𝒫`$ are pairwise disjoint;
    * for each edge $`e`$ of each normal (resp. turned-over) triangle in $``$, there is precisely one path in $`𝒫`$ entering (resp. leaving) $`e`$;
    * for each path in $`𝒫`$ leaving edge $`e`$ and entering edge $`e^{}`$, either $`e`$ belongs to a turned-over triangle in $``$ or $`eE_0^+(G)`$, and similarly, either $`e^{}`$ belongs to a normal triangle in $``$ or $`eE_0^{}(G)`$.

(Degenerate paths $`P=v_e`$ in $`𝒫`$ are admitted. When $`e`$ is an inner edge, such a $`P`$ serves to “connect”the pair of triangles in $``$ sharing the edge $`e`$. When $`e`$ is an outer edge, $`P`$ “connects” this edge with the triangle in $``$ containing $`e`$.) The boundary $`b(\mathrm{\Pi })`$ of $`\mathrm{\Pi }`$ is defined to be set of outer edges $`e`$ for which there is a path in $`𝒫`$ leaving or entering $`e`$. The subsets of edges of $`E_0^+(G)`$ and $`E_0^{}(G)`$ occurring in $`b(\mathrm{\Pi })`$ are denoted by $`b^+(\mathrm{\Pi })`$ and $`b^{}(\mathrm{\Pi })`$), respectively.

The puzzle criterion of the solvability of (2.2)–(2.4) is the following.

###### Theorem 3.1

Let $`G`$ be a convex triangular grid, and let $`\sigma :E_0(G)`$ satisfy (2.5) and ((2.6)). Then a concave cocirculation $`h`$ in $`G`$ with $`h(e)=\sigma (e)`$ for all $`eE_0(G)`$ exists if and only if

(3.2)
$$\sigma (b^+(\mathrm{\Pi }))\sigma (b^{}(\mathrm{\Pi }))0$$

holds for each puzzle $`\mathrm{\Pi }`$.

Thus, the cone $`(G)`$ is described by the puzzle inequalities (3.2) and the linear constraints (2.5) and ((2.6)).

Remark. A puzzle in a 3-side grid $`G`$ introduced in Knutson et al.  is defined to be a diagram $`D`$ consisting of a subdivision of the big triangle $``$ into little triangles and little rhombi of $`G`$, and of a 0,1 labelling of the edges of $`G`$ that are sides of these pieces, satisfying the following conditions: (a) the three sides of each little triangle are labelled either 1,1,1 or 0,0,0, and (b) the sides of each little rhombus $`\rho `$ are labelled 0,1,0,1, in this order clockwise of an acute vertex of $`\rho `$ (the triangle-rhombus-label form). The boundary $`b(D)`$ of $`D`$ is defined to be the set of outer edges labelled 1. There is a natural one-to-one correspondence between the puzzles $`D`$ of  and those $`\mathrm{\Pi }=(,𝒫)`$ in the above definition (the triangle-path form) and this correspondence preserves the puzzle boundary: $`b(D)=b(\mathrm{\Pi })`$. (In this correspondence, $``$ is set of little triangles labelled 1,1,1, and the edges of $`H`$ used in the paths of $`𝒫`$ are those connecting the sides labelled 1 in the rhombi of $`D`$.) The triangle-path form of puzzle is more convenient for us to handle in the proof of Theorem 3.1, which is based on certain path and flow constructions.

To illustrate the theorem, consider a 3-side grid of size $`n`$ and a puzzle having one triangle $`\mathrm{\Delta }`$ and three paths $`P_1,P_2,P_3`$, each $`P_i`$ connecting $`\mathrm{\Delta }`$ with the side-path $`B_i^+=(b_i^1,\mathrm{},b_i^n)`$.

Let $`P_i`$ leave edge $`b_i^{r(i)}B_i`$ and enter edge $`e_i\mathrm{\Delta }`$. Summing up the inequalities in (2.3) for the normal tandems induced by the edges of $`P_i`$, we have $`\sigma (b_i^{r(i)})=h(b_i^{r(i)})h(e_i)`$. This together with (2.2) for the 3-circuit $`(e_1,e_2,e_3)`$ implies $`(\sigma (b_i^{r(i)}):i=1,2,3)0`$. Also $`r(1)+r(2)+r(3)=n+2`$. Thus, any feasible $`\sigma =(\lambda ,\mu ,\nu )(^n)^3`$ must obey

$$\lambda _i+\mu _j+\nu _k0$$

for any choice of $`i,j,k`$ with $`i+j+k=n+2`$. This is the simplest sort of Horn’s inequality (1.2).

One can associate with a puzzle $`\mathrm{\Pi }=(,𝒫)`$ graph $`\mathrm{\Gamma }_\mathrm{\Pi }`$ whose vertices are the triangles in $``$ and the edges in $`b(\mathrm{\Pi })`$ and where the vertices $`u,v`$ are connected by an edge if and only if there is a path in $`𝒫`$ leaving one and entering the other of $`u,v`$ (such a $`\mathrm{\Gamma }_\mathrm{\Pi }`$ describes the topological type of $`\mathrm{\Pi }`$, in a sense). It is not difficult to deduce that $`\mathrm{\Gamma }_\mathrm{\Pi }`$ is determined by the list of cardinalities $`|b(\mathrm{\Pi })B|`$, where $`B`$ ranges over the side-paths of $`G`$. In particular,

1. the numbers $`||`$ and $`|𝒫|`$ are determined by $`b(\mathrm{\Pi })`$.

(Instruction: shrink into a point each little triangle of $`G`$ that neither belongs to $``$ nor meets a path in $`𝒫`$, and simultaneously, for each nondegenerate $`v_ev_e^{}`$ path in $`\mathrm{\Pi }`$, shrink into $`e`$ the parallelogram with opposite sides $`e,e^{}`$. The resulting graph $`G^{}`$ is again a convex grid (possibly degenerate) in which the little triangles one-to-one correspond to those in $``$, and the edges to the paths $`𝒫`$; also the outer edges of $`G^{}`$ one-to-one correspond to the edges in $`b(\mathrm{\Pi })`$ when $`\mathrm{}`$. Moreover, $`G^{}`$ depends only on the above-mentioned cardinalities.)

## 4 Linear Programming Approach

In what follows, speaking of a tandem, we always mean a normal tandem in $`G`$. Assign a variable $`z(C)`$ to each 3-circuit $`C`$ of $`G`$, a variable $`g(\tau )_+`$ to each tandem $`\tau `$, and a variable $`d(e)`$ to each outer edge $`e`$. Then the linear system dual of (2.2)–(2.4) is viewed as

(4.1)
$$\underset{C𝒞(G):eC}{}z(C)\underset{\tau =(e,e^{})𝒯(G)}{}g(\tau )+\underset{\tau =(e^{},e)𝒯(G)}{}g(\tau )=0,eE(G)E_0(G),$$

(4.2)
$$\underset{C𝒞(G):eC}{}z(C)\underset{\tau =(e,e^{})𝒯(G)}{}g(\tau )+\underset{\tau =(e^{},e)𝒯(G)}{}g(\tau )+d(e)=0,eE_0(G).$$

Applying Farkas lemma to (2.2)–(2.4), we obtain the l.p. solvability criterion.

###### Statement 4.1

Let $`\sigma ^{E_0(G)}`$. A concave cocirculation $`h`$ with the border $`\sigma `$ exists if and only if

(4.3)
$$\sigma d0$$

holds for any $`z:𝒞(G)`$, $`g:𝒯(G)_+`$ and $`d:E_0(G)`$ satisfying (4.1) and (4.2).

Hereinafter for $`a,b^E`$, $`ab`$ denotes the inner product $`(a(e)b(e):eE)`$. We call a triple $`K=(z,g,d)`$ satisfying (4.1)–(4.2) a vector configuration, or, briefly, a v-configuration, and regard $`d`$ as its border.

Statement 4.1 implies that the cone $`𝒟`$ of borders of v-configurations (which is convex) is anti-polar to the cone $`(G)`$ of borders of concave cocirculation in $`G`$, i.e., $`𝒟:=\{d^{E_0(G)}:\sigma d0\sigma (G)\}`$. For an outer edge $`e`$, define $`\theta (e):=1`$ if $`eE_0^+(G)`$, and $`1`$ if $`eE_0^{}(G)`$. Since the dimension of $`(G)`$ is $`|E_0(G)|1`$ (by Statement 2.1) and $`(G)`$ is contained in the hyperplane $`\theta ^{}`$ orthogonal to $`\theta `$ (by (2.5)), the cone $`𝒟`$ is full-dimensional and contains the line $`\theta `$. So the facets of $`(G)`$ one-to-one correspond (by the orthogonality) to the 2-dimensional faces of $`𝒟`$, each being of the form $`r_1d+r_2\theta `$ ($`r_1_+,r_2`$) for a certain $`d^{E_0(G)}`$.

For a function (vector) $`x`$, let $`\text{supp}^+(x)`$ and $`\text{supp}^{}(x)`$ denote the positive part $`\{e:x(e)>0\}`$ and the negative part $`\{e:x(e)<0\}`$ of the support $`\text{supp}(x)`$ of $`x`$, respectively. Since inequality (4.3) is invariant in adding to $`d`$ any multiple of $`\theta `$, it suffices to verify this inequality only for the v-configurations $`K=(z,g,d)`$ satisfying:

1. (a) $`\text{supp}^+(d)E_0^+(G)`$ and $`\text{supp}^{}(d)E_0^{}(G)`$, and (b) $`\text{supp}(d)\mathrm{},E_0(G)`$.

In what follows, we throughout assume that any v-configuration in question satisfies (a). When (b) takes place too, we call $`K`$ proper.

Let $`\mathrm{\Sigma }(G)`$ be the set of $`\sigma ^{E_0(G)}`$ satisfying (2.5)–((2.6)). Then $`(G)\mathrm{\Sigma }(G)`$. A v-configuration $`K=(z,g,d)`$ is called essential if $`d`$ separates $`\mathrm{\Sigma }(G)`$, i.e., $`\sigma d<0`$ for some $`\sigma \mathrm{\Sigma }(G)`$. Consider two v-configurations $`K=(z,g,d)`$ and $`K^{}=(z^{},g^{},d^{})`$ (subject to (a) in ((4.4))). $`K`$ and $`K^{}`$ are called equivalent if their borders are proportional, i.e., $`d=rd^{}`$ for some $`r>0`$. We say that $`K^{}`$ dominates $`K`$ if at least one of the following takes place:

1. * $`\sigma \mathrm{\Sigma }(G)`$ and $`\sigma d<0`$ imply $`\sigma d^{}<0`$, and there exists $`\sigma \mathrm{\Sigma }(G)`$ such that $`\sigma d0`$ but $`\sigma d^{}<0`$; or
    * $`K`$ is proper and not equivalent to $`K^{}`$, and $`KrK^{}`$ is a v-configuration (subject to (a) in ((4.4))) for some $`r>0`$.

If $`K`$ is dominated by some $`K^{}`$, then $`K`$ is redundant and can be excluded from consideration (as $`d`$ is á priori not facet-determining for $`(G)`$). This is obvious in case (i). And in case (ii), the border $`d^{\prime \prime }:=drd^{}`$ of the v-configuration $`K^{\prime \prime }:=KrK^{}`$ is nonzero and satisfies $`(d^{\prime \prime })^{}(G)d^{}(G)`$ and $`\text{supp}(d^{\prime \prime })\text{supp}(d)`$. The former inclusion implies that if $`d^{}`$ contains a facet $`F`$ of $`(G)`$, then $`(d^{\prime \prime })^{}`$ contains $`F`$ as well. Then $`d^{\prime \prime }=r_1d+r_2\theta `$ for some $`r_1>0`$ and $`r_2`$, which contradicts the latter inclusion since $`\text{supp}(d)E_0(G)`$ and $`K,K^{}`$ are not equivalent.

Our method of proof of Theorem 3.1 consists in examining an arbitrary essential configuration $`K`$ and attempting to show that $`K`$ is dominated unless it is equivalent to some “puzzle configuration”. Note that one can consider only rational-valued $`z,g,d`$ in (4.1)–(4.2). Moreover, by scaling, it suffices to deal with integer v-configurations $`(z,g,d)`$.

For an outer edge $`e`$ of $`G`$, let $`\chi ^e`$ denote the unit base vector of $`e`$ in $`^{E_0(G)}`$ (i.e., $`\chi ^e(a)=1`$ for $`a=e`$, and 0 otherwise). We will use the following observation:

1. if $`K`$ is an essential v-configuration with border $`d`$, $`K^{}`$ is a v-configuration with border $`d^{}`$, and $`d^{}=d\chi ^e+\chi ^e^{}`$, where $`e,e^{}`$ are outer edges occurring in a straight path of $`b(G)`$ in this order, then $`K^{}`$ dominates $`K`$.

To see this, let $`d^{\prime \prime }:=\chi ^e\chi ^e^{}`$. Then $`\sigma d^{\prime \prime }0`$ for all $`\sigma \mathrm{\Sigma }(G)`$, by ((2.6)). This and $`d=d^{}+d^{\prime \prime }`$ imply $`\sigma d0`$ for all $`\sigma \mathrm{\Sigma }(G)`$ satisfying $`\sigma d^{}0`$. Take $`\sigma _1(G)`$ such that $`\sigma _1(e)>\sigma _1(e^{})`$ (existing by Statement 2.1). Then $`\sigma _1d^{}0`$ and $`\sigma _1d^{\prime \prime }>0`$, implying $`p:=\sigma _1d>0`$. Take $`\sigma _2\mathrm{\Sigma }(G)`$ such that $`q:=\sigma _2d<0`$ (existing as $`K`$ is essential). Define $`\sigma :=\sigma _2\frac{q}{p}\sigma _1`$. We have $`\sigma d=\sigma _2d\frac{q}{p}\sigma _1d=qq=0`$ and $`\sigma d^{}=\sigma d\sigma d^{\prime \prime }=\sigma d^{\prime \prime }=\sigma _2d^{\prime \prime }+\frac{q}{p}\sigma _1d^{\prime \prime }<0`$, yielding ((ii))(i).

## 5 Flow Model

In the proof of Theorem 3.1 we will take advantage of a representation of a v-configuration $`K=(z,g,d)`$ in a more combinatorial form introduced in this section.

For a 3-circuit $`C`$, let us interprete $`z(C)`$ as the weight of the little triangle $`\mathrm{\Delta }_C`$. Similarly, $`d(e)`$ is the weight of an outer edge $`e`$. For each tandem $`\tau =(e,e^{})`$, set $`g(a_\tau ):=g(\tau )`$, interpreting it as the value of flow from $`v_e`$ to $`v_e^{}`$ on the edge $`a_\tau `$ of the graph $`H`$ (introduced in Section 3). The outer edges and little triangles with nonzero weights are interpreted as “sources” or “sinks” of the flow. We say that an outer edge $`e`$ emits $`d(e)`$ (units of) flow if $`d(e)>0`$, and absorbs $`|d(e)|`$ flow if $`d(e)<0`$. Similarly, a little triangle $`\mathrm{\Delta }_C`$ emits $`z(C)`$ flow (through each of its three sides) if $`z(C)>0`$, and absorbs $`|z(C)|`$ flow if $`z(C)<0`$. Relations (4.1)–(4.2) turn into the flow balance condition

(5.1)
$$\text{div}_g(v)+_{C𝒞(G):v\mathrm{\Delta }_C}z(C)+_{eE_0(G):ve}d(e)=0\text{for each}vV(H),$$

where

$$\text{div}_g(v):=_{u:(u,v)E(H)}g(u,v)_{w:(v,w)E(H)}g(v,w).$$

Next, for a path $`P`$ in $`H`$, let $`\chi ^P^{E(H)}`$ denote the incidence vector of the set of edges of $`P`$. Considering $`g`$ as a function on $`E(H)`$, applying usual flow decomposition techniques and taking into account (5.1), one can find paths $`P_1,\mathrm{},P_k`$ in $`H`$ (possibly including degenerate paths) and positive real weights $`\alpha _1,\mathrm{},\alpha _k`$ of these paths such that:

1. $`g=\alpha _1\chi ^{P_1}+\mathrm{}+\alpha _k\chi ^{P_k}`$;

1. for each edge $`e`$ of $`G`$, the sum of weights of emitting elements containing $`e`$ is equal to the sum of weights of paths $`P_i`$ leaving $`e`$; similarly, the sum of absolute values of weights of absorbing elements containing $`e`$ is equal to the sum of weights of paths $`P_i`$ entering $`e`$.

We call $`(P_1,\mathrm{},P_k;\alpha _1,\mathrm{},\alpha _k)`$ satisfying ((5.2))–((5.3)) a paths decomposition of $`g`$.

When $`g`$ is integer-valued, there is a decomposition with all weights $`\alpha _i`$ integer (an integer paths decomposition). In this case we define a triple $`𝒦=(\mathrm{\Phi },𝒫,\iota )`$ representing $`K`$, in a sense, as follows. Take $`d(e)`$ copies of each emitting outer edge $`e`$ and $`z(C)`$ copies of each emitting triangle $`\mathrm{\Delta }_C`$, forming family $`\mathrm{\Phi }^+`$ of (unweighted) emitting elements. Take $`|d(e)|`$ copies of each absorbing outer arc $`e`$ and $`|z(C)|`$ copies of each absorbing triangle $`\mathrm{\Delta }_C`$, forming family $`\mathrm{\Phi }^{}`$ of absorbing elements. Then $`\mathrm{\Phi }`$ is the disjoint union of $`\mathrm{\Phi }^+`$ and $`\mathrm{\Phi }^{}`$. Take $`\alpha _i`$ copies of each path $`P_i`$, forming $`𝒫`$. Assign a map $`\iota :𝒫\mathrm{\Phi }^+\times \mathrm{\Phi }^{}`$ so as to satisfy the following property:

1. if $`P𝒫`$ and $`\iota (P)=(\varphi ,\varphi ^{})`$, then $`P`$ leaves $`\varphi `$ and enters $`\varphi ^{}`$; moreover, for each $`\varphi \mathrm{\Phi }^+`$ (resp. $`\varphi \mathrm{\Phi }^{}`$) and each edge $`e`$ in $`\varphi `$, there is exactly one path $`P𝒫`$ such that $`\iota (P)=(\varphi ,)`$ and $`P`$ leaves $`e`$ (resp. $`\iota (P)=(,\varphi )`$ and $`P`$ enters $`e`$).

The existence of such an $`\iota `$ follows from ((5.3)). When $`\iota (P)=(\varphi ,\varphi ^{})`$, we say that the path $`P`$ is attached to the elements $`\varphi `$ and $`\varphi ^{}`$. So each triangle in $`\mathrm{\Phi }`$ has three attached paths, by one from each of $`H_1,H_2,H_3`$, and each outer edge in $`\mathrm{\Phi }`$ has one attached path.

A converse construction also takes place. More precisely, consider families $`\mathrm{\Phi }^+,\mathrm{\Phi }^{},𝒫`$ consisting of copies of some little triangles and edges from $`E_0^+(G)`$, of copies of little triangles and edges from $`E_0^{}(G)`$, and of copies of paths in $`H`$, respectively. Let $`\mathrm{\Phi }`$ be the disjoint union of $`\mathrm{\Phi }^+`$ and $`\mathrm{\Phi }^{}`$, and $`\iota `$ a map of $`𝒫`$ to $`\mathrm{\Phi }^+\times \mathrm{\Phi }^{}`$ satisfying ((5.4)). We refer to $`𝒦=(\mathrm{\Phi },𝒫,\iota )`$ as a combinatorial configuration, or, briefly, a c-configuration. Emphasize that we admit some little triangles of $`G`$ (but not outer edges) to have copies simultaneously in both $`\mathrm{\Phi }^+`$ and $`\mathrm{\Phi }^{}`$. Now

1. define $`z(C)`$ ($`C𝒞(G)`$) to be the number of copies of the triangle $`\mathrm{\Delta }_C`$ in $`\mathrm{\Phi }^+`$ minus the number of copies of $`\mathrm{\Delta }_C`$ in $`\mathrm{\Phi }^{}`$, define $`d(e)`$ ($`eE_0(G)`$) to be the number of copies of $`e`$ in $`\mathrm{\Phi }^+`$ minus the number of copies of $`e`$ in $`\mathrm{\Phi }^{}`$, and define $`g:=\{\chi ^P:P𝒫\}`$.

Then $`z,g,d`$ give a v-configuration, denoted by $`K(𝒦)`$. We formally define border $`d(𝒦)`$ of $`𝒦`$ to be the border of $`K(𝒦)`$. Also we apply to $`𝒦`$ adjectives “proper, essential” if $`K(𝒦)`$ is such, and similarly for the property of being “equivalent to” or “dominated by” another configuration.

When no little triangle of $`G`$ has copies simultaneously in both $`\mathrm{\Phi }^+,\mathrm{\Phi }^{}`$, we say that $`𝒦`$ is regular. In particular, any c-configuration $`𝒦`$ representing a v-configuration $`K`$ by the first construction is regular; in this case $`K(𝒦)=K`$.

## 6 Proof of the Theorem

The proof of Theorem 3.1 for a convex grid $`G`$ falls into three lemmas. By the arguments in Sections 4 and 5, we can deal with c-configurations and, moreover, with those of them that are regular, essential and proper.

Given a c-configuration $`𝒦=(\mathrm{\Phi },𝒫,\iota )`$, we say that a little triangle or an outer edge of $`G`$ or a path of $`H`$ is in $`𝒦`$ if at least one copy of this element is contained there. Adding to (deleting from) $`𝒦`$ such an element means adding (deleting) exactly one copy of it.

We associate with $`𝒦`$ undirected (multi)graph $`\mathrm{\Gamma }_𝒦`$ whose vertices are the elements of $`\mathrm{\Phi }`$ and whose edges one-to-one correspond to the paths in $`𝒫`$: each path $`P𝒫`$ generates an edge connecting $`\varphi `$ and $`\varphi ^{}`$ when $`\iota (P)=(\varphi ,\varphi ^{})`$ (it is analogous to the graph $`\mathrm{\Gamma }_\mathrm{\Pi }`$ associated with a puzzle $`\mathrm{\Pi }`$, defined in the end of Section 3). The (disjoint) union of $`𝒦`$ with another or the same c-configuration $`𝒦^{}`$ is defined in a natural way and denoted by $`𝒦+𝒦^{}`$ (its associated graph $`\mathrm{\Gamma }_{𝒦+𝒦^{}}`$ is the disjoint union of $`\mathrm{\Gamma }_𝒦`$ and $`\mathrm{\Gamma }_𝒦^{}`$).

If the interiors of distinct little triangles or edges $`\varphi ,\varphi ^{},\varphi ^{\prime \prime }`$ of $`G`$ are traversed by a line of $`H`$ in this order, we say that $`\varphi ^{}`$ lies between $`\varphi `$ and $`\varphi ^{\prime \prime }`$.

We call $`𝒦`$ oriented if all triangles in $`\mathrm{\Phi }^{}`$ (the absorbing triangles) are normal and all triangles in $`\mathrm{\Phi }^+`$ (the emitting triangles) are turned-over. The first lemma eliminates the non-oriented configurations.

###### Lemma 6.1

Let a c-configuration $`𝒦=(\mathrm{\Phi },𝒫,\iota )`$ be regular, proper and essential. There exists a c-configuration $`𝒦^{}`$ such that either $`𝒦^{}`$ dominates $`𝒦`$, or $`𝒦^{}`$ is equivalent to $`𝒦`$ and is oriented.

Proof. Since we can consider any regular c-configuration equivalent to $`𝒦`$, one may assume that, among such configurations, $`𝒦`$ is chosen so that

1. the number $`\eta (𝒦):=|\mathrm{\Phi }|+|𝒫|`$ is as small as possible.

Let us say that a triangle in $`\mathrm{\Phi }`$ is good if it is either emitting and turned-over, or absorbing and normal. If all triangles are good, $`𝒦`$ is already oriented. So assume $`𝒦`$ contains at least one bad triangle. Our aim is to show that $`𝒦`$ is dominated.

First of all we impose an additional condition on $`𝒦`$. Suppose there is a degenerate path $`P𝒫`$ attached to a pair of bad triangles $`\mathrm{\Delta }\mathrm{\Phi }^+`$ and $`\mathrm{\Delta }^{}\mathrm{\Phi }^{}`$; so $`\mathrm{\Delta },\mathrm{\Delta }^{}`$ share an edge $`e`$, and $`P`$ is of the form $`v_e`$. Let $`e`$ be parallel to $`\xi _i`$ and let $`a,a^{}`$ be the edges of $`\mathrm{\Delta },\mathrm{\Delta }^{}`$, respectively, parallel to $`\xi _{i1}`$. Observe that $`H_{i1}`$ has (one-edge) path $`Q`$ leaving $`v_a`$ and entering $`v_a^{}`$. When $`𝒫`$ contains a copy of $`Q`$ attached to the pair $`(\mathrm{\Delta },\mathrm{\Delta }^{})`$ as well, we call this pair dense. See the picture where $`i=3`$.

We assume that, among all regular c-configurations having the same border $`d(𝒦)`$ and satisfying ((6.1)), $`𝒦`$ is chosen so that

1. the number $`\omega (𝒦)`$ of dense pairs in $`𝒦`$ is maximum.

Suppose the graph $`\mathrm{\Gamma }_𝒦`$ associated with $`\mathrm{\Gamma }`$ is not connected. Then $`𝒦`$ is the union of two nonempty c-configurations $`𝒦^{},𝒦^{\prime \prime }`$, and we have $`d(𝒦)=d(𝒦^{})+d(𝒦^{\prime \prime })`$ and $`\eta (𝒦)=\eta (𝒦^{})+\eta (𝒦^{})`$. ((6.1)) implies that $`d(𝒦^{})0`$ and $`𝒦^{}`$ is not equivalent to $`𝒦`$. Hence $`𝒦^{}`$ dominates $`𝒦`$, by ((ii))(ii). So one may assume that $`\mathrm{\Gamma }_𝒦`$ is connected. Then each $`\varphi \mathrm{\Phi }`$ is reachable in $`\mathrm{\Gamma }_𝒦`$ by a path from a vertex representing an outer edge; let $`\rho (\varphi )`$ denote the minimum number of edges of such a path.

We consider a bad triangle $`\mathrm{\Delta }`$ with $`\rho (\mathrm{\Delta })=:\overline{\rho }`$ minimum and proceed by induction on $`\overline{\rho }`$. Let $`P𝒫`$ be a path attached to $`\mathrm{\Delta }`$ and to an element $`\varphi \mathrm{\Phi }`$ with $`\rho (\varphi )=\overline{\rho }1`$. Consider two cases.

Case 1. Let $`\overline{\rho }=1`$. Then $`\varphi `$ is (a copy of) an outer edge $`b`$. Assume $`bE_0^+(G)`$; the case $`bE_0^{}(G)`$ is symmetric. Then $`\mathrm{\Delta }`$ is absorbing and turned-over, and $`P`$ leaves $`b`$ and enters $`\mathrm{\Delta }`$. Let for definiteness $`b`$ be parallel to $`\xi _2`$. For $`i=1,2,3`$, consider $`P_i𝒫`$ and $`\varphi _i\mathrm{\Phi }^+`$ such that $`P_i`$ is in $`H_i`$ and $`\iota (P_i)=(\varphi _i,\mathrm{\Delta })`$. Let $`e_i`$ be the edge of $`\mathrm{\Delta }`$ parallel to $`\xi _i`$. (So $`P_2=P`$ and $`\varphi _2=b`$.)

Suppose $`P_3`$ is degenerate, i.e., $`P_3=v_{e_3}`$. Then $`\varphi _3`$ is a normal emitting triangle, and therefore, $`\varphi _3`$ is bad. Take path $`Q`$ in $`H_2`$ attached to $`\varphi _3`$, and let $`\iota (Q)=(\varphi _3,\stackrel{~}{\varphi })`$. The fact that $`P_3`$ is degenerate implies that $`b,\varphi _3,\mathrm{\Delta }`$ are traversed by a line of $`H_2`$ in this order. Hence $`H_2`$ has path $`P^{}`$ leaving $`b`$ and entering $`\stackrel{~}{\varphi }`$ and path $`Q^{}`$ leaving $`\varphi _3`$ and entering $`\mathrm{\Delta }`$. Replace in $`𝒫`$ the paths $`P,Q`$ by $`P^{},Q^{}`$, making $`P^{}`$ attached to $`b,\stackrel{~}{\varphi }`$ and making $`Q^{}`$ attached to $`\varphi _3,\mathrm{\Delta }`$.

This results in a correct c-configuration $`𝒦^{}`$ with $`\eta (𝒦^{})=\eta (K)`$ in which $`(\varphi _3,\mathrm{\Delta })`$ becomes a dense pair. One can see that if $`Q`$ is nondegenerate, then such a transformation does not destroy any dense pair of the previous configuration; so $`\omega (𝒦^{})>\omega (𝒦)`$, contradicting ((6.2)). And if $`Q`$ is degenerate, then $`\varphi _3`$ and $`\stackrel{~}{\varphi }`$ share an arc of $`H_2`$, whence $`\stackrel{~}{\varphi }`$ is a turned-over absorbing triangle forming a pair of bad triangles with $`\varphi _3`$. The only possible dense pair which could be destroyed by the transformation is just $`(\varphi _3,\stackrel{~}{\varphi })`$ (when this pair is also connected in $`𝒦`$ by the corresponding path in $`H_1`$). In this case we have $`\omega (𝒦^{})\omega (𝒦)`$, so the replacement maintains ((6.2)). Moreover, the new path leaving $`b`$ (namely, $`P^{}`$) enters a bad triangle (namely, $`\stackrel{~}{\varphi }`$) as before and is shorter than $`P`$:

Doing so, we eventualy obtain a c-configuration where $`b`$ is connected with a bad triangle whose attached path in $`H_3`$ is nondegenerate.

Thus, we may assume that $`P_3`$ is nondegenerate. Then, by the convexity of $`G`$, the edge $`e_1`$ of $`\mathrm{\Delta }`$ does not lie on the boundary of $`G`$, and $`b`$ cannot be the last edge of the side-path $`B_2^+`$. We now transform $`𝒦`$ as follows. Let $`\mathrm{\Delta }^{}`$ be the normal triangle of $`G`$ containing $`e_1`$, and $`b^{}`$ the edge of $`B_2^+`$ next to $`b`$. Then $`H_2`$ has path $`P^{}`$ leaving $`b^{}`$ and entering $`\mathrm{\Delta }^{}`$ and $`H_3`$ has path $`P_3^{}`$ leaving $`\varphi _3`$ and entering $`\mathrm{\Delta }^{}`$ ($`P_3^{}`$ is a part of the nondegenerate $`P_3`$). We replace in $`𝒦`$ the edge $`b`$ by (one emitting copy of) $`b^{}`$, the triangle $`\mathrm{\Delta }`$ by (one absorbing copy of) $`\mathrm{\Delta }^{}`$, and the paths $`P,P_3`$ by $`P^{},P_3^{}`$, making $`P^{}`$ attached to $`b^{},\mathrm{\Delta }^{}`$, and making $`P_3^{}`$ attached to $`\varphi _3,\mathrm{\Delta }^{}`$ (while $`P_1`$ becomes attached to $`\mathrm{\Delta }^{}`$ instead of $`\mathrm{\Delta }`$) :

This results in a (not necessarily regular) c-configuration $`𝒦^{}`$ with the border $`d(𝒦)\chi ^b+\chi ^b^{}`$. By ((4.6)), $`𝒦`$ is dominated by $`𝒦^{}`$.

Case 2. Let $`\overline{\rho }>1`$. Assume the bad triangle $`\mathrm{\Delta }`$ is absorbing (and turned-over); the case of emitting $`\mathrm{\Delta }`$ is symmetric. Let for definiteness $`P`$ be in $`H_2`$, and define $`P_i,\varphi _i,e_i`$ ($`i=1,2,3`$) as in Case 1. (So $`P=P_2`$ and $`\varphi =\varphi _2`$.) Since $`\rho (\varphi )=\overline{\rho }11`$, $`\varphi `$ is a good triangle. So $`\varphi `$ is a turned-over emitting triangle and $`P`$ is nondegenerate. Arguing as in Case 1, we can impose the condition that $`P_3`$ is nondegenerate. This and the convexity of $`G`$ imply that neither the edge $`e_1`$ of $`\mathrm{\Delta }`$ nor the edge $`q`$ of $`\varphi `$ parallel to $`\xi _1`$ is in $`b(G)`$. Let $`\mathrm{\Delta }^{}`$ be the normal little triangle of $`G`$ containing $`e_1`$, and $`\varphi ^{}`$ the normal triangle containing $`q`$. We replace $`\mathrm{\Delta },\varphi `$ in $`\mathrm{\Phi }`$ by $`\mathrm{\Delta }^{},\varphi ^{}`$.

More precisely, when $`\mathrm{\Delta }`$ is replaced by $`\mathrm{\Delta }^{}`$, we accordingly replace the paths $`P,P_3`$ attached to $`\mathrm{\Delta }`$ by paths $`P^{},P_3^{}`$ (while $`P_1`$ preserves, becoming attached to $`\mathrm{\Delta }^{}`$). Here $`P^{}`$ is the path of $`H_2`$ leaving $`\varphi ^{}`$ and entering $`\mathrm{\Delta }^{}`$, and $`P_3^{}`$ is the path of $`H_3`$ leaving $`\varphi _3`$ and entering $`\mathrm{\Delta }^{}`$ (as before, $`P_3^{}`$ is a part of the nondegenerate path $`P_3`$). And when replacing $`\varphi `$ by $`\varphi ^{}`$, we should also replace path $`\stackrel{~}{Q}`$ of $`H_3`$ attached to $`\varphi `$, entering triangle $`\stackrel{~}{\varphi }\mathrm{\Phi }^{}`$ say, by path $`\stackrel{~}{Q}^{}`$ of $`H_3`$ leaving $`\varphi ^{}`$ and entering $`\stackrel{~}{\varphi }`$. ($`\stackrel{~}{Q}^{}`$ exists since $`\varphi `$ lies between $`\varphi ^{}`$ and $`\stackrel{~}{\varphi }`$.) The path of $`H_1`$ attached to $`\varphi `$ becomes attached to $`\varphi ^{}`$. This gives a c-configuration $`𝒦^{}`$ in which the added triangle $`\varphi ^{}`$ is bad and has the rank $`\rho (\varphi ^{})`$ equal to $`\overline{\rho }1`$.

We have $`d(𝒦^{})=d(𝒦)`$ and $`\eta (𝒦^{})=\eta (𝒦)`$. The latter implies that $`𝒦^{}`$ is regular, i.e., $`𝒦`$ has no emitting copy of $`\mathrm{\Delta }^{}`$ or $`\varphi ^{}`$. For otherwise, cancelling in $`𝒦^{}`$ one emitting copy and one absorbing copy of the same little triangle of $`G`$ and properly concatenating their attached paths, we would obtain a configuration with a smaller value of $`\eta `$, contrary to ((6.1)). Finally, one can see that neither $`\mathrm{\Delta }`$ nor $`\varphi `$ can be involved in dense pairs of $`𝒦`$. Hence no dense pair is destroyed while constructing $`𝒦^{}`$, implying $`\omega (𝒦^{})\omega (𝒦)`$. Now the result follows by induction on $`\overline{\rho }`$.

Thus, it suffices to consider only oriented configurations.

A puzzle $`\mathrm{\Pi }=(,𝒫)`$ generates an oriented c-configuration $`(\mathrm{\Phi },𝒫,\iota )`$ in a natural way: $`\mathrm{\Phi }^+`$ is the set of turned-over triangles in $``$ and edges in $`b^+(\mathrm{\Pi })`$, $`\mathrm{\Phi }^{}`$ is the set of normal triangles in $``$ and edges in $`b^{}(\mathrm{\Pi })`$, and for each $`uv`$ path $`P𝒫`$, $`\iota (P)`$ is the pair $`(\varphi \mathrm{\Phi }^+,\varphi \mathrm{\Phi }^{})`$ such that the point $`u`$ is contained in $`\varphi `$ and $`v`$ is contained in $`\varphi ^{}`$. Such a puzzle c-configuration is denoted by $`𝒦_\mathrm{\Pi }`$.

The next lemma describes a situation when an oriented configuration can be split into two configurations one of which is a puzzle configuration. Let us say that paths $`P,P^{}`$ of $`H`$ are crossing if they are not parallel and their interiors have a point in common, and that $`P`$ and a little triangle $`\mathrm{\Delta }`$ of $`G`$ are overlapping if $`P`$ meets the interior of $`\mathrm{\Delta }`$:

One can see that the puzzle configurations are precisely those having neither crossing nor overlapping pairs. Given an oriented c-configuration $`𝒦=(\mathrm{\Phi },𝒫,\iota )`$, define its minimal pre-configuration $`𝒦^{\mathrm{min}}=(\mathrm{\Psi },𝒫^{\mathrm{min}},\widehat{\iota })`$ as follows. Let $`\mathrm{\Psi }^+`$ (resp. $`\mathrm{\Psi }^{}`$) be the set of little triangles and outer edges of $`G`$ having at least one copy in $`\mathrm{\Phi }^+`$ (resp. $`\mathrm{\Phi }^{}`$). Then $`\mathrm{\Psi }=\mathrm{\Psi }^+\mathrm{\Psi }^{}`$. The set $`𝒫^{\mathrm{min}}`$ is formed by taking for each edge $`eE(G)`$ contained in a member of $`\mathrm{\Psi }^+`$, one (inclusion-wise) minimal path in $`𝒫`$ with the beginning $`v_e`$, taking for each edge $`eE(G)`$ contained in a member of $`\mathrm{\Psi }^{}`$, one minimal path in $`𝒫`$ with the end $`v_e`$, and ignoring repeated paths if arise. Define $`\widehat{\iota }`$ to be the map attaching a $`uv`$ path $`P𝒫^{\mathrm{min}}`$ to the pair $`(\varphi \mathrm{\Psi }^+,\varphi ^{}\mathrm{\Psi }^{})`$ such that $`u\varphi `$ and $`v\varphi ^{}`$ (this pair is unique since $`K`$ is oriented). Note that $`𝒦^{\mathrm{min}}`$ need not be a c-configuration since some triangles (outer edges) in it may have more than three (resp. one) attached paths.

###### Lemma 6.2

Let a c-configuration $`𝒦=(\mathrm{\Phi },𝒫,\iota )`$ be proper and oriented, and let $`𝒦^{\mathrm{min}}=(\mathrm{\Psi },𝒫^{\mathrm{min}},\widehat{\iota })`$ be its minimal pre-configuration. Suppose $`𝒦^{\mathrm{min}}`$ contains neither crossing paths nor overlapping a path and a triangle. Then: (a) $`𝒦^{\mathrm{min}}`$ is a puzzle c-configuration, and (b) $`𝒦^{\mathrm{min}}`$ either is equivalent to $`𝒦`$ or dominates $`𝒦`$.

Proof. From the non-existence of paths in $`𝒫^{\mathrm{min}}`$ overlapping triangles in $`\mathrm{\Psi }`$ it easily follows that for each element $`\varphi \mathrm{\Psi }^+`$ and each edge $`e`$ in $`\varphi `$, there is exactly one path $`P𝒫^{\mathrm{min}}`$ leaving $`e`$, and similarly for each element $`\varphi ^{}\mathrm{\Psi }^{}`$ and each edge $`e^{}`$ in $`\varphi ^{}`$, there is exactly one path $`P^{}𝒫^{\mathrm{min}}`$ entering $`e^{}`$. Hence $`𝒦^{\mathrm{min}}`$ is a c-configuration, and now the absence of crossing paths in $`𝒦`$ implies that it is a puzzle configuration, yielding (a). Next, one can rearrange the attaching map $`\iota `$ in $`𝒦`$ so that $`𝒦`$ be represented as the union of $`𝒦^{\mathrm{min}}`$ and some c-configuration $`𝒦^{\prime \prime }`$. This implies (b), by ((ii))(ii).

For $`i=1,2,3`$, a sequence $`(\varphi _1,\mathrm{},\varphi _k)`$ of distinct little triangles or edges of $`G`$ is called an $`i`$-chain if their interiors are traversed in this order by a path of $`H_i`$. If $`(\mathrm{\Delta },\mathrm{\Delta }^{})`$ is an $`i`$-chain of two normal little triangles and there is no normal triangle between them, we say that $`\mathrm{\Delta }`$ is the $`i`$-predecessor of $`\mathrm{\Delta }^{}`$, and similarly for turned-over triangles.

Our final lemma is the following.

###### Lemma 6.3

Let a c-configuration $`𝒦=(\mathrm{\Phi },𝒫,\iota )`$ be proper, essential and oriented. If $`𝒦`$ is not equivalent to a puzzle c-configuration, then $`𝒦`$ is dominated.

Proof. Since we can replace $`𝒦`$ by any oriented c-configuration equivalent to $`𝒦`$ (e.g., by taking the union of $`r`$ copies of $`𝒦`$ for any $`r`$), one may assume that, among such configurations, $`𝒦`$ is chosen so that:

1. * there are sufficiently many copies of each member of $`\mathrm{\Phi }𝒫`$;
    * subject to (i), the number $`t(𝒦)`$ of little triangles of $`G`$ having copies in $`\mathrm{\Phi }`$ is maximum;
    * subject to (i),(ii), the number $`p(𝒦)`$ of paths of $`H`$ having copies in $`𝒦`$ is maximum.

From (iii) it follows that

1. for any (not necessarily distinct) vertices $`u_1,u_2,u_3,u_4`$ occurring in a path of $`H`$ in this order, if $`𝒫`$ contains copies of both $`u_1u_3`$ path $`P`$ and $`u_2u_4`$ path $`P^{}`$, then $`𝒫`$ contains copies of both $`u_1u_4`$ path $`Q`$ and $`u_2u_3`$ path $`Q^{}`$ as well, and vice versa.

Indeed, if at least one of $`Q,Q^{}`$ is not in $`𝒫`$, we can add $`Q,Q^{}`$ to $`𝒫`$ and delete $`P,P^{}`$ from $`𝒫`$, accordingly correcting the map $`\iota `$. This increases $`p(𝒦)`$. (Recall that adding to $`𝒦`$ a triangle or an outer edge of $`G`$ or a path of $`H`$ means adding one copy of this element, and similarly for deleting an element.) The reverse assertion is proved similarly.

Also we assume that the minimal pre-configuration $`𝒦^{\mathrm{min}}`$ contains crossing paths or overlapping a path and a triangle; otherwise the result immediately follows from Lemma 6.2. We show that $`𝒦`$ is dominated in both cases.

Case 1. Let $`𝒦^{\mathrm{min}}`$ contain crossing a $`uv`$ path $`P`$ and a $`u^{}v^{}`$ path $`Q`$. Assume for definiteness that $`P`$ is in $`H_2`$ and minimal among the paths of $`𝒫`$ beginning at $`u`$, and that $`Q`$ is in $`H_1`$ ($`P`$ is anti-parallel to $`\xi _1`$ and $`Q`$ is anti-parallel to $`\xi _3`$); the case when $`P`$ is minimal among the paths ending at $`v`$ is symmetric. Observe that the point $`w`$ where $`P,Q`$ intersect is a vertex of $`H_2`$. Let $`\mathrm{\Delta }`$ be the normal little triangle whose edge parallel to $`\xi _2`$ contains $`w`$ as the median point. Then $`\mathrm{\Delta }`$ is not in $`\mathrm{\Phi }`$. For otherwise $`𝒫`$ would contain a path from some vertex $`w^{}`$ to $`w`$ (as $`\mathrm{\Delta }`$ is absorbing). Applying ((6.4)) to $`w^{},u,w,v`$ or to $`u,w^{},w,v`$, we obtain that $`𝒫`$ contains the $`uw`$ path, contradicting the minimality of $`P`$.

Next we proceed as follows. For $`i=1,2,3`$, let $`e_i`$ be the edge of $`\mathrm{\Delta }`$ parallel to $`\xi _i`$. (So $`w=v_{e_2}`$.) Take the turned-over little triangle $``$ containing $`e_3`$. Let $`e_1^{},e_2^{}`$ be the edges of $``$ parallel to $`\xi _1,\xi _2`$, respectively. Then $`H_2`$ has $`uw`$ path $`P^{}`$ and $`v_{e_2^{}}v`$ path $`P^{\prime \prime }`$, and $`H_1`$ has $`u^{}v_{e_1}`$ path $`Q^{}`$:

Add (one copy of) the triangle $`\mathrm{\Delta }`$ to $`\mathrm{\Phi }^{}`$, the triangle $``$ to $`\mathrm{\Phi }^+`$, and the paths $`P^{},P^{\prime \prime },Q^{}`$ together with the degenerate path $`v_{e_3}`$ (“connecting” $`\mathrm{\Delta }`$ and $``$ in $`H_3`$) to $`𝒫`$. Accordingly delete $`P,Q`$ from $`𝒫`$. The attachments for the added elements are assigned in a natural way (e.g., $`\iota (P^{}):=(\varphi ,\mathrm{\Delta })`$, where $`\varphi `$ is the element of the old $`\mathrm{\Phi }^+`$ to which $`P`$ was attached). This increases the value of the parameter $`t`$ (since $`\mathrm{\Delta }`$ is added while the new $`𝒦`$ contains a copy of each triangles from the previous $`𝒦`$, by assumption ((iii))(i)). However, $`𝒦`$ becomes an “incomplete” configuration since $``$ has no attached path in $`H_1`$, and similarly for element $`\widehat{\varphi }`$ of $`\mathrm{\Phi }^{}`$ to which $`Q`$ was attached. We cannot improve $`𝒦`$ straightforwardly because the points $`\stackrel{~}{u}:=v_{e_1^{}}`$ and $`v^{}`$ do not lie on one line of $`H_1`$.

Our aim is to improve this $`𝒦`$ without decreasing the current value of $`t`$, in order to obtain a correct c-configuration $`𝒦^{}`$ either dominating or equivalent to the initial $`𝒦`$. This will yield the result in the former case and lead to a contradiction with assumption ((iii))(ii) in the latter case.

First of all we iteratively construct a sequence $`S`$ of alternating members of $`\mathrm{\Phi }`$ and $`𝒫`$ as follows. Start with $`\mathrm{\Delta }_1:=\widehat{\varphi }`$. Let $`\mathrm{\Delta }_i\mathrm{\Phi }`$ be the last element of the current $`S`$. If $`\mathrm{\Delta }_i`$ is an outer edge, halt. Otherwise add $`P_{i+1},\mathrm{\Delta }_{i+1}`$ to $`S`$, where $`P_{i+1}`$ is attached to $`\mathrm{\Delta }_i,\mathrm{\Delta }_{i+1}`$. More precisely: (a) if $`i`$ is odd (and $`\mathrm{\Delta }_i`$ is a normal triangle), then $`P_{i+1}`$ is a path of $`H_2`$ and $`\iota (P_{i+1})=(\mathrm{\Delta }_{i+1},\mathrm{\Delta }_i)`$, and (b) if $`i`$ is even (and $`\mathrm{\Delta }_i`$ is a turned-over triangle), then $`P_{i+1}`$ is a path of $`H_1`$ and $`\iota (P_{i+1})=(\mathrm{\Delta }_i,\mathrm{\Delta }_{i+1})`$. Let $`\mathrm{\Delta }_{q+1}`$ be the last element of the final $`S`$. Clearly the edge $`b:=\mathrm{\Delta }_{q+1}`$ belongs to $`B_2^+`$ when $`q`$ is odd, and to $`B_1^{}`$ when $`q`$ is even.

Assume $`q`$ is odd; the case of $`q`$ even is examined analogously. For $`i=1,\mathrm{},q`$, let $`Q_i𝒫`$ be the path of $`H_3`$ attached to $`\mathrm{\Delta }_i`$ (it enters $`\mathrm{\Delta }_i`$ for $`i`$ odd, and leaves $`\mathrm{\Delta }_i`$ for $`i`$ even). Let $`\mathrm{\Delta }_i^{}`$ be the other element of $`\mathrm{\Phi }`$ to which $`Q_i`$ is attached. We say that the triangle $`\mathrm{\Delta }_i`$ is squeezed if $`i`$ is odd and $`Q_i`$ is degenerate.

We first explain how to transform $`𝒦`$ into the desired correct c-configuration when no $`\mathrm{\Delta }_i`$ is squeezed. By the convexity of $`G`$ (and regardless of the squeezedness of any $`\mathrm{\Delta }_i`$), the line in the plane parallel to $`\xi _3`$ and passing the point $`\stackrel{~}{u}`$ separates $`S`$ from $`B_3^+`$ (letting $`B_3^+`$ be the common vertex of $`B_2^{}`$ and $`B_1^{}`$ when they meet). This implies that $`S`$ can be shifted by distance 1 in the direction of $`\xi _2`$ (approaching $`B_3^+`$). More precisely, each triangle $`\mathrm{\Delta }_i`$ has 3-predecessor $`\stackrel{~}{\mathrm{\Delta }}_i`$ in $`G`$, and $`B_2^+`$ contains edge $`\stackrel{~}{b}`$ next to $`b`$. See the picture where $`q=3`$.

These triangles $`\stackrel{~}{\mathrm{\Delta }}_i`$ and the elements $`\stackrel{~}{\mathrm{\Delta }}_0:=`$ and $`\stackrel{~}{\mathrm{\Delta }}_{q+1}:=\stackrel{~}{b}`$ are connected in $`H`$ by paths $`P_1^{},\mathrm{},P_{q+1}^{}`$ in a natural way: $`P_i^{}`$ is the path of $`H_1`$ leaving $`\stackrel{~}{\mathrm{\Delta }}_i`$ and entering $`\stackrel{~}{\mathrm{\Delta }}_{i+1}`$ when $`i`$ is odd, and the path of $`H_2`$ leaving $`\stackrel{~}{\mathrm{\Delta }}_{i+1}`$ and entering $`\stackrel{~}{\mathrm{\Delta }}_i`$ when $`i`$ is even. Also there are paths $`Q_1^{},\mathrm{},Q_q^{}`$ of $`H_3`$ such that $`Q_i^{}`$ leaves $`\mathrm{\Delta }_i^{}`$ and enters $`\stackrel{~}{\mathrm{\Delta }}_i`$ when $`i`$ is odd (as $`\mathrm{\Delta }_i`$ is not squeezed, and therefore, $`\stackrel{~}{\mathrm{\Delta }}_i`$ lies between $`\mathrm{\Delta }_i^{}`$ and $`\mathrm{\Delta }_i`$), and $`Q_i^{}`$ leaves $`\stackrel{~}{\mathrm{\Delta }}_i`$ and enters $`\mathrm{\Delta }_i^{}`$ when $`i`$ is even.

Add to $`𝒦`$ the triangles $`\stackrel{~}{\mathrm{\Delta }}_1,\mathrm{},\stackrel{~}{\mathrm{\Delta }}_q`$, the paths $`P_1^{},\mathrm{},P_{q+1}^{},Q_1^{},\mathrm{},Q_q^{}`$ and the edge $`\stackrel{~}{b}`$, making $`P_i^{}`$ attached to $`\stackrel{~}{\mathrm{\Delta }}_{i1},\stackrel{~}{\mathrm{\Delta }}_i`$, and making $`Q_j^{}`$ attached to $`\stackrel{~}{\mathrm{\Delta }}_j,\mathrm{\Delta }_j^{}`$. Accordingly delete from $`𝒦`$ the triangles $`\mathrm{\Delta }_1,\mathrm{},\mathrm{\Delta }_q`$, the paths $`P_2,\mathrm{},P_{q+1},Q_1,\mathrm{},Q_q`$ and the outer edge $`b`$. This results in a correct c-configuration $`𝒦^{}`$. Moreover, $`𝒦^{}`$ has the border $`d(𝒦)\chi ^b+\chi ^{\stackrel{~}{b}}`$. Therefore, $`𝒦^{}`$ dominates the initial $`𝒦`$, by ((4.6)).

Next suppose there is a squeezed $`\mathrm{\Delta }_i`$ ($`i`$ is odd); let $`i`$ be minimum among such triangles. Form the triangles $`\stackrel{~}{\mathrm{\Delta }}_0,\mathrm{},\stackrel{~}{\mathrm{\Delta }}_{i1}`$ and paths $`P_1^{},\mathrm{},P_i^{},Q_1^{},\mathrm{},Q_{i1}^{}`$ as above. Take paths $`R,D𝒫`$ attached to $`\mathrm{\Delta }_i^{}`$ and belonging to $`H_2`$ and $`H_1`$, respectively. Let $`\varphi ,\varphi ^{}`$ be the other (normal) triangles to which $`R,D`$ are attached, respectively. Since $`\mathrm{\Delta }_i`$ is squeezed, $`(\mathrm{\Delta }_{i+1},\mathrm{\Delta }_i,\mathrm{\Delta }_i^{},\varphi )`$ is a 2-chain and $`(\stackrel{~}{\mathrm{\Delta }}_{i1},\mathrm{\Delta }_i^{},\varphi ^{})`$ is a 1-chain:

Let $`M`$ be the path of $`H_2`$ leaving $`\mathrm{\Delta }_{i+1}`$ and entering $`\varphi `$, and $`M^{}`$ the path of $`H_1`$ leaving $`\stackrel{~}{\mathrm{\Delta }}_{i1}`$ and entering $`\varphi ^{}`$. We add to $`𝒦`$ the triangles $`\stackrel{~}{\mathrm{\Delta }}_1,\mathrm{},\stackrel{~}{\mathrm{\Delta }}_{i1}`$ and the paths $`P_1^{},\mathrm{},P_i^{},Q_1^{},\mathrm{},Q_{i1}^{},M,M^{}`$ and accordingly delete the triangles $`\mathrm{\Delta }_1,\mathrm{},\mathrm{\Delta }_i`$ and $`\mathrm{\Delta }_i^{}`$ and the paths $`P_2,\mathrm{},P_{i+1},Q_1,\mathrm{},Q_i,R,D`$. (Note that if $`P_i`$ is degenerate, then $`\stackrel{~}{\mathrm{\Delta }}_{i1}`$ and $`\mathrm{\Delta }_i^{}`$ are copies of the same triangle of $`G`$; we consider them as different objects one of which is added and the other is deleted.) The resulting $`𝒦^{}`$ is a correct c-configuration with the same border $`d(𝒦)`$. But $`t(𝒦^{})>t(𝒦)`$ (as $`\mathrm{\Delta }`$ was added, while deleting the above triangles does not affect $`t`$, by ((iii))(i)). This contradicts ((iii))(ii).

Case 2. Let $`𝒦^{\mathrm{min}}`$ contain overlapping a path $`P`$ and a triangle $`\varphi `$. One may assume that $`P`$ is a $`uv`$ path of $`H_1`$ and that $`P`$ is minimal among the paths in $`𝒫`$ beginning at $`u`$. Let $`\iota (P)=(\varphi ^{},\varphi ^{\prime \prime })`$. Then $`\varphi `$ lies between $`\varphi ^{}`$ and $`\varphi ^{\prime \prime }`$. Notice that there is no normal (absorbing) triangle $`\stackrel{~}{\varphi }\mathrm{\Phi }`$ between $`\varphi ^{}`$ and $`\varphi ^{\prime \prime }`$. For if such a $`\stackrel{~}{\varphi }`$ exists, then the end vertex $`w`$ of the path of $`H_1`$ attached to $`\stackrel{~}{\varphi }`$ is an intermediate vertex of $`P`$. But then $`𝒫`$ contains the $`uw`$ path (by ((6.4))), contrary to the minimality of $`P`$. So $`\varphi `$ is a turned-over (emitting) triangle.

Take path $`Q`$ of $`H_2`$ attached to $`\varphi `$; let $`\iota (Q)=(\varphi ,\psi )`$. Since the absorbing element $`\psi `$ cannot be a normal triangle lying between $`\varphi ^{}`$ and $`\varphi ^{\prime \prime }`$ (by the argument above), the path $`Q`$ is nondegenerate. Let $`e`$ be the edge of $`\varphi `$ parallel to $`\xi _2`$, and $`\mathrm{\Delta }`$ the normal little triangle of $`G`$ containing $`e`$. Then $`\mathrm{\Delta }`$ lies between $`\varphi ^{}`$ and $`\varphi ^{\prime \prime }`$; let $`P^{}`$ be the path of $`H_1`$ leaving $`\varphi ^{}`$ and entering $`\mathrm{\Delta }`$. Note that $`𝒦`$ contains no copy of $`\mathrm{\Delta }`$ (again by the argument above). Next, let $`e^{}`$ be the edge of $`\mathrm{\Delta }`$ parallel to $`\xi _3`$, and $``$ the turned-over triangle of $`G`$ containing $`e^{}`$. Then $``$ lies between $`\varphi `$ and $`\psi `$ (as $`Q`$ is nondegenerate); let $`Q^{}`$ be the path of $`H_2`$ leaving $``$ and entering $`\psi `$.

Add to $`𝒦`$ the triangles $`\mathrm{\Delta },`$, the paths $`P^{},Q^{}`$, the degenerate path $`v_e`$ (“connecting” $`\varphi `$ and $`\mathrm{\Delta }`$ in $`H_2`$) and the degenerate path $`v_e^{}`$ (“connecting” $``$ and $`\mathrm{\Delta }`$ in $`H_3`$), assigning the attachments for them in an obvious way. Accordingly delete from $`𝒦`$ the paths $`P,Q`$. This results in an “incomplete” c-configuration, but having a larger value of $`t`$, in which $``$ and $`\varphi ^{\prime \prime }`$ have no attached paths in $`H_1`$. (It cannot be improved straightforwardly since $`v`$ and the median point $`\stackrel{~}{u}`$ of the edge of $``$ parallel to $`\xi _1`$ do not lie on one line of $`H_1`$). So we have a situation as in Case 1 and proceed in a similar way to transform $`𝒦`$ into a correct c-configuration $`𝒦^{}`$ either dominating the initial $`𝒦`$ or being equivalent to $`𝒦`$ but having a larger value of $`t`$.

This completes the proof of the lemma.

By Lemmas 6.1 and 6.3, any non-dominated proper essential configuration is equivalent to a puzzle configuration. This implies Theorem 3.1, in view of explanations in Sections 4,5.

Remark. Analysing the proof of Lemma 6.3, one sees that, in fact, a slightly sharper version of this lemma is obtained; namely, taking into account assumption ((iii))(ii) and the construction of the minimal pre-configuration $`𝒦^{\mathrm{min}}`$:

1. if a c-configuration $`𝒦`$ is proper, essential and oriented and if $`𝒦`$ is not dominated, then $`𝒦`$ is equivalent to a puzzle configuration $`𝒦_\mathrm{\Pi }`$ such that the set of triangles of the puzzle $`\mathrm{\Pi }`$ includes all little triangles of $`G`$ having copies in $`𝒦`$.

## 7 Concluding Remarks

We conclude this paper with several remarks.

First, for a cocirculation $`h`$ in $`G`$ and a tandem $`\tau =(e,e^{})`$, call $`\delta _h(\tau ):=h(e)h(e^{})`$ the discrepancy of $`h`$ at $`\tau `$. So $`h`$ is concave if the discrepancy at each tandem is nonnegative. A more general problem ($``$) is to find a cocirculation $`h`$ having a given border $`\sigma `$ and obeying prescribed lower bounds $`c`$ on the discrepancies: $`\delta _h(\tau )c(\tau )`$ for each $`\tau 𝒯(G)`$. This is reduced to the case of zero bounds when $`c`$ comes up from another cocirculation $`g`$ in $`G`$. More precisely, let $`c(\tau ):=\delta _g(\tau )`$ for each tandem $`\tau `$. Re-define the required border by $`\sigma ^{}(e):=\sigma (e)g(e)`$ for each outer edge $`e`$. Then $`h^{}`$ is a concave cocirculation with the border $`\sigma ^{}`$ if and only if $`h:=h^{}+g`$ is a cocirculation with the border $`\sigma `$ satisfying the lower bound $`c`$ on the discrepancies. Thus, the corresponding changes in the puzzle inequalities (3.2) and in the monotone condition ((2.6)) give a solvability criterion for problem ($``$) with a cocirculation-induced $`c`$.

In particular, the puzzle criterion modified in this way works when all tandem discrepancies are required to be greater than or equal to a prescribed constant $`\alpha `$. This is because there exists a cocirculation $`g`$ in $`G`$ where the discrepancy at each tandem is exactly $`\alpha `$. (Such a $`g`$ is constructed easily: assuming w.l.o.g. that $`G`$ is a 3-side grid of size $`n`$, put $`g(e_i):=(k2i+1)\alpha `$ ($`i=1,\mathrm{},k`$) for each side-path $`(e_1,\mathrm{},e_k)`$ in $`G`$.)

Second, from the sharper version of Lemma 6.3 given in ((6.5)) one derives that each puzzle $`\mathrm{\Pi }`$ determining a facet of $`(G)`$ is (uniquely) determined by its boundary $`b(\mathrm{\Pi })`$.

Indeed, suppose $`\mathrm{\Pi }_1,\mathrm{\Pi }_2`$ are two different puzzles with $`b(\mathrm{\Pi }_1)=b(\mathrm{\Pi }_2)`$. Let $`𝒦_i`$ stand for the c-configuration induced by $`\mathrm{\Pi }_i`$; one may assume that $`𝒦_i`$ is proper and essential. Then $`𝒦:=𝒦_1+𝒦_2`$ is an oriented c-configuration equivalent to $`𝒦_i`$. Assume $`𝒦`$ is not dominated and take the puzzle $`\mathrm{\Pi }`$ as in ((6.5)). We have $`b(𝒦_\mathrm{\Pi })=b(𝒦_i)`$, so the number $`q`$ of triangles in $`\mathrm{\Pi }`$ is equal to the number $`q_1`$ of triangles in $`\mathrm{\Pi }_1`$, by ((3.3)). On the other hand, the fact that $`\mathrm{\Pi }_1`$ and $`\mathrm{\Pi }_2`$ are different implies that $`𝒦`$ involves more little triangles of $`G`$ compared with $`𝒦_1`$. This implies $`q>q_1`$, by ((6.5)); a contradiction.

Different puzzles with equal boundaries do exist. An example for a 3-side grid is shown in Fig. 1.

A puzzle determined by its boundary is called rigid. Knutson, Tao and Woodward proved that in the case of 3-side grids the facet-determining puzzles are exactly the rigid ones. They, moreover, obtained a combinatorial characterization of facet-determining puzzles, implying that they are recognizable in polynomial time.

###### Theorem 7.1

 Let $`\mathrm{\Pi }=(,𝒫)`$ be a puzzle in a 3-side grid $`G`$ such that $``$ is nonempty and different from the set of all little triangles of $`G`$. The following are equivalent:

* $`\mathrm{\Pi }`$ determines a facet of $`(G)`$;
* $`\mathrm{\Pi }`$ is rigid;
* $`\mathrm{\Pi }`$ admits no gentle circuits.

To explain the notion of gentle path/circuit, let $`R`$ be the set of little rhombi of $`G`$ that are split by a path in $`𝒫`$ into two parallelograms. Let $`G_0`$ be the subgraph of $`G`$ induced by the edges separating either a triangle in $``$ and a rhombus in $`R`$ (the tp-edges), or a rhombus in $`R`$ and a little triangle contained in no member of $`R`$ (the pn-edges). Re-orient each tp-edge (resp. pn-edge) $`e`$ so that the triangle of $``$ (resp. the rhombus in $`R`$) containing $`e`$ lie on the right. A path or circuit $`P`$ of $`G_0`$ is called gentle if, when moving along $`P`$ from an edge to the next edge, the angle of turn is either $`0^{}`$ or $`60^{}`$, never $`120^{}`$. For example, the circuit surrounding the hexagon formed by the six central triangles in the right puzzle in Fig. 1 is gentle.

One can show that Theorem 7.1 remains valid for an arbitrary convex grid $`G`$. (Implication (i)$``$(ii) has already been shown. The method of proof of (ii)$``$(iii) and (iii)$``$(i) given in  is applicable to an arbitrary convex grid, as it, in essense, does not depend on the shape of the convex region $``$ spanned by $`G`$. Roughly speaking, the proof of (ii)$``$(iii) relies on a local transformation of a puzzle $`\mathrm{\Pi }`$ having a gentle circuit $`C`$. It creates another puzzle with the same boundary by re-arranging $`\mathrm{\Pi }`$ only within the 1-neighbourhood of $`C`$ (being the union of little triangles and rhombi sharing common edges with $`C`$). The proof of (iii)$``$(i) uses the function on the tp- and pn-edges whose value on an edge $`e`$ is the number of all maximal gentle paths with the first edge $`e`$. When $`\mathrm{\Pi }`$ has no gentle circuits, this function (regardless of the shape of $``$) is easily transformed into a concave cocirculation $`h_0`$ in $`G`$ for which the tandem inequality is strict on each little rhombus separated by a tp- or pn-edge. Using $`h_0`$, it is routine to construct $`|E_0(G)|2`$ concave cocirculations whose borders are linearly independent and orthogonal to the border of $`𝒦_\mathrm{\Pi }`$.) We omit details of the proof here.

It is not difficult to check that any puzzle $`\mathrm{\Pi }`$ with $`=\mathrm{}`$ and $`|𝒫|=1`$ is facet-determining as well (such a puzzle can arise when $``$ has $`4`$ sides). When $`=\mathrm{}`$ and $`|𝒫|2`$, $`\mathrm{\Pi }`$ is already not facet-determining as it is the union of two disjoint puzzles.

Third, by a result of Knutson and Tao  on integral honeycombs, a feasible integer-valued function $`\sigma `$ on the outer edges of a 3-side grid $`G`$ is extendable to an integer concave cocirculation. In a forthcoming paper  we show that this is generalized to a convex grid $`G`$ and, moreover, a sharper property takes place: a concave cocirculation $`h`$ in a convex grid $`G`$ can be turned into an integer concave cocirculation preserving the values of $`h`$ on all outer edges $`e`$ with $`h(e)`$ and on the edges of all little triangles where $`h`$ is integral for each of the three edges.

Acknowledgement. I am thankful to Vladimir Danilov and Gleb Koshevoy for many stimulating discussions on discrete concave functions and related topics.