ORIGINAL_ARTICLE
Combinatorial parameters on bargraphs of permutations
In this paper, we consider statistics on permutations of length $n$ represented geometrically as bargraphs having the same number of horizontal steps. More precisely, we find the joint distribution of the descent and up step statistics on the bargraph representations, thereby obtaining a new refined count of permutations of a given length. To do so, we consider the distribution of the parameters on permutations of a more general multiset of which $\mathcal{S}_n$ is a subset. In addition to finding an explicit formula for the joint distribution on this multiset, we provide counts for the total number of descents and up steps of all its members, supplying both algebraic and combinatorial proofs. Finally, we derive explicit expressions for the sign balance of these statistics, from which the comparable results on permutations follow as special cases.
http://toc.ui.ac.ir/article_22243_50e3198f5c3ad3e8dd7663d6d7305903.pdf
2018-06-01T11:23:20
2018-02-22T11:23:20
1
16
10.22108/toc.2017.102359.1483
combinatorial statistic
$q$-generalization
bargraph
permutations
Toufik
Mansour
toufik@math.haifa.ac.il
true
1
Department of Mathematics, University of Tennessee, Knoxville, TN, USA
Department of Mathematics, University of Tennessee, Knoxville, TN, USA
Department of Mathematics, University of Tennessee, Knoxville, TN, USA
AUTHOR
Mark
Shattuck
shattuck@math.utk.edu
true
2
Mathematics Department, University of Tennessee, Knoxville, TN, USA
Mathematics Department, University of Tennessee, Knoxville, TN, USA
Mathematics Department, University of Tennessee, Knoxville, TN, USA
LEAD_AUTHOR
[1] A. Blecher, C. Brennan and A. Knopfmacher, Levels in bargraphs, Ars Math. Contemp., 9 (2015) 297–310.
1
[2] A. Blecher, C. Brennan and A. Knopfmacher, Peaks in bargraphs, Trans. Royal Soc. S. Afr., 71 (2016) 97–103.
2
[3] A. Blecher, C. Brennan and A. Knopfmacher, Combinatorial parameters in bargraphs, Quaest. Math., 39 (2016) 619–635.
3
[4] E. Deutsch and S. Elizalde, Statistics on bargraphs viewed as cornerless Motzkin paths, Discrete Appl. Math., 221 (2017) 54–66.
4
[5] S. Fereti´ c, A perimeter enumeration of column-convex polyominoes, Discrete Math. Theor. Comput. Sci., 9 (2007) 57–83.
5
[6] A. Geraschenko, An investigation of skyline polynomials, http://people.brandeis.edu/ gessel/47a/geraschenko.pdf.
6
[7] S. Heubach and T. Mansour, Combinatorics of Compositions and Words, Discrete Math. Appl., Chapman &
7
Hall/CRC, Boca Raton, (2009).
8
[8] Q.-M. Luo, An explicit formula for the Euler numbers of higher order, Tamkang J. Math., 36 (2005) 315–317.
9
[9] T. Mansour, Enumeration of words by sum of differences between adjacent letters, Discrete Math. Theor. Comput. Sci., 11 (2009) 173–185.
10
[10] J. Osborn and T. Prellberg, Forcing adsorption of a tethered polymer by pulling, J. Stat. Mech., 2010 (2010) 1–18.
11
[11] T. Prellberg and R. Brak, Critical exponents from nonlinear functional equations for partially directed cluster models, J. Stat. Phys., 78 (1995) 701–730.
12
[12] N. J. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org, 2010.
13
[13] H. M. Srivastava and J. Choi, Series Associated with the Zeta and Related Functions, Kluwer Academic Publishers, Dordrecht, 2001.
14
ORIGINAL_ARTICLE
The log-convexity of the fubini numbers
Let $f_n$ denotes the $n$th Fubini number. In this paper, first we give upper and lower bounds for the Fubini numbers $f_n$. Then the log-convexity of the Fubini numbers has been obtained. Furthermore we also give the monotonicity of the sequence $\{\sqrt[n]{f_n}\}_{n\ge 1}$ by using the aforementioned bounds.
http://toc.ui.ac.ir/article_21835_8b52d6cf1daabf7e0e9be379112846e3.pdf
2018-06-01T11:23:20
2018-02-22T11:23:20
17
23
10.22108/toc.2017.104212.1496
Fubini number
log-convexity
monotonicity
Qing
Zou
zou-qing@uiowa.edu
true
1
The University of Iowa
The University of Iowa
The University of Iowa
LEAD_AUTHOR
[1] M. E. Dasef and S. M. Kautz, Some sums of some importance, College Math. J., 28 (1997) 52–55.
1
[2] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009.
2
[3] T. Mansour and M. Schork, Commutation Relations, Normal Ordering, and Stirling Numbers, Chapman and
3
Hall/CRC, 2015.
4
[4] A. Dil and V. Kurt, Investigating Geometric and Exponential Polynomials with Euler-Seidel Matrices, J. Integer Seq., 14 (2011) pp. 12.
5
[5] N. Pippenger, The Hypercube of Resistors, Asymptotic Expansions, and Preferential Arrangements, Math. Mag., 83 (2010) 331–346.
6
[6] O. A. Gross, Preferential Arrangements, Amer. Math. Monthly, 69 (1962) 4–8.
7
[7] Z. W. Sun, Conjectures Involving Arithmetical Sequences, Proceedings of the 6th China-Japan Seminar, S. Kane-mitsu, H. Li and J. Liu eds., World Scientific, Singapore, 2013 244–258.
8
[8] W. Y. C. Chen and E. X. W. Xia, 2-log-concavity of the Boros-Moll Polynomials, Proc. Edinb. Math. Soc., 56
9
(2013) 701–722.
10
[9] W. Y. C. Chen, J. J. F. Guo and L. X. W. Wang, Infinitely Log-monotonic Combinatorial Sequences, Adv. in Appl. Math., 52 (2014) 99–120.
11
[10] E. H. Liu and L. J. Jin, The Ratio Log-concavity of the Cohen Numbers, J. Inequal. Appl., 2016 (2016) pp. 9.
12
[11] F.-Z. Zhao, The Log-convexity of Genocchi Numbers and the Monotonicity of Some Sequences Related to Genocchi Numbers, J. Math. Inequal., 10 (2016) 541–550.
13
[12] J. P. Barthelemy, An Asymptotic Equivalent for the Number of Total Preorders on a Finite Set, Discrete Math., 29 (1980) 311–313.
14
[13] M. Aigner, Combinatorial Theory, Grundlehren der Mathematischen Wissenschaften, 234, Springer, Berlin, 1979.
15
[14] A. Knopfmacher and M. E. Mays, A Survey of Factorization Counting Functions, Int. J. Number Theory, 1 (2005) 563–581.
16
[15] Y. Wang and B.-X. Zhu, Proofs of some conjectures on monotonicity of number-theoretic and combinatorial se-quences, Science China Math., 57 no. 11 (2014) 2429–2435.
17
ORIGINAL_ARTICLE
Solution to the minimum harmonic index of graphs with given minimum degree
The harmonic index of a graph $G$ is defined as $ H(G)=\sum\limits_{uv\in E(G)}\frac{2}{d(u)+d(v)}$, where $d(u)$ denotes the degree of a vertex $u$ in $G$. Let $\mathcal{G}(n,k)$ be the set of simple $n$-vertex graphs with minimum degree at least $k$. In this work we consider the problem of determining the minimum value of the harmonic index and the corresponding extremal graphs among $\mathcal{G}(n,k)$. We solve the problem for each integer $k (1\le k\le n/2)$ and show the corresponding extremal graph is the complete split graph $K_{k,n-k}^*$. This result together with our previous result which solve the problem for each integer $k (n/2 \le k\le n-1)$ give a complete solution of the problem.
http://toc.ui.ac.ir/article_22272_28d4f6f37d2867d952c1398e234888f8.pdf
2018-06-01T11:23:20
2018-02-22T11:23:20
25
33
10.22108/toc.2017.101076.1462
harmonic index
minimum degree
extremal graphs
Meili
Liang
liangmeili2004@163.com
true
1
Guangdong University of Foreign Studies
Guangdong University of Foreign Studies
Guangdong University of Foreign Studies
AUTHOR
Bo
Cheng
bocheng2006@126.com
true
2
Guangdong University of Foreign Studies
Guangdong University of Foreign Studies
Guangdong University of Foreign Studies
AUTHOR
Jianxi
Liu
liujianxi2001@gmail.com
true
3
Guangdong University of Foreign Studies
Guangdong University of Foreign Studies
Guangdong University of Foreign Studies
LEAD_AUTHOR
[1] O. Favaron, M. Mahó and J.F. Saclé, Some eigenvalue properties in graphs (conjectures of Graffiti-II), Discrete Math., 111 (1993) 197–220.
1
[2] J. Liu, Harmonic index of dense graphs, Ars Combinatoria, 120 (2015) 293–304.
2
[3] L. Lovász, Combinatorial problems and exercises, Akadémiai Kiadó, Budapest, 1979.
3
[4] X. Li and I. Gutman, Mathematical Aspects of Randic-Type Molecular Structure Descriptors, Mathematical Chem-istry Monographs, Kragujevac, (2006) pp. VI+330.
4
[5] X. Li and Y. T. Shi, A survey on the Randic index, MATCH Commun. Math. Comput. Chem., 59 (2008) 127–156.
5
[6] B. Lucic, N. Trinajstic and B. Zhou, Comparison between the sum-connectivity index and product-connectivity index for benzenoid hydrocarbons, Chem. Phys. Lett., 475 (2009) 146–148.
6
[7] R. Wu, Z. Tang and H. Deng, A lower bound for the harmonic index of a graph with minimum degree at least two, Filomat, 27 (2013) 51–55.
7
[8] L. Zhong, The harmonic index for graphs, Appl. Math. Lett., 25 (2012) 561–566.
8
[9] L. Zhong, The harmonic index on unicyclic graphs, Ars Combin., 104 (2012) 261–269.
9
ORIGINAL_ARTICLE
On matrix and lattice ideals of digraphs
Let $\textit{G}$ be a simple, oriented connected graph with $n$ vertices and $m$ edges. Let $I(\textbf{B})$ be the binomial ideal associated to the incidence matrix \textbf{B} of the graph $G$. Assume that $I_L$ is the lattice ideal associated to the rows of the matrix $\textbf{B}$. Also let $\textbf{B}_i$ be a submatrix of $\textbf{B}$ after removing the $i$-th row. We introduce a graph theoretical criterion for $G$ which is a sufficient and necessary condition for $I(\textbf{B})=I(\textbf{B}_i)$ and $I(\textbf{B}_i)=I_L$. After that we introduce another graph theoretical criterion for $G$ which is a sufficient and necessary condition for $I(\textbf{B})=I_L$. It is shown that the heights of $I(\textbf{B})$ and $I(\textbf{B}_i)$ are equal to $n-1$ and the dimensions of $I(\textbf{B})$ and $I(\textbf{B}_i)$ are equal to $m-n+1$; then $I(\textbf{B}_i)$ is a complete intersection ideal.
http://toc.ui.ac.ir/article_22320_d8db69e39a4e17deb1cc31c93e4e6186.pdf
2018-06-01T11:23:20
2018-02-22T11:23:20
35
46
10.22108/toc.2017.105701.1510
Directed graph
Binomial ideal
Matrix ideals
Hamid
Damadi
hamid.damadi@aut.ac.ir
true
1
Department of Mathematics, Amirkabir University of Technology (Tehran Polytechnic) Tehran, Iran.
Department of Mathematics, Amirkabir University of Technology (Tehran Polytechnic) Tehran, Iran.
Department of Mathematics, Amirkabir University of Technology (Tehran Polytechnic) Tehran, Iran.
AUTHOR
Farhad
Rahmati
frahmati@aut.ac.ir
true
2
Amirkabir University of Technology
Amirkabir University of Technology
Amirkabir University of Technology
LEAD_AUTHOR
[1] C. Berkesch-Zamaere, L. Matusevich and U. Walther, Torus equivariant Dmodules and hypergeometric systems, Preprint, arXiv (2013): 1308:5901.
1
[2] A. Dickenstein, L. Matusevich and E. Miller, Combinatorics of binomial primary decomposition, Math. Z., 264 (2010) 745–763.
2
[3] A. Dickenstein, L. Matusevich and E. Miller, Binomial D-modules, Duke Math. J., 151 (2010) 385–429.
3
[4] K. Eto, Cohen-Macaulay rings associated with oriented digraphs, J. Algebra, 206 (1998) 541–554.
4
[5] K. Eto, A free resolution of a binomial ideal, Comm. Algebra, 27 (1999) 3459–3472.
5
[6] D. Eisenbud and B. Sturmfels, Binomial ideals, Duke Math. J., 84 (1996) 1–45.
6
[7] K. Fischer and J. Shapiro, Mixed matrices and binomial ideals, J. Pure and Appl. Algebra, 113 (1996) 39–54.
7
[8] S. Hosten and J. Shapiro, Primary decomposition of lattice basis ideals, J. Symbolic Comput, 29 (2000) 625–639.
8
[9] H. Matsumura, Commutative algebra, Second edition, Mathematics Lecture Note Series, 56, Benjamin/Cummings Publishing Co., Inc., Reading, Mass., 1980.
9
[10] A. Schrijver, Theory of Linear and Integer Programming, A Wiley-Interscience Publication. John Wiley Sons, Ltd., Chichester, 1986.
10
ORIGINAL_ARTICLE
Reduced zero-divisor graphs of posets
This paper investigates properties of the reduced zero-divisor graph of a poset. We show that a vertex is an annihilator prime ideal if and only if it is adjacent to all other annihilator prime ideals and there are always two annihilator prime ideals which are not adjacent to a non-annihilator prime ideal. We also classify all posets whose reduced zero-divisor graph is planar or toroidal and the number of distinct annihilator prime ideals is four or seven.
http://toc.ui.ac.ir/article_22311_893dce7cc938e8e23dd5defcadb2c102.pdf
2018-06-01T11:23:20
2018-02-22T11:23:20
47
54
10.22108/toc.2018.55164.1417
poset
reduced zero-divisor graph
annihilator prime ideal
Deiborlang
Nongsiang
ndeiborlang@yahoo.in
true
1
North Eastern Hill University
North Eastern Hill University
North Eastern Hill University
LEAD_AUTHOR
Promode
Saikia
promode4@gmail.com
true
2
North Eastern Hill University
North Eastern Hill University
North Eastern Hill University
AUTHOR
[1] M. Alizadeh, A. K. Das, H. R. Maimani, M. R. Pournaki and S. Yassemi, On the diameter and girth of zero-divisor graphs of posets, Discrete Appl. Math., 160 (2012) 1319–1324.
1
[2] G. Chartrand and O. R. Oellermann, Applied and Algorithmic Graph Theory, McGraw-Hill, Inc., New York, 1993.
2
[3] A. K. Das and D. Nongsiang, On Reduced Zero-Divisor Graphs of Posets, J. Discrete Math., 2015 (2015) pp. 7.
3
[4] B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, second ed., Cambridge University Press, New York, 2002.
4
[5] R. Halas, Annihilators and ideals in ordered sets, Czechoslovak Math. J., 45 (1995) 127–134.
5
[6] R. Halas, Relative polars in ordered sets, Czechoslovak Math. J., 50 (2000) 415–429.
6
[7] R. Halas and M. Jukl, On Beck’s coloring of posets, Discrete Math., 309 (2009) 4584–4589.
7
[8] E. Neufeld and W. Myrvold, Practical Toroidality Testing, Proceedings of the eighth annual ACM-SIAM symposium on Discrete Algorithms, New Orleans, LA, 1997 574–580.
8
[9] A. T. White, Graphs, groups and surfaces, North-Holland Mathematics Studies, no. 8., American Elsevier Publishing Co., Inc., New York, 1973.
9