148 results on '"Mathematics - Combinatorics"'
Search Results
2. The saturation number of monomial ideals
- Author
-
Reza Abdolmaleki and Ali Akbar Yazdan Pour
- Subjects
Algebra and Number Theory ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Primary: 13F20, Secondary: 05E40 ,Mathematics - Commutative Algebra ,Commutative Algebra (math.AC) - Abstract
Let $S=\mathbb{K}[x_1,\ldots, x_n]$ be the polynomial ring over a field $\mathbb{K}$ and $\mathfrak{m}= (x_1, \ldots, x_n)$ be the irredundant maximal ideal of $S$. For an ideal $I \subset S$, let $\mathrm{sat}(I)$ be the minimum number $k$ for which $I \colon \mathfrak{m}^k = I \colon \mathfrak{m}^{k+1}$. In this paper, we compute the saturation number of irreducible monomial ideals and their powers. We apply this result to find the saturation number of the ordinary powers and symbolic powers of some families of monomial ideals in terms of the saturation number of irreducible components appearing in an irreducible decomposition of these ideals. Moreover, we give an explicit formula for the saturation number of monomial ideals in two variables.
- Published
- 2023
3. A Model for Birdwatching and other Chronological Sampling Activities
- Author
-
Jesús A. De Loera, Edgar Jaramillo-Rodriguez, Deborah Oliveros, and Antonio J. Torres
- Subjects
General Mathematics ,Probability (math.PR) ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Mathematics - Probability - Abstract
In many real life situations one has $m$ types of random events happening in chronological order within a time interval and one wishes to predict various milestones about these events or their subsets. An example is birdwatching. Suppose we can observe up to $m$ different types of birds during a season. At any moment a bird of type $i$ is observed with some probability. There are many natural questions a birdwatcher may have: how many observations should one expect to perform before recording all types of birds? Is there a time interval where the researcher is most likely to observe all species? Or, what is the likelihood that several species of birds will be observed at overlapping time intervals? Our paper answers these questions using a new model based on random interval graphs. This model is a natural follow up to the famous coupon collector's problem., Comment: 26 pages, 8 figures. To be published in The American Mathematical Monthly
- Published
- 2023
4. An Upper Bound on the Size of Sidon Sets
- Author
-
Balogh, J��zsef, F��redi, Zolt��n, and Roy, Souktik
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,Mathematics - Number Theory ,General Mathematics ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Number Theory (math.NT) ,Computer Science - Discrete Mathematics - Abstract
In this entry point into the subject, combining two elementary proofs, we decrease the gap between the upper and lower bounds by $0.2\%$ in a classical combinatorial number theory problem. We show that the maximum size of a Sidon set of $\{ 1, 2, \ldots, n\}$ is at most $\sqrt{n}+ 0.998n^{1/4}$ for sufficiently large $n$., Minor edits from previous version
- Published
- 2023
5. A parametric congruence motivated by Orr's identity
- Author
-
Chen Wang and Zhi-Wei Sun
- Subjects
Algebra and Number Theory ,Mathematics - Number Theory ,Applied Mathematics ,FOS: Mathematics ,Mathematics - Combinatorics ,Number Theory (math.NT) ,Combinatorics (math.CO) ,11A07, 33C20, 11B65, 05A10 ,Analysis - Abstract
For any $m,n\in\mathbb{N}=\{0,1,2\ldots\}$, the truncated hypergeometric series ${}_{m+1}F_m$ is defined by $$ {}_{m+1}F_m\bigg[\begin{matrix}x_0&x_1&\ldots&x_m\\ &y_1&\ldots&y_m\end{matrix}\bigg|z\bigg]_n=\sum_{k=0}^n\frac{(x_0)_k(x_1)_k\cdots(x_m)_k}{(y_1)_k\cdots(y_m)_k}\cdot\frac{z^k}{k!}, $$ where $(x)_k=x(x+1)\cdots(x+k-1)$ is the Pochhammer symbol. Let $p$ be an odd prime. For $α,z\in\mathbb{Z}_p$ with $\langle -α\rangle_p\equiv0\pmod{2}$, where $\langle x\rangle_p$ denotes the least nonnegative residue of $x$ modulo $p$ for any $x\in\mathbb{Z}_p$, we mainly prove the following congruence motivated by Orr's identity: $$ {}_2F_1\bigg[\begin{matrix}\frac12α&\frac32-\frac12α\\ &1\end{matrix}\bigg|z\bigg]_{p-1}{}_2F_1\bigg[\begin{matrix}\frac12α&\frac12-\frac12α\\ &1\end{matrix}\bigg|z\bigg]_{p-1}\equiv{}_3F_2\bigg[\begin{matrix}α&2-α&\frac12\\ &1&1\end{matrix}\bigg|z\bigg]_{p-1}\pmod{p^2}. $$ As a corollary, for any positive integer $b$ with $p\equiv\pm1\pmod{b}$ and $\langle -1/b\rangle_p\equiv0\pmod{2}$, we deduce that $$ \sum_{k=0}^{p-1}(b^2k+b-1)\frac{\binom{2k}{k}}{4^k}\binom{-1/b}{k}\binom{1/b-1}{k}\equiv0\pmod{p^2}. $$ This confirms a conjectural congruence of the second author., 8 pages, accepted by Journal of Difference Equations and Applications
- Published
- 2023
6. Chebyshev Polynomials, Sliding Columns, and the k-Step Fibonacci Numbers
- Author
-
Dresden, Greg
- Subjects
Mathematics - Number Theory ,General Mathematics ,Mathematics::History and Overview ,FOS: Mathematics ,Mathematics - Combinatorics ,11B39 ,Number Theory (math.NT) ,Combinatorics (math.CO) - Abstract
We give a direct and intuitive proof (via sliding some columns up and down) of the following interesting fact: if we write out the Chebyshev polynomials in a chart and take the sums of coefficients along certain diagonals, we obtain the Fibonaccis, the Tribonaccis, the Tetranaccis, and so on., Comment: 5 pages. To appear in Mathematics Magazine, 2022
- Published
- 2023
7. Generalized Paley graphs equienergetic with their complements
- Author
-
Ricardo Alberto Podestá and Denis E. Videla
- Subjects
Algebra and Number Theory ,Astrophysics::High Energy Astrophysical Phenomena ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,05C50 - Abstract
We consider generalized Paley graphs $\Gamma(k,q)$, generalized Paley sum graphs $\Gamma^+(k,q)$, and their corresponding complements $\bar \Gamma(k,q)$ and $\bar \Gamma^+(k,q)$, for $k=3,4$. Denote by $\Gamma = \Gamma^*(k,q)$ either $\Gamma(k,q)$ or $\Gamma^+(k,q)$. We compute the spectra of $\Gamma(3,q)$ and $\Gamma(4,q)$ and from them we obtain the spectra of $\Gamma^+(3,q)$ and $\Gamma^+(4,q)$ also. Then we show that, in the non-semiprimitive case, the spectrum of $\Gamma(3,p^{3\ell})$ and $\Gamma(4,p^{4\ell})$ with $p$ prime can be recursively obtained, under certain arithmetic conditions, from the spectrum of the graphs $\Gamma(3,p)$ and $\Gamma(4,p)$ for any $\ell \in \mathbb{N}$, respectively. Using the spectra of these graphs we give necessary and sufficient conditions on the spectrum of $\Gamma^*(k,q)$ such that $\Gamma^*(k,q)$ and $\bar \Gamma^*(k,q)$ are equienergetic for $k=3,4$. In a previous work we have classified all bipartite regular graphs $\Gamma_{bip}$ and all strongly regular graphs $\Gamma_{srg}$ which are complementary equienergetic, i.e.\@ $\{\Gamma_{bip}, \bar{\Gamma}_{bip}\}$ and $\{\Gamma_{srg}, \bar{\Gamma}_{srg}\}$ are equienergetic pairs of graphs. Here we construct infinite pairs of equienergetic non-isospectral regular graphs $\{\Gamma, \bar \Gamma\}$ which are neither bipartite nor strongly regular., Comment: 22 pages
- Published
- 2022
8. Perturbing eigenvalues of nonnegative centrosymmetric matrices
- Author
-
Díaz, Roberto C., Julio, Ana I., and Linares, Yankis R.
- Subjects
Algebra and Number Theory ,Computer Science::Computational Engineering, Finance, and Science ,FOS: Mathematics ,Mathematics - Combinatorics ,Physics::Optics ,Combinatorics (math.CO) - Abstract
An $n\times n$ matrix $C$ is said to be {\it centrosymmetric} if it satisfies the relation $JCJ=C$, where $J$ is the $n\times n$ counteridentity matrix. Centrosymmetric matrices have a rich eigenstructure that has been studied extensively in the literature. Many results for centrosymmetric matrices have been generalized to wider classes of matrices that arise in a wide variety of disciplines. In this paper, we obtain interesting spectral properties for nonnegative centrosymmetric matrices. We show how to change one single eigenvalue, two or three eigenvalues of an $n\times n$ nonnegative centrosymmetric matrix without changing any of the remaining eigenvalues neither nonnegativity nor the centrosymmetric structure. Moreover, our results allow partially answer some known questions given by Guo [11] and by Guo and Guo [12]. Our proofs generate algorithmic procedures that allow to compute a solution matrix., Comment: 23 pages
- Published
- 2022
9. Total mixed domination in graphs
- Author
-
Kazemnejad, Farshad, Kazemi, Adel P., and Moradi, Somayeh
- Subjects
05C69 ,FOS: Mathematics ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Combinatorics (math.CO) - Abstract
For a graph $G=(V,E)$, we call a subset $ S\subseteq V \cup E$ a total mixed dominating set of $G$ if each element of $V \cup E$ is either adjacent or incident to an element of $S$, and the total mixed domination number $\gamma_{tm}(G)$ of $G$ is the minimum cardinality of a total mixed dominating set of $G$. In this paper, we initiate to study the total mixed domination number of a connected graph by giving some tight bounds in terms of some parameters such as order and total domination numbers of the graph and its line graph. Then we discuss on the relation between total mixed domination number of a graph and its diameter. Studing of this number in trees is our next work. Also we show that the total mixed domination number of a graph is equale to the total domination number of a graph which is obtained by the graph. Giving the total mixed domination numbers of some special graphs is our last work.
- Published
- 2022
10. Integral Recurrences from A to Z
- Author
-
Robert Dougherty-Bliss
- Subjects
Mathematics - History and Overview ,History and Overview (math.HO) ,General Mathematics ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,39-02 (Primary), 11-02 (Secondary) - Abstract
George Boros and Victor Moll's masterpiece "Irresistible Integrals" does well to include a suitably-titled appendix, "The Revolutionary WZ Method," which gives a brief overview of the celebrated Wilf--Zeilberger method of definite summation. Paradoxically, "Irresistible Integrals" does not contain the suitably-titled appendix, "The Revolutionary AZ Method," which would have been an excellent place to give a brief overview of the Almkvist--Zeilberger method of definite integration! This omission can be forgiven, but once realized it must be rectified. The remarkable AZ machinery deserves to be more widely known to the general public than it is. We will do our part by presenting a series of case studies that culminate in a -- fun but overkill -- integral-based proof that $e$ is irrational., Comment: 11 pages
- Published
- 2022
11. Perfect state transfer on semi-Cayley graphs over abelian groups
- Author
-
Arezoomand, Majid
- Subjects
Mathematics::Group Theory ,Algebra and Number Theory ,FOS: Mathematics ,Mathematics - Combinatorics ,Group Theory (math.GR) ,Combinatorics (math.CO) ,Mathematics - Group Theory - Abstract
In this paper, we consider the problem on the existence of perfect state transfer(PST for short) on semi-Cayley graphs over abelian groups (which are not necessarily regular), i.e on the graphs having semiregular and abelian subgroups of automorphisms with two orbits of equal size. We stablish a characterization of semi-Cayley graphs over abelian groups having PST. As a result, we give a characterization of Cayley graphs over groups with an abelian subgroup of index 2 having PST, which improves the earlier results on Cayley graphs over abelian groups, dihedral groups and dicyclic group and determines Cayley graphs over generalized dihedral groups and generalized dicyclic groups having PST.
- Published
- 2022
12. Sufficient spectral conditions for graphs being k-edge-Hamiltonian or k-Hamiltonian
- Author
-
Li, Yongtao and Peng, Yuejian
- Subjects
Mathematics - Spectral Theory ,Algebra and Number Theory ,FOS: Mathematics ,Mathematics - Combinatorics ,05C50, 15A18, 05C38 ,Combinatorics (math.CO) ,Spectral Theory (math.SP) - Abstract
A graph $G$ is $k$-edge-Hamiltonian if any collection of vertex-disjoint paths with at most $k$ edges altogether belong to a Hamiltonian cycle in $G$. A graph $G$ is $k$-Hamiltonian if for all $S\subseteq V(G)$ with $|S|\le k$, the subgraph induced by $V(G)\setminus S$ has a Hamiltonian cycle. These two concepts are classical extensions for the usual Hamiltonian graphs. In this paper, we present some spectral sufficient conditions for a graph to be $k$-edge-Hamiltonian and $k$-Hamiltonian in terms of the adjacency spectral radius as well as the signless Laplacian spectral radius. Our results could be viewed as slight extensions of the recent theorems proved by Li and Ning [Linear Multilinear Algebra 64 (2016)], Nikiforov [Czechoslovak Math. J. 66 (2016)] and Li, Liu and Peng [Linear Multilinear Algebra 66 (2018)]. Moreover, we shall prove a stability result for graphs being $k$-Hamiltonian, which could be regarded as a complement of two recent results of F\"{u}redi, Kostochka and Luo [Discrete Math. 340 (2017)] and [Discrete Math. 342 (2019)]., Comment: 21 pages, 1 figure. Any comments and suggestions are welcome. E-mail addresses: ytli0921@hnu.edu.cn (Yongtao Li), ypeng1@hnu.edu.cn (Yuejian Peng, corresponding author). Linear and Multilinear Algebra, 2022
- Published
- 2022
13. Guessing about Guessing: Practical Strategies for Card Guessing with Feedback
- Author
-
Diaconis, Persi, Graham, Ron, and Spiro, Sam
- Subjects
General Mathematics ,Probability (math.PR) ,FOS: Mathematics ,Mathematics - Combinatorics ,60C05 ,Combinatorics (math.CO) ,Mathematics - Probability - Abstract
In simple card games, cards are dealt one at a time and the player guesses each card sequentially. We study problems where feedback (e.g. correct/incorrect) is given after each guess. For decks with repeated values (as in blackjack where suits do not matter) the optimal strategy differs from the "greedy strategy" (of guessing a most likely card each round). Further, both optimal and greedy strategies are far too complicated for real time use by human players. Our main results show that simple heuristics perform close to optimal., Comment: 20 pages, minor typos corrected, to appear in the American Mathematical Monthly excluding Section 6
- Published
- 2022
14. Discrete Dynamical Systems From Real Valued Mutation
- Author
-
John Machacek and Nicholas Ovenhouse
- Subjects
General Mathematics ,FOS: Mathematics ,Mathematics - Combinatorics ,Dynamical Systems (math.DS) ,Combinatorics (math.CO) ,Mathematics - Dynamical Systems - Abstract
We introduce a family of discrete dynamical systems which includes, and generalizes, the mutation dynamics of rank two cluster algebras. These systems exhibit behavior associated with integrability, namely preservation of a symplectic form, and in the tropical case, the existence of a conserved quantity. We show in certain cases that the orbits are unbounded. The tropical dynamics are related to matrix mutation, from the theory of cluster algebras. We are able to show that in certain special cases, the tropical map is periodic. We also explain how our dynamics imply the asymptotic sign-coherence observed by Gekhtman and Nakanishi in the $2$-dimensional situation.
- Published
- 2022
15. Cubic Equations Through the Looking Glass of Sylvester
- Author
-
Chen, William Y. C.
- Subjects
Mathematics - History and Overview ,History and Overview (math.HO) ,General Mathematics ,FOS: Mathematics ,Mathematics - Combinatorics ,05A10 ,Combinatorics (math.CO) ,Education - Abstract
One can hardly believe that there is still something to be said about cubic equations. To dodge this doubt, we will instead try and say something about Sylvester. He doubtless found a way of solving cubic equations. As mentioned by Rota, it was the only method in this vein that he could remember. We realize that in the generic case Sylvester's magnificent approach aimed at reduced cubic equations boils down to an easy identity expressing a cubic polynomial as a sum of two third powers of linear forms. This leads to Cardano's formula for cubic equations involving the third roots of unity., Comment: 3 pages, to appear in the College Mathematics Journal
- Published
- 2022
16. Algorithmic Symplectic Packing
- Author
-
Fischer, Greta, Gutt, Jean, and Jünger, Michael
- Subjects
Mathematics - Symplectic Geometry ,Optimization and Control (math.OC) ,General Mathematics ,FOS: Mathematics ,Mathematics - Combinatorics ,Symplectic Geometry (math.SG) ,Combinatorics (math.CO) ,Mathematics - Optimization and Control - Abstract
In this article we explore a symplectic packing problem where the targets and domains are $2n$-dimensional symplectic manifolds. We work in the context where the manifolds have first homology group equal to $\mathbb{Z}^n$, and we require the embeddings to induce isomorphisms between first homology groups. In this case, Maley, Mastrangeli and Traynor showed that the problem can be reduced to a combinatorial optimization problem, namely packing certain allowable simplices into a given standard simplex. They designed a computer program and presented computational results. In particular, they determined the simplex packing widths in dimension four for up to $k=12$ simplices, along with lower bounds for higher values of $k$. We present a modified algorithmic approach that allows us to determine the $k$-simplex packing widths for up to $k = 13$ simplices in dimension four and up to $k = 8$ simplices in dimension six. Moreover, our approach determines all simplex-multisets that allow for optimal packings., Comment: 28 pages, improved general presentation, added an explanation to some numbers appearing in tables
- Published
- 2022
17. Biobjective optimization problems on matroids with binary costs
- Author
-
Jochen Gorski, Kathrin Klamroth, and Julia Sudhoff
- Subjects
FOS: Computer and information sciences ,Control and Optimization ,Optimization and Control (math.OC) ,Applied Mathematics ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,Combinatorics (math.CO) ,Management Science and Operations Research ,Mathematics - Optimization and Control ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
Like most multiobjective combinatorial optimization problems, biobjective optimization problems on matroids are in general intractable and their corresponding decision problems are in general NP-hard. In this paper, we consider biobjective optimization problems on matroids where one of the objective functions is restricted to binary cost coefficients. We show that in this case the problem has a connected efficient set with respect to a natural definition of a neighborhood structure and hence, can be solved efficiently using a neighborhood search approach. This is, to the best of our knowledge, the first non-trivial problem on matroids where connectedness of the efficient set can be established. The theoretical results are validated by numerical experiments with biobjective minimum spanning tree problems (graphic matroids) and with biobjective knapsack problems with a cardinality constraint (uniform matroids). In the context of the minimum spanning tree problem, coloring all edges with cost 0 green and all edges with cost 1 red leads to an equivalent problem where we want to simultaneously minimize one general objective and the number of red edges (which defines the second objective) in a Pareto sense.
- Published
- 2022
18. Collatz Meets Fibonacci
- Author
-
Michael Albert, Bjarki Gudmundsson, and Henning Ulfarsson
- Subjects
Mathematics::Combinatorics ,05A05 ,General Mathematics ,FOS: Mathematics ,Mathematics - Combinatorics ,G.2.1 ,Combinatorics (math.CO) - Abstract
The Collatz map is defined for a positive even integer as half that integer, and for a positive odd integer as that integer threefold, plus one. The Collatz conjecture states that when the map is iterated the number one is eventually reached. We study permutations that arise as sequences from this iteration. We show that permutations of this type of length up to 14 are enumerated by the Fibonacci numbers. Beyond that excess permutations appear. We will explain the appearance of these excess permutations and give an upper bound on the exact enumeration., 7 pages, 2 figures, 2 tables
- Published
- 2022
19. On regular graphs equienergetic with their complements
- Author
-
Podest��, Ricardo A. and Videla, Denis E.
- Subjects
Algebra and Number Theory ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Primary 05C50, Secondary 05C75, 05C92, 05E30 - Abstract
We give necessary and sufficient conditions on the parameters of a regular graph $\Gamma$ (with or without loops) such that $E(\Gamma)=E(\overline \Gamma)$. We study complementary equienergetic cubic graphs obtaining classifications up to isomorphisms for connected cubic graphs with single loops (5 non-isospectral pairs) and connected integral cubic graphs without loops ($\Gamma = K_3 \square K_2$ or $Q_3$). Then we show that, up to complements, the only bipartite regular graphs equienergetic and non-isospectral with their complements are the crown graphs $Cr(n)$ or $C_4$. Next, for the family of strongly regular graphs $\Gamma$ we characterize all possible parameters $srg(n,k,e,d)$ such that $E(\Gamma) = E(\overline \Gamma)$. Furthermore, using this, we prove that a strongly regular graph is equienergetic to its complement if and only if it is either a conference graph or else it is a pseudo Latin square graph (i.e. has $OA$ parameters). We also characterize all complementary equienergetic pairs of graphs of type $\mathcal{C}(2)$, $\mathcal{C}(3)$ and $\mathcal{C}(5)$ in Cameron's hierarchy (the cases $\mathcal{C}(1)$ and $\mathcal{C}(4)$ are still open). Finally, we consider unitary Cayley graphs over rings $G_R=X(R,R^*)$. We show that if $R$ is a finite Artinian ring with an even number of local factors, then $G_R$ is complementary equienergetic if and only if $R=\mathbb{F}_q \times \mathbb{F}_{q'}$ is the product of 2 finite fields., Comment: Some additions, the paper grow from25 to 32 pages (5 tables). We add arbitrary number of loops in Proposition 2.3 and some examples with graphs with loops. Cubic graphs are now in a section (3). In section 8 we add "Unitary Cayley graphs with loops". Final remarks added
- Published
- 2022
20. Multiset and Mixed Metric Dimension for Starphene and Zigzag-Edge Coronoid
- Author
-
Hassan Raza, Vijay Kumar Bhat, SUNNY SHARMA, and Jia-Bao Liu
- Subjects
Polymers and Plastics ,Organic Chemistry ,FOS: Mathematics ,Materials Chemistry ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,05C12, 05C90 - Abstract
Let $\Gamma=(V,E)$ be a simple connected graph. A vertex $a$ is said to recognize (resolve) two different elements $b_{1}$ and $b_{2}$ from $V(\Gamma)\cup E(\Gamma)$ if $d(a, b_{1})\neq d(a, b_{2}\}$. A subset of distinct ordered vertices $U_{M}\subseteq V(\Gamma)$ is said to be a mixed metric generator for $\Gamma$ if each pair of distinct elements from $V\cup E$ are recognized by some element of $U_{M}$. The mixed metric generator with a minimum number of elements is called a mixed metric basis of $\Gamma$. Then, the cardinality of this mixed metric basis for $\Gamma$ is called the mixed metric dimension of $\Gamma$, denoted by $mdim(\Gamma)$. The concept of studying chemical structures using graph theory terminologies is both appealing and practical. It enables researchers to more precisely and easily examines various chemical topologies and networks. In this paper, we consider two well known chemical structures; starphene $SP_{a,b,c}$ and six-sided hollow coronoid $HC_{a,b,c}$ and respectively compute their multiset dimension and mixed metric dimension., Comment: 13 pages, 3 figures, 3 tables
- Published
- 2021
21. Hessenberg varieties associated to ad-nilpotent ideals
- Author
-
Martha Precup and Caleb Ji
- Subjects
Pure mathematics ,Algebra and Number Theory ,Fiber (mathematics) ,Flag (linear algebra) ,Mathematics::Rings and Algebras ,Function (mathematics) ,Mathematics::Numerical Analysis ,Mathematics - Algebraic Geometry ,Nilpotent ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Affine transformation ,Ideal (ring theory) ,Variety (universal algebra) ,Mathematics::Representation Theory ,Algebraic Geometry (math.AG) ,Mathematics ,Hessenberg variety - Abstract
We consider Hessenberg varieties in the flag variety of $GL_n(\mathbb{C})$ with the property that the corresponding Hessenberg function defines an ad-nilpotent ideal. Each such Hessenberg variety is contained in a Springer fiber. We extend a theorem of Tymoczko to this setting, showing that these varieties have an affine paving obtained by intersecting with Schubert cells. Our method of proof constructs an an affine paving for each Springer fiber that restricts to an affine paving of the Hessenberg variety. We use the combinatorial properties of this paving to prove that Hessenberg varieties of this kind are connected., Comment: 21 pages
- Published
- 2021
22. Sums of Finite Sets of Integers, II
- Author
-
Melvyn Nathanson
- Subjects
Mathematics - Number Theory ,11B13, 11B34, 11B75, 11D07 ,General Mathematics ,FOS: Mathematics ,Mathematics - Combinatorics ,Number Theory (math.NT) ,Combinatorics (math.CO) - Abstract
Let $\mathcal{A}$ be a finite set of integers, and let $h\mathcal{A}$ denote the $h$-fold sumset of $\mathcal{A}$. Let $(h\mathcal{A})^{(t)}$ be subset of $h\mathcal{A}$ consisting of all integers that have at least $t$ representations as a sum of $h$ elements of $\mathcal{A}$. The structure of the set $(h\mathcal{A})^{(t)}$ is completely determined for all $h \geq h_t$., 8 pages; minor revisions
- Published
- 2021
23. Computer Bounds for Kronheimer–Mrowka Foam Evaluation
- Author
-
David Boozer
- Subjects
Functor ,General Mathematics ,Dimension (graph theory) ,05-04, 05C10, 05C15, 57M15, 57R56 ,Geometric Topology (math.GT) ,Four color theorem ,Field (mathematics) ,Special class ,Combinatorics ,Mathematics - Geometric Topology ,Dodecahedron ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Gauge theory ,Vector space ,Mathematics - Abstract
Kronheimer and Mrowka recently suggested a possible approach towards a new proof of the four color theorem that does not rely on computer calculations. Their approach is based on a functor $J^\sharp$, which they define using gauge theory, from the category of webs and foams to the category of vector spaces over the field of two elements. They also consider a possible combinatorial replacement $J^\flat$ for $J^\sharp$. Of particular interest is the relationship between the dimension of $J^\flat(K)$ for a web $K$ and the number of Tait colorings $\mathrm{Tait}(K)$ of $K$; these two numbers are known to be identical for a special class of "reducible" webs, but whether this is the case for nonreducible webs is not known. We describe a computer program that strongly constrains the possibilities for the dimension and graded dimension of $J^\flat(K)$ for a given web $K$, in some cases determining these quantities uniquely. We present results for a number of nonreducible example webs. For the dodecahedral web $W_1$ the number of Tait colorings is $\mathrm{Tait}(W_1) = 60$, but our results suggest that $\dim J^\flat(W_1) = 58$., Comment: 15 pages, 7 figures; minor revisions to abstract and introduction to clarify implications of results
- Published
- 2021
24. Number of Vertices of the Polytope of Integer Partitions and Factorization of the Partitioned Number
- Author
-
Shlyk, Vladimir A.
- Subjects
General Mathematics ,Mathematics - Combinatorics ,05A17 (Primary), 52B12 (Secondary) - Abstract
The polytope of integer partitions of $n$ is the convex hull of the corresponding $n$-dimensional integer points. Its vertices are of importance because every partition is their convex combination. Computation shows intriguing features of $v(n),$ the number of the polytope vertices: its graph has a saw-toothed shape with the highest peaks at prime $n$'s. We explain the shape of $v(n)$ by the large number of partitions of even $n$'s that were counted by N. Metropolis and P. R. Stein. These partitions are convex combinations of two others. We reveal that divisibility of $n$ by 3 also reduces the value of $v(n),$ which is caused by partitions that are convex combinations of three but not two others, and characterize convex representations of such integer points in arbitrary integral polytope. To approach the prime $n$ phenomenon, we use a specific classification of integers and demonstrate that the graph of $v(n)$ is stratified to layers corresponding to resulting classes. Our main conjecture claims that $v(n)$ depends on collections of divisors of $n.$ We also offer an initial argument for that the number of vertices of the Gomory's master corner polyhedron on the cyclic group has features similar to those of $v(n).$, Comment: 14 pages, 6 figures, 2 tables. Modified version of the article. The setting out is improved. The statement of Corollary 1 is corrected. New data are used in section 6
- Published
- 2021
25. A Frameless 2-Coloring of the Plane Lattice
- Author
-
Craig S. Kaplan and Jeffrey Shallit
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,Formal Languages and Automata Theory (cs.FL) ,General Mathematics ,FOS: Mathematics ,Mathematics - Combinatorics ,Computer Science - Formal Languages and Automata Theory ,Combinatorics (math.CO) ,Computer Science - Discrete Mathematics - Abstract
A picture frame in two dimensions is a rectangular array of symbols, with at least two rows and columns, where the first and last rows are identical, and the first and last columns are identical. If a coloring of the plane lattice has no picture frames, we call it frameless. In this note we show how to create a simple 2-coloring of the plane lattice that is frameless.
- Published
- 2021
26. On some p-transitive association schemes
- Author
-
Yu Jiang
- Subjects
Discrete mathematics ,Finite group ,Transitive relation ,Algebra and Number Theory ,digestive, oral, and skin physiology ,Group algebra ,Prime (order theory) ,Association scheme ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Representation Theory (math.RT) ,Mathematics - Representation Theory ,05E30 ,Mathematics - Abstract
In this paper, for any prime $p$, we propose the notion of a $p$-transitive association scheme. This notion aims to generalize the fact that the regular module of a group algebra of a finite group has a unique trivial submodule to the case of the regular modules of modular adjacency algebras. We completely determine the $p$-transitive quasi-thin association schemes and the $p$-transitive association schemes with thin thin residue by their structure theory properties., 14 pages, typo-free version
- Published
- 2021
27. Strong metric dimensions for power graphs of finite groups
- Author
-
Liangliang Zhai and Xuanlong Ma
- Subjects
Mathematics::Functional Analysis ,Finite group ,Epigraph ,Algebra and Number Theory ,High Energy Physics::Lattice ,High Energy Physics::Phenomenology ,010102 general mathematics ,010103 numerical & computational mathematics ,05C25, 05C69 ,01 natural sciences ,Graph ,Vertex (geometry) ,Power (physics) ,Metric dimension ,Nonlinear Sciences::Chaotic Dynamics ,Set (abstract data type) ,Combinatorics ,Mathematics::Group Theory ,FOS: Mathematics ,Mathematics - Combinatorics ,Order (group theory) ,Combinatorics (math.CO) ,0101 mathematics ,Mathematics - Abstract
Let $G$ be a finite group. The order supergraph of $G$ is the graph with vertex set $G$, and two distinct vertices $x,y$ are adjacent if $o(x)\mid o(y)$ or $o(y)\mid o(x)$. The enhanced power graph of $G$ is the graph whose vertex set is $G$, and two distinct vertices are adjacent if they generate a cyclic subgroup. The reduced power graph of $G$ is the graph with vertex set $G$, and two distinct vertices $x,y$ are adjacent if $\langle x\rangle \subset \langle y\rangle$ or $\langle y\rangle \subset \langle x\rangle$. In this paper, we characterize the strong metric dimension of the order supergraph, the enhanced power graph and the reduced power graph of a finite group., Comment: This is the final version to be published in Communications in Algebra, 16 pages
- Published
- 2021
28. Exponential Riordan arrays and Jacobi elliptic functions
- Author
-
Paul Barry and Arnauld Mesinga Mwafise
- Subjects
Pure mathematics ,Mathematics::Combinatorics ,Algebra and Number Theory ,Mathematics::Probability ,FOS: Mathematics ,Elliptic function ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Mathematics ,Exponential function ,Jacobi elliptic functions - Abstract
This paper establishes relationships between elliptic functions and Riordan arrays leading to new classes of Riordan arrays which here are called elliptic Riordan arrays. In particular, the case of Riordan arrays derived from Jacobi elliptic functions that are parameterized by the elliptic modulus $k$ will be treated here. Some concrete examples of such Riordan arrays are presented via a recursive formula.
- Published
- 2021
29. Density of numerical sets associated to a numerical semigroup
- Author
-
Deepesh Singhal and Yuxin Lin
- Subjects
Pure mathematics ,Algebra and Number Theory ,Semigroup ,010102 general mathematics ,Zero (complex analysis) ,010103 numerical & computational mathematics ,01 natural sciences ,Set (abstract data type) ,Mathematics::Category Theory ,Numerical semigroup ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,0101 mathematics ,Mathematics - Abstract
A numerical set is a co-finite subset of the natural numbers that contains zero. Its Frobenius number is the largest number in its complement. Each numerical set has an associated semigroup $A(T)=\{t\mid t+T\subseteq T\}$, which has the same Frobenius number as $T$. For a fixed Frobenius number $f$ there are $2^{f-1}$ numerical sets. It is known that there is a number $\gamma$ close to $0.484$ such that the ratio of these numerical sets that are mapped to $N_f=\{0\}\cup(f,\infty)$ is asymptotically $\gamma$. We identify a collection of families $N(D,f)$ of numerical semigroups such that for a fixed $D$ the ratio of the $2^{f-1}$ numerical sets that are mapped to $N(D,f)$ converges to a positive limit as $f$ goes to infinity. We denote the limit as $\gamma_D$, these constants sum up to $1$ meaning that they asymptotically account for almost all numerical sets., Comment: 13 pages
- Published
- 2021
30. Distance matrix of weighted cactoid-type digraphs
- Author
-
Sumit Mohanty and Joyentanuj Das
- Subjects
Strongly connected component ,Mathematics::Combinatorics ,Algebra and Number Theory ,Inverse ,Digraph ,Type (model theory) ,Combinatorics ,Distance matrix ,Computer Science::Discrete Mathematics ,Path (graph theory) ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Computer Science::Data Structures and Algorithms ,05C12, 05C50 ,Mathematics - Abstract
A strongly connected digraph is called a cactoid-type if each of its blocks is a digraph consisting of finitely many oriented cycles sharing a common directed path. In this article, we find the formula for the determinant of the distance matrix for weighted cactoid-type digraphs and find its inverse, whenever it exists. We also compute the determinant of the distance matrix for a class of unweighted and undirected graphs consisting of finitely many cycles, sharing a common path.
- Published
- 2021
31. Disconnected character graphs and odd dominating sets
- Author
-
Mahdi Ebrahimi
- Subjects
Algebra and Number Theory ,Simple graph ,010102 general mathematics ,Group Theory (math.GR) ,010103 numerical & computational mathematics ,20C15, 05C69, 05C25 ,01 natural sciences ,Combinatorics ,Set (abstract data type) ,Character (mathematics) ,Dominating set ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,0101 mathematics ,Mathematics - Group Theory ,Mathematics - Abstract
Suppose $\Gamma$ is a finite simple graph. If $D$ is a dominating set of $\Gamma$ such that each $x\in D$ is contained in the set of vertices of an odd cycle of $\Gamma$, then we say that $D$ is an odd dominating set for $\Gamma$. For a finite group $G$, let $\Delta(G)$ denote the character graph built on the set of degrees of the irreducible complex characters of $G$. In this paper, we show that the complement of $\Delta(G)$ contains an odd dominating set, if and only if $\Delta(G)$ is a disconnected graph with non-bipartite complement., Comment: arXiv admin note: text overlap with arXiv:2002.01353, arXiv:1909.01180, arXiv:1909.03062
- Published
- 2021
32. (Re)constructing Code Loops
- Author
-
David Michael Roberts and Ben Nagy
- Subjects
Code (set theory) ,Class (set theory) ,Computer science ,General Mathematics ,010102 general mathematics ,Group Theory (math.GR) ,Extension (predicate logic) ,01 natural sciences ,20N05 (primary), 20B40, 20G10 (secondary) ,Algebra ,Binary Golay code ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,0101 mathematics ,Moufang loop ,Mathematics - Group Theory - Abstract
The Moufang loop named for Richard Parker is a central extension of the extended binary Golay code. It the prototypical example of a general class of nonassociative structures known today as code loops, which have been studied from a number of different algebraic and combinatorial perspectives. This expository article aims to highlight an experimental approach to computing in code loops, by a combination of a small amount of precomputed information and making use of the rich identities that code loops' twisted cocycles satisfy. As a byproduct we demonstrate that one can reconstruct the multiplication in Parker's loop from a mere fragment of its twisted cocycle. We also give relatively large subspaces of the Golay code over which Parker's loop splits as a direct product., 10 pages, three figures, one ancillary text file containing enough data to reconstruct the multiplication in the Parker loop. v2 Updated after referee feedback
- Published
- 2021
33. On numerical semigroups with at most 12 left elements
- Author
-
D. Marín-Aragón, Shalom Eliahou, Laboratoire de Mathématiques Pures et Appliquées Joseph Liouville (LMPA), and Université du Littoral Côte d'Opale (ULCO)
- Subjects
Algebra and Number Theory ,010102 general mathematics ,Group Theory (math.GR) ,010103 numerical & computational mathematics ,01 natural sciences ,[MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR] ,Conductor ,Set (abstract data type) ,Combinatorics ,Dimension (vector space) ,Numerical semigroup ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,FOS: Mathematics ,Mathematics - Combinatorics ,Embedding ,Combinatorics (math.CO) ,0101 mathematics ,Mathematics - Group Theory ,Mathematics - Abstract
For a numerical semigroup S $\subseteq$ N with embedding dimension e, conductor c and left part L = S $\cap$ [0, c -- 1], set W (S) = e|L| -- c. In 1978 Wilf asked, in equivalent terms, whether W (S) $\ge$ 0 always holds, a question known since as Wilf's conjecture. Using a closely related lower bound W 0 (S) $\le$ W (S), we show that if |L| $\le$ 12 then W 0 (S) $\ge$ 0, thereby settling Wilf's conjecture in this case. This is best possible, since cases are known where |L| = 13 and W 0 (S) = --1. Wilf's conjecture remains open for |L| $\ge$ 13.
- Published
- 2021
34. Containing All Permutations
- Author
-
Vincent Vatter and Michael Engen
- Subjects
Combinatorics ,Computer science ,General Mathematics ,010102 general mathematics ,Mathematics - Combinatorics ,DIAC ,0101 mathematics ,Object (computer science) ,01 natural sciences - Abstract
Numerous versions of the question "what is the shortest object containing all permutations of a given length?" have been asked over the past fifty years: by Karp (via Knuth) in 1972; by Chung, Diaconis, and Graham in 1992; by Ashlock and Tillotson in 1993; and by Arratia in 1999. The large variety of questions of this form, which have previously been considered in isolation, stands in stark contrast to the dearth of answers. We survey and synthesize these questions and their partial answers, introduce infinitely more related questions, and then establish an improved upper bound for one of these questions., Comment: To appear in the American Mathematical Monthly
- Published
- 2021
35. Distance matrix of a multi-block graph: determinant and inverse
- Author
-
Joyentanuj Das and Sumit Mohanty
- Subjects
Block graph ,Algebra and Number Theory ,Inverse ,010103 numerical & computational mathematics ,01 natural sciences ,Graph ,Combinatorics ,Distance matrix ,FOS: Mathematics ,Mathematics - Combinatorics ,Multipartite graph ,Combinatorics (math.CO) ,0101 mathematics ,05C12, 05C50 ,Connectivity ,Distance matrices in phylogeny ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
A connected graph is called a multi-block graph if each of its blocks is a complete multi-partite graph. Building on the work of \cite{Bp3,Hou3}, we compute the determinant and inverse of the distance matrix for a class of multi-block graphs.
- Published
- 2020
36. Connectedness of Lakshmibai-Seshadri path crystals for hyperbolic Kac-Moody algebras of rank 2
- Author
-
Ryuta Hiasa
- Subjects
Path (topology) ,Pure mathematics ,Algebra and Number Theory ,Social connectedness ,010102 general mathematics ,010103 numerical & computational mathematics ,01 natural sciences ,Crystal ,High Energy Physics::Theory ,Mathematics::Quantum Algebra ,FOS: Mathematics ,Mathematics - Combinatorics ,Rank (graph theory) ,Graph (abstract data type) ,Combinatorics (math.CO) ,0101 mathematics ,Algebra over a field ,Mathematics::Representation Theory ,Mathematics - Abstract
Let $\mathfrak{g}$ be a hyperbolic Kac-Moody algebra of rank $2$. We give a necessary and sufficient condition for the crystal graph of the Lakshmibai-Seshadri path crystal $\mathbb{B}(\lambda)$ to be connected for an arbitrary integral weight $\lambda$., Comment: 22 pages, 3 figures; to appear in Comm. Algebra
- Published
- 2020
37. On basic operations related to network induction of discrete convex functions
- Author
-
Kazuo Murota
- Subjects
TheoryofComputation_MISCELLANEOUS ,Mathematical optimization ,021103 operations research ,Control and Optimization ,Applied Mathematics ,MathematicsofComputing_GENERAL ,MathematicsofComputing_NUMERICALANALYSIS ,0211 other engineering and technologies ,0102 computer and information sciences ,02 engineering and technology ,90C27, 90C10, 90C25 ,01 natural sciences ,Optimization and Control (math.OC) ,010201 computation theory & mathematics ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Convex function ,Mathematics - Optimization and Control ,Game theory ,Software ,Mathematics - Abstract
Discrete convex functions are used in many areas, including operations research, discrete-event systems, game theory, and economics. The objective of this paper is to investigate basic operations such as direct sum, splitting, and aggregation that are related to network induction of discrete convex functions as well as discrete convex sets. Various kinds of discrete convex functions in discrete convex analysis are considered such as integrally convex functions, L-convex functions, M-convex functions, multimodular functions, and discrete midpoint convex functions., Comment: 42 pages. arXiv admin note: text overlap with arXiv:1907.09161
- Published
- 2020
38. Combinatorial index formulas for Lie algebras of seaweed type
- Author
-
Vincent E. Coll, Alex Cameron, and Matthew Hyatt
- Subjects
Pure mathematics ,Algebra and Number Theory ,Index (economics) ,Computation ,010102 general mathematics ,Mathematics - Rings and Algebras ,010103 numerical & computational mathematics ,Type (model theory) ,01 natural sciences ,Meander (mathematics) ,Rings and Algebras (math.RA) ,Lie algebra ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,0101 mathematics ,Algebra over a field ,Mathematics::Representation Theory ,Computer Science::Databases ,Mathematics - Abstract
Analogous to the types A, B, and C cases, we address the computation of the index of seaweed subalgebras in the type-D case. Formulas for the algebra's index can be computed by counting the connected components of its associated meander. We focus on a set of distinguished vertices of the meander, called the tail of the meander, and using the tail, we provide comprehensive combinatorial formulas for the index of a seaweed in all the classical types. Using these formulas, we provide all general closed-form index formulas where the index is given by a polynomial greatest common divisor formula in the sizes of the parts that define the seaweed.
- Published
- 2020
39. Statistics of Square-Tiled Surfaces: Symmetry and Short Loops
- Author
-
Sunrose T. Shrestha and Jane Wang
- Subjects
Class (set theory) ,General Mathematics ,010102 general mathematics ,Geometric Topology (math.GT) ,Torus ,Geometry ,Dynamical Systems (math.DS) ,0102 computer and information sciences ,Translation (geometry) ,01 natural sciences ,Square (algebra) ,Mathematics - Geometric Topology ,010201 computation theory & mathematics ,Simplicity (photography) ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Mathematics - Dynamical Systems ,0101 mathematics ,Symmetry (geometry) ,Mathematics - Abstract
Square-tiled surfaces are a class of translation surfaces that are of particular interest in geometry and dynamics because, as covers of the square torus, they share some of its simplicity and structure. In this paper, we study counting problems that result from focusing on properties of the square torus one by one. After drawing insights from experimental evidence, we consider the implications between these properties and their frequency in each stratum of translation surfaces., 18 pages
- Published
- 2020
40. A Stochastic Approach to Eulerian Numbers
- Author
-
Kiana Mittelstaedt
- Subjects
General Mathematics ,Aggregate behavior ,Eulerian path ,Random walk ,symbols.namesake ,FOS: Mathematics ,05A15, 60C05 ,symbols ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Statistical physics ,Internal diffusion ,Mathematics ,Sequence (medicine) - Abstract
We examine the aggregate behavior of one-dimensional random walks in a model known as (one-dimensional) Internal Diffusion Limited Aggregation. In this model, a sequence of $n$ particles perform random walks on the integers, beginning at the origin. Each particle walks until it reaches an unoccupied site, at which point it occupies that site and the next particle begins its walk. After all walks are complete, the set of occupied sites is an interval of length $n$ containing the origin. We show the probability that $k$ of the occupied sites are positive is given by an Eulerian probability distribution. Having made this connection, we use generating function techniques to compute the expected run time of the model., Comment: 14 pages
- Published
- 2020
41. The Martin Gardner Polytopes
- Author
-
Raman Sanyal, Nicole Schulz, Kristin Fritsch, and Janin Heuer
- Subjects
Mathematics::Combinatorics ,General Mathematics ,010102 general mathematics ,Magic (programming) ,Polytope ,01 natural sciences ,Combinatorics ,FOS: Mathematics ,Mathematics - Combinatorics ,Mathematics::Metric Geometry ,Combinatorics (math.CO) ,05Axx, 52B12, 52B20, 52B35 ,0101 mathematics ,Mathematics - Abstract
In the chapter "Magic with a Matrix" in \emph{Hexaflexagons and Other Mathematical Diversions} (1988), Martin Gardner describes a delightful "party trick" to fill the squares of a $d$-by-$d$ chessboard with nonnegative integers such that the sum of the numbers covered by any placement of $d$ nonthreatening rooks is a given number $N$. We consider such chessboards from a geometric perspective which gives rise to a family of lattice polytopes. The polyhedral structure of these Gardner polytopes explains the underlying trick and enables us to count such chessboards for given $N$ in three different ways. We also observe a curious duality that relates Gardner polytopes to Birkhoff polytopes., Comment: 8 pages, v4: substantially improved results and exposition, accepted for publication in American Mathematical Monthly
- Published
- 2020
42. Free quadri-algebras and dual quadri-algebras
- Author
-
Loïc Foissy, Foissy, Loïc, and Combinatoire Algébrique, Résurgence, Moules et Applications - - CARMA2012 - ANR-12-BS01-0017 - BLANC - VALID
- Subjects
Pure mathematics ,Koszul duality ,Combinatorial Hopf algebras ,010103 numerical & computational mathematics ,Mathematics::Algebraic Topology ,01 natural sciences ,Mathematics::K-Theory and Homology ,18D50 ,Mathematics::Quantum Algebra ,Mathematics::Category Theory ,[MATH.MATH-RA] Mathematics [math]/Rings and Algebras [math.RA] ,Subobject ,Mathematics - Combinatorics ,0101 mathematics ,Mathematics ,Algebra and Number Theory ,Generator (computer programming) ,Conjecture ,Mathematics::Rings and Algebras ,010102 general mathematics ,Hopf algebra ,Dual (category theory) ,16W10, 18D50, 16T05 ,16T05 KEYWORDS Quadri-algebras ,AMS CLASSIFICATION16W10 - Abstract
We study quadri-algebras and dual quadri-algebras. We describe the free quadri-algebra on one generator as a subobject of the Hopf algebra of permutations FQSym, proving a conjecture due to Aguiar and Loday, using that the operad of quadri-algebras can be obtained from the operad of dendriform algebras by both black and white Manin products. We also give a combinatorial description of free dual quadri-algebras. A notion of quadri-bialgebra is also introduced, with applications to the Hopf algebras FQSym and WQSym., Comment: 19 pages
- Published
- 2020
43. On parametrized families of numerical semigroups
- Author
-
Franklin Kerstetter and Christopher O'Neill
- Subjects
Pure mathematics ,Algebra and Number Theory ,Mathematics::Commutative Algebra ,Mathematics::Operator Algebras ,Betti number ,010102 general mathematics ,Of the form ,010103 numerical & computational mathematics ,Commutative Algebra (math.AC) ,Mathematics - Commutative Algebra ,01 natural sciences ,Mathematics::Group Theory ,Numerical semigroup ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,0101 mathematics ,Mathematics - Abstract
A numerical semigroup is an additive subsemigroup of the non-negative integers. In this paper, we consider parametrized families of numerical semigroups of the form $P_n = \langle f_1(n), \ldots, f_k(n) \rangle$ for polynomial functions $f_i$. We conjecture that for large $n$, the Betti numbers, Frobenius number, genus, and type of $P_n$ each coincide with a quasipolynomial. This conjecture has already been proven in general for Frobenius numbers, and for the remaining quantities in the special case when $P_n = \langle n, n + r_2, \ldots, n + r_k \rangle$. Our main result is to prove our conjecture in the case where each $f_i$ is linear. In the process, we develop the notion of weighted factorization length, and generalize several known results for standard factorization lengths and delta sets to this weighted setting.
- Published
- 2020
44. The 6-girth-thickness of the complete graph
- Author
-
Héctor Castañeda-López, Christian Rubio-Montiel, Claudia Silva-Ruiz, Andrea B. Ramos-Tort, and Pablo C. Palomino
- Subjects
lcsh:Mathematics ,010102 general mathematics ,Complete graph ,planar decomposition ,0102 computer and information sciences ,lcsh:QA1-939 ,01 natural sciences ,thickness ,Graph ,girth ,Combinatorics ,010201 computation theory & mathematics ,FOS: Mathematics ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Combinatorics (math.CO) ,0101 mathematics ,complete graph ,05C10 ,Mathematics - Abstract
The $g$-girth-thickness $\theta(g,G)$ of a graph $G$ is the minimum number of planar subgraphs of girth at least $g$ whose union is $G$. In this paper, we determine the $6$-girth-thickness $\theta(6,K_n)$ of the complete graph $K_n$ in almost all cases. And also, we calculate by computer the missing value of $\theta(4,K_n)$., Comment: 10 pages, 8 figures
- Published
- 2020
45. Normal 5-edge-colorings of a family of Loupekhine snarks
- Author
-
Luca Ferrarini, Vahan Mkrtchyan, Giuseppe Mazzuoccolo, Ferrarini, L, Mazzuoccolo, G, and Mkrtchyan, V
- Subjects
FOS: Computer and information sciences ,Cubic graph ,Petersen coloring conjecture ,normal edge-coloring ,class of snarks ,Discrete Mathematics (cs.DM) ,cubic graph ,lcsh:Mathematics ,Edge (geometry) ,petersen coloring conjecture ,lcsh:QA1-939 ,Combinatorics ,Set (abstract data type) ,class of snark ,Computer Science::Discrete Mathematics ,FOS: Mathematics ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Combinatorics (math.CO) ,MAT/03 - GEOMETRIA ,Computer Science - Discrete Mathematics ,Mathematics - Abstract
In a proper edge-coloring of a cubic graph an edge $uv$ is called poor or rich, if the set of colors of the edges incident to $u$ and $v$ contains exactly three or five colors, respectively. An edge-coloring of a graph is normal, if any edge of the graph is either poor or rich. In this note, we show that some snarks constructed by using a method introduced by Loupekhine admit a normal edge-coloring with five colors. The existence of a Berge-Fulkerson Covering for a part of the snarks considered in this paper was recently proved by Manuel and Shanthi (2015). Since the existence of a normal edge-coloring with five colors implies the existence of a Berge-Fulkerson Covering, our main theorem can be viewed as a generalization of their result., Comment: 8 pages, 6 figures
- Published
- 2020
46. Partial theta function identities from Wang and Ma's conjecture
- Author
-
Chuanan Wei
- Subjects
Basic hypergeometric series ,Algebra and Number Theory ,Conjecture ,Applied Mathematics ,010102 general mathematics ,Theta function ,01 natural sciences ,010101 applied mathematics ,Combinatorics ,Identity (mathematics) ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,FOS: Mathematics ,Mathematics - Combinatorics ,Embedding ,Combinatorics (math.CO) ,0101 mathematics ,Analysis ,Mathematics - Abstract
Recently, Wang and Ma propose a conjecture associated with the possible generalization of Andrews-Warnaar identities. It is confirmed in this paper. As the applications of this conjecture, we prove that a family of series can be expressed by the partial theta functions and construct some new partial theta function identities.
- Published
- 2020
47. Centrosymmetric stochastic matrices
- Author
-
Sarah Plosker, Darian McLaren, and Lei Cao
- Subjects
Pure mathematics ,Algebra and Number Theory ,Convex set ,Stochastic matrix ,010103 numerical & computational mathematics ,01 natural sciences ,15B51, 05C35 ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,0101 mathematics ,Extreme point ,Centrosymmetric matrix ,Rotation (mathematics) ,Mathematics - Abstract
We consider the convex set $\Gamma_{m,n}$ of $m\times n$ stochastic matrices and the convex set $\Gamma_{m,n}^\pi\subset \Gamma_{m,n}$ of $m\times n$ centrosymmetric stochastic matrices (stochastic matrices that are symmetric under rotation by 180 degrees). For $\Gamma_{m,n}$, we demonstrate a Birkhoff theorem for its extreme points and create a basis from certain $(0,1)$-matrices. For $\Gamma_{m,n}^\pi$, we characterize its extreme points and create bases, whose construction depends on the parity of $m$, using our basis construction for stochastic matrices. For each of $\Gamma_{m,n}$ and $\Gamma_{m,n}^\pi$, we further characterize their extreme points in terms of their associated bipartite graphs, we discuss a graph parameter called the fill and compute it for the various basis elements, and we examine the number of vertices of the faces of these sets. We provide examples illustrating the results throughout., Comment: 12 pages, 1 table, 1 figure
- Published
- 2020
48. Algebraic Matroids in Action
- Author
-
Zvi Rosen, Louis Theran, Jessica Sidman, and University of St Andrews. Pure Mathematics
- Subjects
Algebraic statistics ,General Mathematics ,T-NDAS ,010102 general mathematics ,01 natural sciences ,Matroid ,Algebra ,Mathematics - Algebraic Geometry ,Action (philosophy) ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,QA Mathematics ,Algebraic independence ,0101 mathematics ,Algebraic number ,QA ,Algebraic Geometry (math.AG) ,Theme (narrative) ,Mathematics - Abstract
In recent years, various notions of algebraic independence have emerged as a central and unifying theme in a number of areas of applied mathematics, including algebraic statistics and the rigidity theory of bar-and-joint frameworks. In each of these settings the fundamental problem is to determine the extent to which certain unknowns depend algebraically on given data. This has, in turn, led to a resurgence of interest in algebraic matroids, which are the combinatorial formalism for algebraic (in)dependence. We give a self-contained introduction to algebraic matroids together with examples highlighting their potential application., v3, more discussion of bar-joint rigidity
- Published
- 2020
49. Remarks on enveloping semigroups
- Author
-
Mahir Bilen Can
- Subjects
Monoid ,Pure mathematics ,Algebra and Number Theory ,010102 general mathematics ,010103 numerical & computational mathematics ,01 natural sciences ,Mathematics - Algebraic Geometry ,Simple group ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Representation Theory (math.RT) ,0101 mathematics ,Algebraic Geometry (math.AG) ,Mathematics - Representation Theory ,Mathematics - Abstract
The local structures of enveloping semigroups of simple groups are investigated. All J-coirreducible connected stabilizer submonoids are determined. The notion of a navel of a reductive monoid is introduced. The cross-section lattice of the enveloping monoid is shown to be atomic. In type A, the generating series for the number of $G\times G$-orbits is found., To appear in Communications in Algebra
- Published
- 2020
50. Lower bounds on nonnegative signed domination parameters in graphs
- Author
-
Arezoo N. Ghameshlou
- Subjects
Domination analysis ,nonnegative signed domination number ,lcsh:Mathematics ,010102 general mathematics ,0102 computer and information sciences ,lcsh:QA1-939 ,nonnegative signed -subdomination number ,01 natural sciences ,Graph ,Combinatorics ,05C69 ,010201 computation theory & mathematics ,Condensed Matter::Superconductivity ,FOS: Mathematics ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Combinatorics (math.CO) ,0101 mathematics ,Mathematics - Abstract
Let $1 \leq k \leq n$ be a positive integer. A {\em nonnegative signed $k$-subdominating function} is a function $f:V(G) \rightarrow \{-1,1\}$ satisfying $\sum_{u\in N_G[v]}f(u) \geq 0$ for at least $k$ vertices $v$ of $G$. The value $\min\sum_{v\in V(G)} f(v)$, taking over all nonnegative signed $k$-subdominating functions $f$ of $G$, is called the {\em nonnegative signed $k$-subdomination number} of $G$ and denoted by $\gamma^{NN}_{ks}(G)$. When $k=|V(G)|$, $\gamma^{NN}_{ks}(G)=\gamma^{NN}_s(G)$ is the {\em nonnegative signed domination number}, introduced in \cite{HLFZ}. In this paper, we investigate several sharp lower bounds of $\gamma^{NN}_s(G)$, which extend some presented lower bounds on $\gamma^{NN}_s(G)$. We also initiate the study of the nonnegative signed $k$-subdomination number in graphs and establish some sharp lower bounds for $\gamma^{NN}_{ks}(G)$ in terms of order and the degree sequence of a graph $G$., Comment: 9 pages
- Published
- 2020
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.