A bijection is given between the set of directed column-convex polyominoes on triangular and honeycomb lattices of area n and some families of restricted compositions. This is an analogous result to ...one given by Deutsch and Prodinger for polyominoes over square lattices. As a byproduct, we deduce new close forms for the number of hexagonal and triangular directed column-convex polyominoes of area n with k columns.
We introduce several classes of polytopes contained in 0, 1 n and cut out by inequalities involving sums of consecutive coordinates , extending a construction by Stanley. We show that the normalized ...volumes of these polytopes enumerate the extensions to total cyclic orders of certains classes of partial cyclic orders. We also provide a combinatorial interpretation of the Ehrhart h *-polynomials of some of these polytopes in terms of descents of total cyclic orders. The Euler numbers, the Eulerian numbers and the Narayana numbers appear as special cases.
Antifactors of regular bipartite graphs Hongliang Lu; Wei Wang; Juan Yan
Discrete mathematics and theoretical computer science,
06/2020, Letnik:
22 no. 1, Številka:
Graph Theory
Journal Article
Recenzirano
Odprti dostop
Let $G=(X,Y;E)$ be a bipartite graph, where $X$ and $Y$ are color classes and $E$ is the set of edges of $G$. Lov\'asz and Plummer \cite{LoPl86} asked whether one can decide in polynomial time that a ...given bipartite graph $G=(X,Y; E)$ admits a 1-anti-factor, that is subset $F$ of $E$ such that $d_F(v)=1$ for all $v\in X$ and $d_F(v)\neq 1$ for all $v\in Y$. Cornu\'ejols \cite{CHP} answered this question in the affirmative. Yu and Liu \cite{YL09} asked whether, for a given integer $k\geq 3$, every $k$-regular bipartite graph contains a 1-anti-factor. This paper answers this question in the affirmative.
Graph partitioning and graph clustering are ubiquitous subtasks in many applications where graphs play an important role. Generally speaking, both techniques aim at the identification of vertex ...subsets with many internal and few external edges. To name only a few, problems addressed by graph partitioning and graph clustering algorithms are: li>What are the communities within an (online) social network? How do I speed up a numerical simulation by mapping it efficiently onto a parallel computer? How must components be organised on a computer chip such that they can communicate efficiently with each other? What are the segments of a digital image? Which functions are certain genes (most likely) responsible for? The 10th DIMACS Implementation Challenge Workshop was devoted to determining realistic performance of algorithms where worst case analysis is overly pessimistic and probabilistic models are too unrealistic. Articles in the volume describe and analyse various experimental data with the goal of getting insight into realistic algorithm performance in situations where analysis fails. This book is published in cooperation with the Center for Discrete Mathematics and Theoretical Computer Science.
This thesis concerns the combinatorics and algebra of set systems. Let V be a set of size n. We define a vector space Mn with basis the power set of V. This space decomposes into a direct sum of ...eigenspaces under certain incidence maps. Any collection of k-sets S embeds naturally into this space, and so decomposes as a sum of eigenvectors. The main objects of study are the lengths of these eigenvectors, which we call the shape of S. We prove that the shape of S is a linear transformation of the inner distribution, and show that t-designs have a specific shape. We give some classifications of the shape of collections of k-sets for small k. Given a permutation group G, we define the subspace MG of Mn of all vectors fixed by G. We show that this space is spanned by the G-orbits of the power set of V and as a consequence of this, prove the Livingstone-Wagner Theorem. We then give some results about groups that have the same number of orbits on 2-sets and 3-sets.
The principal concern of this document is to develop and expose methodology for enumerating idempotents in certain semigroups of diagrams in the sense of 76. These semigroups are known to be ...significant in the representation theory of associated algebras. In particular these algebras are shown in many cases to be semisimple, giving certain idempotents (and in particular those of the monoids of concern) a prominent role in understanding certain features of the representation theory in this situation. The results developed here are mostly theoretical in nature. We propose two viewpoints leading to some combinatorial understanding of the idempotents in the Motzkin (respectively Jones and partial Jones) monoid. In the first instance, we construct a cell complex, whose connected components partition the set of all idempotents into small, manageable chunks that can be analysed uniformly starting from those of particularly low rank. The structure of this complex captures some intricate combinatorics in the semigroup in a fairly simple, uniform way, and reduces our problem to finding and characterising idempotents of particularly low rank. The latter viewpoint takes us closer to pure combinatorics; a family of parameters attached to the elements of the monoids in question. These are examined in the context of ordinary generating functions, counting the elements with various parameter profiles. In particular, important algebraic features of Motzkin pictures, such as degree, rank, idempotency, and membership in the Jones and partial Jones monoids, can be tested against parameter profiles, reducing the problem of understanding all three to that of a parametric underiii iv standing of only the Motzkin monoid. We can then amalgamate these families of techniques into the development of fast linear-space algorithms for counting elements of various parameter profiles by examining certain "convex" elements. In particular, the general problem of enumeration by parameter profile is reduced greatly to enumerating convex elements by parameter profile. As a corollary to this study of convexity, we observe that the sequence of numbers of idempotents (in each semigroup) of some fixed rank-deficiency d = (n − r) is equal (apart from the first couple of values) to some polynomial of degree d; for particularly low rank-deficiency, we calculate these polynomials. Finally, we can show that the problem of understanding these idempotents in this way reduces to the classical open problem in combinatorics of counting meanders, witnessing the fact that significant progress on the former problem would necessitate some development of a better understanding of the latter.
In the past years, techniques from different areas of mathematics have been successfully applied in extremal combinatorics problems. Examples include applications of number theory, geometry and group ...theory in Ramsey theory and analytical methods to different problems in extremal combinatorics. By providing an analytic point of view of many discrete problems, the theory of combinatorial limits led to substantial results in many areas of mathematics and computer science, in particular in extremal combinatorics. In this thesis, we explore the connection between combinatorial limits and extremal combinatorics. In particular, we prove that extremal graph theory problemsmay have unique optimal solutions with arbitrarily complex structure, study a property closely related to Sidorenko's conjecture, one of the most important open problems in extremal combinatorics, and prove a 30-year old conjecture of Gyori and Tuza regarding decomposing the edges of a graph into triangles and edges.
We generalize the brick polytope of V. Pilaud and F. Santos to spherical subword complexes for finite Coxeter groups. This construction provides polytopal realizations for a certain class of subword ...complexes containing all cluster complexes of finite types. For the latter, the brick polytopes turn out to coincide with the known realizations of generalized associahedra, thus opening new perspectives on these constructions. This new approach yields in particular the vertex description of generalized associahedra, a Minkowski sum decomposition into Coxeter matroid polytopes, and a combinatorial description of the exchange matrix of any cluster in a finite type cluster algebra.
We consider uniform random permutations in classes having a finite combinatorial specification for the substitution decomposition. These classes include (but are not limited to) all permutation ...classes with a finite number of simple permutations. Our goal is to study their limiting behavior in the sense of permutons.
The limit depends on the structure of the specification restricted to families with the largest growth rate. When it is strongly connected, two cases occur. If the associated system of equations is linear, the limiting permuton is a deterministic X-shape. Otherwise, the limiting permuton is the Brownian separable permuton, a random object that already appeared as the limit of most substitution-closed permutation classes, among which the separable permutations. Moreover these results can be combined to study some non strongly connected cases.
To prove our result, we use a characterization of the convergence of random permutons by the convergence of random subpermutations. Key steps are the combinatorial study, via substitution trees, of families of permutations with marked elements inducing a given pattern, and the singularity analysis of the corresponding generating functions.
For a fixed integer k, we consider the set of noncrossing partitions, where both the block sizes and the difference between adjacent elements in a block is 1 mod k. We show that these k-indivisible ...noncrossing partitions can be recovered in the setting of subgroups of the symmetric group generated by (k+1)-cycles, and that the poset of k-indivisible noncrossing partitions under refinement order has many beautiful enumerative and structural properties. We encounter k-parking functions and some special Cambrian lattices on the way, and show that a special class of lattice paths constitutes a nonnesting analogue.
PDF
