Parabolic Tamari Lattices in Linear Type B Fang, Wenjie; Mühle, Henri; Novelli, Jean-Christophe
The Electronic journal of combinatorics,
03/2024, Letnik:
31, Številka:
1
Journal Article
Recenzirano
We study parabolic aligned elements associated with the type-$B$ Coxeter group and the so-called linear Coxeter element. These elements were introduced algebraically in (Mühle and Williams, 2019) for ...parabolic quotients of finite Coxeter groups and were characterized by a certain forcing condition on inversions. We focus on the type-$B$ case and give a combinatorial model for these elements in terms of pattern avoidance. Moreover, we describe an equivalence relation on parabolic quotients of the type-$B$ Coxeter group whose equivalence classes are indexed by the aligned elements. We prove that this equivalence relation extends to a congruence relation for the weak order. The resulting quotient lattice is the type-$B$ analogue of the parabolic Tamari lattice introduced for type $A$ in (Mühle and Williams, 2019).
Given a mixed hypergraph $\mathcal{F}=(V,\mathcal{A}\cup \mathcal{E})$, a non-negative integer $k$ and functions $f,g:V\rightarrow \mathbb{Z}_{\geq 0}$, a packing of $k$ spanning mixed ...hyperarborescences of $\mathcal{F}$ is called $(k,f,g)$-flexible if every $v \in V$ is the root of at least $f(v)$ and at most $g(v)$ of the mixed hyperarborescences. We give a characterization of the mixed hypergraphs admitting such packings. This generalizes results of Frank and, more recently, Gao and Yang. Our approach is based on matroid intersection, generalizing a construction of Edmonds. We also obtain an algorithm for finding a minimum weight solution to the problem mentioned above.
In this paper, we first prove that a Rota-Baxter family algebra indexed by a semigroup induces an ordinary Rota-Baxter algebra structure on the tensor product with the semigroup algebra. We show that ...the same phenomenon arises for dendriform and tridendriform family algebras. Then we construct free dendriform family algebras in terms of typed decorated planar binary trees. Finally, we generalize typed decorated rooted trees to typed valently decorated Schröder trees and use them to construct free tridendriform family algebras.
Domination in Kn\"odel Graphs Racicot, Jesse; Rosso, Giovanni
Discrete mathematics and theoretical computer science,
05/2022, Letnik:
24, no. 1, Številka:
Graph Theory
Journal Article
Recenzirano
Odprti dostop
Given a graph and an integer $k$, it is an NP-complete problem to decide
whether there is a dominating set of size at most $k$. In this paper we study
this problem for the Kn\"odel Graph on $n$ ...vertices using elementary number
theory techniques. In particular, we show an explicit upper bound for the
domination number of the Kn\"odel Graph on $n$ vertices any time that we can
find a prime number $p$ dividing $n$ for which $2$ is a primitive root.
On the genera of polyhedral embeddings of cubic graph Brinkmann, Gunnar; Tucker, Thomas; Van Cleemput, Nico
Discrete mathematics and theoretical computer science,
11/2021, Letnik:
23, no. 3, Številka:
Graph Theory
Journal Article
Recenzirano
Odprti dostop
In this article we present theoretical and computational results on the
existence of polyhedral embeddings of graphs. The emphasis is on cubic graphs.
We also describe an efficient algorithm to ...compute all polyhedral embeddings of
a given cubic graph and constructions for cubic graphs with some special
properties of their polyhedral embeddings. Some key results are that even cubic
graphs with a polyhedral embedding on the torus can also have polyhedral
embeddings in arbitrarily high genus, in fact in a genus {\em close} to the
theoretical maximum for that number of vertices, and that there is no bound on
the number of genera in which a cubic graph can have a polyhedral embedding.
While these results suggest a large variety of polyhedral embeddings,
computations for up to 28 vertices suggest that by far most of the cubic graphs
do not have a polyhedral embedding in any genus and that the ratio of these
graphs is increasing with the number of vertices.
We study the transients of matrices in max-plus algebra. Our approach is based on the weak CSR expansion. Using this expansion, the transient can be expressed by $\max\{T_1,T_2\}$, where $T_1$ is the ...weak CSR threshold and $T_2$ is the time after which the purely pseudoperiodic CSR terms start to dominate in the expansion. Various bounds have been derived for $T_1$ and $T_2$, naturally leading to the question which matrices, if any, attain these bounds. In the present paper we characterize the matrices attaining two particular bounds on $T_1$, which are generalizations of the bounds of Wielandt and Dulmage-Mendelsohn on the indices of non-weighted digraphs. This also leads to a characterization of tightness for the same bounds on the transients of critical rows and columns. The characterizations themselves are generalizations of those for the non-weighted case.
A set of integers S⊂N is an α–strong Sidon set if the pairwise sums of its elements are far apart by a certain measure depending on α, more specifically if|(x+w)−(y+z)|≥max{xα,yα,zα,wα} for every ...x,y,z,w∈S satisfying max{x,w}≠max{y,z}. We obtain a new lower bound for the growth of α–strong infinite Sidon sets when 0≤α<1. We also further extend that notion in a natural way by obtaining the first non-trivial bound for α–strong infinite Bh sets. In both cases, we study the implications of these bounds for the density of, respectively, the largest Sidon or Bh set contained in a random infinite subset of N. Our theorems improve on previous results by Kohayakawa, Lee, Moreira and Rödl.
This thesis is concerned with the representation theory of the symmetric groups and related algebras, in particular the combinatorics underlying the representations of the Khovanov-Lauda-Rouquier ...(KLR) algebras. These algebras are of particular interest since they possess cyclotomic quotients which were shown by Brundan and Kleshchev to be isomorphic to the Ariki-Koike algebras. The Ariki-Koike algebras generalise Iwahori-Hecke algebras of the symmetric group, and so in turn generalise the symmetric groups themselves. Via this isomorphism, we are able to utilise the grading of the KLR algebras in the setting of the Ariki-Koike algebras, and thus study graded Specht modules. Specht modules of the KLR algebras admit a definition which lends them well to diagrammatic combinatorics. We shall first develop an arsenal of combinatorial lemmas related to the manipulation of braid diagrams. Then, we will use these to demonstrate the existence of explicit homomorphisms between Specht modules of certain KLR algebras, related to moving particular shapes between the multipar-titions associated to these Specht modules. We shall begin by considering moving single nodes between bipartitions, but eventually consider moving multiple large connected shapes of nodes between components of multipartitions in higher levels. We will then use the obtained homomorphisms to investigate the homomor-phism spaces between Specht modules that lie in core blocks of level 2 KLR algebras whose base tuples consists entirely of zeroes. We will completely describe the dominated homomorphism spaces between Specht modules in these blocks. In particular, when the quantum characteristic is not 2 and the multicharge entries are distinct, we will completely describe all homomorphism spaces between Specht modules in these blocks. We will also give a conjecture about replacing the base tuple with any arbitrary base tuple.
PDF
![Domination in Kn\"odel Graphs](http://api.summon.serialssolutions.com/2.0.0/image/issn/XR4PS5YY4K/1365-8050/small "Domination in Kn\\"odel Graphs")
