Symmetry classes of spanning trees of Aztec diamonds and perfect matchings of odd squares with a unit hole

We say that two graphs are similar if their adjacency matrices are similar matrices. We show that the square grid G _n of order n is similar to the disjoint union of two copies of the quartered Aztec diamond QAD _n−1 of order n−1 with the path P _n ⁽²⁾ on n vertices having edge weights equal to 2. Our proof is based on an explicit change of basis in the vector space on which the adjacency matrix acts. The arguments verifying that this change of basis works are combinatorial. It follows in particular that the characteristic polynomials of the above graphs satisfy the equality P(G _n )=P(P _n ⁽²⁾)[P(QAD _n−1)]². On the one hand, this provides a combinatorial explanation for the “squarishness” of the characteristic polynomial of the square grid—i.e., that it is a perfect square, up to a factor of relatively small degree. On the other hand, as formulas for the characteristic polynomials of the path and the square grid are well known, our equality determines the characteristic polynomial of the quartered Aztec diamond. In turn, the latter allows computing the number of spanning trees of quartered Aztec diamonds. We present and analyze three more families of graphs that share the above described “linear squarishness” property of square grids: odd Aztec diamonds, mixed Aztec diamonds, and Aztec pillowcases—graphs obtained from two copies of an Aztec diamond by identifying the corresponding vertices on their convex hulls. We apply the above results to enumerate all the symmetry classes of spanning trees of the even Aztec diamonds, and all the symmetry classes not involving rotations of the spanning trees of odd and mixed Aztec diamonds. We also enumerate all but the base case of the symmetry classes of perfect matchings of odd square grids with the central vertex removed. In addition, we obtain a product formula for the number of spanning trees of Aztec pillowcases. Research supported in part by NSF grant DMS-0500616.     

On complete intersection toric ideals of graphs

We study the graphs G for which their toric ideals I _G are complete intersections. In particular, we prove that for a connected graph G such that I _G is a complete intersection all of its blocks are bipartite except for at most two. We prove that toric ideals of graphs which are complete intersections are circuit ideals. In this case, the generators of the toric ideal correspond to even cycles of G except of at most one generator, which corresponds to two edge disjoint odd cycles joint at a vertex or with a path. We prove that the blocks of these graphs satisfy the odd cycle condition. Finally, we characterize all complete intersection toric ideals of graphs which are normal.     

On line perfect graphs

Line-perfect graphs have been defined by L.E. Trotter as graphs whose line-graphs are perfect. They are characterized by the property of having no elementary odd cycle of size larger than 3. L.E. Trotter showed constructively that the maximum cardinality of a set of mutually non-adjacent edges (matching) is equal to the minimum cardinality of a collection of sets of mutually adjacent edges which cover all edges.The purpose of this note is to give an algorithmic proof that the chromatic index of these graphs is equal to the maximum cardinality of a set of mutually adjacent edges.     

Characterizations of postman sets

Using results by McKee and Woodall on binary matroids, we show that the set of postman sets has odd cardinality, generalizing a result by Toida on the cardinality of cycles in Eulerian graphs. We study the relationship between T-joins and blocks of the underlying graph, obtaining a decomposition of postman sets in terms of blocks. We conclude by giving several characterizations of T-joins which are postman sets.     

Characterizations of Postman Sets

Using results by McKee and Woodall on binary matroids, we prove that the set of postman sets has odd cardinality, generalizing a result by Toida on the cardinality of cycles in Eulerian graphs. We study the relationship between T-joins and blocks of the underlying graph, obtaining a decom- position of postman sets in terms of blocks. We conclude by giving several characterizations of T-joins which are postman sets and commenting on practical issues.     

Symplectic Spaces And Ear-Decomposition Of Matroids

Matroids admitting an odd ear-decomposition can be viewed as natural generalizations of factor-critical graphs. We prove that a matroid representable over a field of characteristic 2 admits an odd ear-decomposition if and only if it can be represented by some space on which the induced scalar product is a non-degenerate symplectic form. We also show that, for a matroid representable over a field of characteristic 2, the independent sets whose contraction admits an odd ear-decomposition form the family of feasible sets of a representable Δ-matroid.     

More Jonsson Algebras

 We prove that on many inaccessible cardinals there is a Jonsson algebra, so e.g. the first regular Jonsson cardinal λ is λ × ω-Mahlo. We give further restrictions on successor of singulars which are Jonsson cardinals. E.g. there is a Jonsson algebra of cardinality . Lastly, we give further information on guessing of clubs. Received: 10 March 1992 / First revised version: 11 August 1997 / Second revised version: 12 September 2000 / Published online: 5 November 2002     

Completely symmetric configurations for <Emphasis Type="Italic">σ</Emphasis>-games on grid graphs

The paper deals with σ-games on grid graphs (in dimension 2 and more) and conditions under which any completely symmetric configuration of lit vertices can be reached – in particular the completely lit configuration – when starting with the all-unlit configuration. The answer is complete in dimension 2. In dimension ≥3, the answer is complete for the σ ⁺-game, and for the σ ⁻-game if at least one of the sizes is even. The case σ ⁻, dimension ≥3 and all sizes odd remains open.     

A superadditivity and submultiplicativity property for cardinalities of sumsets

For finite sets of integers A ₁,…,A _n we study the cardinality of the n-fold sumset A ₁+…+ A _n compared to those of (n−1)-fold sumsets A ₁+…+A _i−1+A _i+1+…+A _n . We prove a superadditivity and a submultiplicativity property for these quantities. We also examine the case when the addition of elements is restricted to an addition graph between the sets.     

Classification of topologies on finite sets using graphs

With the use of directed graphs, we study topologies on finite sets. On this basis, we propose a new classification of these topologies. Some properties of T ₀-topologies on finite sets are proved. In particular, we prove the existence, in T ₀-topologies, of open sets containing any number of elements that does not exceed the cardinality of the set itself. Translated from Ukrains'kyi Matematychnyi Zhurnal, Vol. 60, No. 7, pp. 992–996, July, 2008.     

Cycles through specified vertices of a graph

We prove that ifS is a set ofk−1 vertices in ak-connected graphG, then the cycles throughS generate the cycle space ofG. Moreover, whenk≧3, each cycle ofG can be expressed as the sum of an odd number of cycles throughS. On the other hand, ifS is a set ofk vertices, these conclusions do not necessarily hold, and we characterize the exceptional cases. As corollaries, we establish the existence of odd and even cycles through specified vertices and deduce the existence of long odd and even cycles in graphs of high connectivity.     

On the geometry of complete intersection toric varieties

In this paper we give a geometric characterization of the cones of toric varieties that are complete intersections. In particular, we prove that the class of complete intersection cones is the smallest class of cones which is closed under direct sum and contains all simplex cones. Further, we show that the number of the extreme rays of such a cone, which is less than or equal to 2n − 2, is exactly 2n − 2 if and only if the cone is a bipyramidal cone, where n > 1 is the dimension of the cone. Finally, we characterize all toric varieties whose associated cones are complete intersection cones. Received: 4 July 2005     

On the smallest sets blocking simple perfect matchings in a convex geometric graph

In this paper we present a complete characterization of the smallest sets which block all the simple perfect matchings in a complete convex geometric graph on 2m vertices. In particular, we show that all these sets are caterpillar graphs with a special structure, and that their total number is m·2 ^m−1.     

Welschinger invariants of toric Del Pezzo surfaces with nonstandard real structures

The Welschinger invariants of real rational algebraic surfaces are natural analogs of the Gromov-Witten invariants, and they estimate from below the number of real rational curves passing through prescribed configurations of points. We establish a tropical formula for the Welschinger invariants of four toric Del Pezzo surfaces equipped with a nonstandard real structure. Such a formula for real toric Del Pezzo surfaces with a standard real structure (i.e., naturally compatible with the toric structure) was established by Mikhalkin and the author. As a consequence we prove that for any real ample divisor D on a surface Σ under consideration, through any generic configuration of c ₁(Σ)D − 1 generic real points, there passes a real rational curve belonging to the linear system |D|. To Vladimir Igorevich Arnold on the occasion of his 70th birthday     

Even and odd holes in cap‐free graphs

It is an old problem in graph theory to test whether a graph contains a chordless cycle of length greater than three (hole) with a specific parity (even, odd). Studying the structure of graphs without odd holes has obvious implications for Berge's strong perfect graph conjecture that states that a graph G is perfect if and only if neither G nor its complement contain an odd hole. Markossian, Gasparian, and Reed have proven that if neither G nor its complement contain an even hole, then G is β‐perfect. In this article, we extend the problem of testing whether G(V, E) contains a hole of a given parity to the case where each edge of G has a label odd or even. A subset of E is odd (resp. even) if it contains an odd (resp. even) number of odd edges. Graphs for which there exists a signing (i.e., a partition of E into odd and even edges) that makes every triangle odd and every hole even are called even‐signable. Graphs that can be signed so that every triangle is odd and every triangle is odd and every hole is odd are called odd‐signable. We derive from a theorem due to Truemper co‐NP characterizations of even‐signable and odd‐signable graphs. A graph is strongly even‐signable if it can be signed so that every cycle of length ≥ 4 with at most one chord is even and every triangle is odd. Clearly a strongly even‐signable graph is even‐signable as well. Graphs that can be signed so that cycles of length four with one chord are even and all other cycles with at most one chord are odd are called strongly odd‐signable. Every strongly odd‐signable graph is odd‐signable. We give co‐NP characterizations for both strongly even‐signable and strongly odd‐signable graphs. A cap is a hole together with a node, which is adjacent to exactly two adjacent nodes on the hole. We derive a decomposition theorem for graphs that contain no cap as induced subgraph (cap‐free graphs). Our theorem is analogous to the decomposition theorem of Burlet and Fonlupt for Meyniel graphs, a well‐studied subclass of cap‐free graphs. If a graph is strongly even‐signable or strongly odd‐signable, then it is cap‐free. In fact, strongly even‐signable graphs are those cap‐free graphs that are even‐signable. From our decomposition theorem, we derive decomposition results for strongly odd‐signable and strongly even‐signable graphs. These results lead to polynomial recognition algorithms for testing whether a graph belongs to one of these classes. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 289–308, 1999     

Paired-Domination in Subdivided Star-Free Graphs

A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired-domination number of G, denoted by γ _pr(G), is the minimum cardinality of a paired-dominating set of G. In [Dorbec P, Gravier S, Henning MA, J Comb Optim 14(1):1–7, 2007], the authors gave tight bounds for paired-dominating sets of generalized claw-free graphs. Yet, the critical cases are not claws but subdivided stars. We here give a bound for graphs containing no induced subdivided stars, depending on the size of the star.     

Toric Kempf-Ness sets

In the theory of algebraic group actions on affine varieties, the concept of a Kempf-Ness set is used to replace the categorical quotient by the quotient with respect to a maximal compact subgroup. Using recent achievements of “toric topology,” we show that an appropriate notion of a Kempf-Ness set exists for a class of algebraic torus actions on quasiaffine varieties (coordinate subspace arrangement complements) arising in the Batyrev-Cox “geometric invariant theory” approach to toric varieties. We proceed by studying the cohomology of these “toric” Kempf-Ness sets. In the case of projective nonsingular toric varieties the Kempf-Ness sets can be described as complete intersections of real quadrics in a complex space. Published in Russian in Trudy Matematicheskogo Instituta imeni V.A. Steklova, 2008, Vol. 263, pp. 159–172.     

Upper bound of the third edge-connectivity of graphs

Let G be a simple connected graph of order n≥6. The third edge-connectivity of G is defined as the minimum cardinality over all the sets of edges, if any, whose deletion disconnects G and every component of the resulting graph has at least 3 vertices. In this paper, we first characterize those graphs whose third-edge connectivity is well defined, then establish the tight upper bound for the third edge-connectivity.     

Dirac’s Theorem on Simplicial Matroids

We introduce the notion of k-hyperclique complexes, i.e., the largest simplicial complexes on the set [n] with a fixed k-skeleton. These simplicial complexes are a higher-dimensional analogue of clique (or flag) complexes (case k = 2) and they are a rich new class of simplicial complexes. We show that Dirac’s theorem on chordal graphs has a higher-dimensional analogue in which graphs and clique complexes get replaced, respectively, by simplicial matroids and k-hyperclique complexes. We prove also a higher-dimensional analogue of Stanley’s reformulation of Dirac’s theorem on chordal graphs.