location:  Publications → journals
Search results

Search: MSC category 05 ( Combinatorics )

 Expand all        Collapse all Results 1 - 25 of 53

1. CMB 2014 (vol 57 pp. 658)

Thang, Nguyen Tat
 Admissibility of Local Systems for some Classes of Line Arrangements Let $\mathcal{A}$ be a line arrangement in the complex projective plane $\mathbb{P}^2$ and let $M$ be its complement. A rank one local system $\mathcal{L}$ on $M$ is admissible if roughly speaking the cohomology groups $H^m(M,\mathcal{L})$ can be computed directly from the cohomology algebra $H^{*}(M,\mathbb{C})$. In this work, we give a sufficient condition for the admissibility of all rank one local systems on $M$. As a result, we obtain some properties of the characteristic variety $\mathcal{V}_1(M)$ and the Resonance variety $\mathcal{R}_1(M)$. Keywords:admissible local system, line arrangement, characteristic variety, multinet, resonance varietyCategories:14F99, 32S22, 52C35, 05A18, 05C40, 14H50

2. CMB 2014 (vol 57 pp. 573)

Kiani, Sima; Maimani, Hamid Reza; Nikandish, Reza
 Some Results on the Domination Number of a Zero-divisor Graph In this paper, we investigate the domination, total domination and semi-total domination numbers of a zero-divisor graph of a commutative Noetherian ring. Also, some relations between the domination numbers of $\Gamma(R/I)$ and $\Gamma_I(R)$, and the domination numbers of $\Gamma(R)$ and $\Gamma(R[x,\alpha,\delta])$, where $R[x,\alpha,\delta]$ is the Ore extension of $R$, are studied. Keywords:zero-divisor graph, domination numberCategories:05C75, 13H10

3. CMB 2014 (vol 57 pp. 520)

Guo, Guangquan; Wang, Guoping
 Maximizing the Index of Trees with Given Domination Number The index of a graph $G$ is the maximum eigenvalue of its adjacency matrix $A(G)$. In this paper we characterize the extremal tree with given domination number that attains the maximum index. Keywords:trees, spectral radius, index, domination numberCategory:05C50

4. CMB 2013 (vol 57 pp. 72)

Grari, A.

5. CMB 2013 (vol 57 pp. 375)

López, S. C.; Muntaner-Batle, ; Rius-Font,
 A Problem on Edge-magic Labelings of Cycles Kotzig and Rosa defined in 1970 the concept of edge-magic labelings as follows: let $G$ be a simple $(p,q)$-graph (that is, a graph of order $p$ and size $q$ without loops or multiple edges). A bijective function $f:V(G)\cup E(G)\rightarrow \{1,2,\ldots,p+q\}$ is an edge-magic labeling of $G$ if $f(u)+f(uv)+f(v)=k$, for all $uv\in E(G)$. A graph that admits an edge-magic labeling is called an edge-magic graph, and $k$ is called the magic sum of the labeling. An old conjecture of Godbold and Slater sets that all possible theoretical magic sums are attained for each cycle of order $n\ge 7$. Motivated by this conjecture, we prove that for all $n_0\in \mathbb{N}$, there exists $n\in \mathbb{N}$, such that the cycle $C_n$ admits at least $n_0$ edge-magic labelings with at least $n_0$ mutually distinct magic sums. We do this by providing a lower bound for the number of magic sums of the cycle $C_n$, depending on the sum of the exponents of the odd primes appearing in the prime factorization of $n$. Keywords:edge-magic, valence, $\otimes_h$-productCategory:05C78

6. CMB 2013 (vol 57 pp. 225)

 Small Flag Complexes with Torsion We classify flag complexes on at most $12$ vertices with torsion in the first homology group. The result is moderately computer-aided. As a consequence we confirm a folklore conjecture that the smallest poset whose order complex is homotopy equivalent to the real projective plane (and also the smallest poset with torsion in the first homology group) has exactly $13$ elements. Keywords:clique complex, order complex, homology, torsion, minimal modelCategories:55U10, 06A11, 55P40, 55-04, 05-04

7. CMB 2013 (vol 57 pp. 631)

Sokić, Miodrag
 Indicators, Chains, Antichains, Ramsey Property We introduce two Ramsey classes of finite relational structures. The first class contains finite structures of the form $(A,(I_{i})_{i=1}^{n},\leq ,(\preceq _{i})_{i=1}^{n})$ where $\leq$ is a total ordering on $A$ and $% \preceq _{i}$ is a linear ordering on the set $\{a\in A:I_{i}(a)\}$. The second class contains structures of the form $(A,\leq ,(I_{i})_{i=1}^{n},\preceq )$ where $(A,\leq )$ is a weak ordering and $% \preceq$ is a linear ordering on $A$ such that $A$ is partitioned by $% \{a\in A:I_{i}(a)\}$ into maximal chains in the partial ordering $\leq$ and each $\{a\in A:I_{i}(a)\}$ is an interval with respect to $\preceq$. Keywords:Ramsey property, linear orderingsCategories:05C55, 03C15, 54H20

8. CMB 2013 (vol 57 pp. 141)

Mukwembi, Simon
 Size, Order, and Connected Domination We give a sharp upper bound on the size of a triangle-free graph of a given order and connected domination. Our bound, apart from strengthening an old classical theorem of Mantel and of TurÃ¡n , improves on a theorem of Sanchis. Further, as corollaries, we settle a long standing conjecture of Graffiti on the leaf number and local independence for triangle-free graphs and answer a question of Griggs, Kleitman and Shastri on a lower bound of the leaf number in triangle-free graphs. Keywords:size, connected domination, local independence number, leaf numberCategory:05C69

9. CMB 2013 (vol 57 pp. 188)

 A Characterization of Bipartite Zero-divisor Graphs In this paper we obtain a characterization for all bipartite zero-divisor graphs of commutative rings $R$ with $1$, such that $R$ is finite or $|Nil(R)|\neq2$. Keywords:zero-divisor graph, bipartite graphCategories:13AXX, 05C25

10. CMB 2013 (vol 56 pp. 449)

Akbari, S.; Chavooshi, M.; Ghanbari, M.; Zare, S.
 The $f$-Chromatic Index of a Graph Whose $f$-Core has Maximum Degree $2$ Let $G$ be a graph. The minimum number of colors needed to color the edges of $G$ is called the chromatic index of $G$ and is denoted by $\chi'(G)$. It is well-known that $\Delta(G) \leq \chi'(G) \leq \Delta(G)+1$, for any graph $G$, where $\Delta(G)$ denotes the maximum degree of $G$. A graph $G$ is said to be Class $1$ if $\chi'(G) = \Delta(G)$ and Class $2$ if $\chi'(G) = \Delta(G) + 1$. Also, $G_\Delta$ is the induced subgraph on all vertices of degree $\Delta(G)$. Let $f:V(G)\rightarrow \mathbb{N}$ be a function. An $f$-coloring of a graph $G$ is a coloring of the edges of $E(G)$ such that each color appears at each vertex $v\in V(G)$ at most $f (v)$ times. The minimum number of colors needed to $f$-color $G$ is called the $f$-chromatic index of $G$ and is denoted by $\chi'_{f}(G)$. It was shown that for every graph $G$, $\Delta_{f}(G)\le \chi'_{f}(G)\le \Delta_{f}(G)+1$, where $\Delta_{f}(G)=\max_{v\in V(G)} \big\lceil \frac{d_G(v)}{f(v)}\big\rceil$. A graph $G$ is said to be $f$-Class $1$ if $\chi'_{f}(G)=\Delta_{f}(G)$, and $f$-Class $2$, otherwise. Also, $G_{\Delta_f}$ is the induced subgraph of $G$ on $\{v\in V(G):\,\frac{d_G(v)}{f(v)}=\Delta_{f}(G)\}$. Hilton and Zhao showed that if $G_{\Delta}$ has maximum degree two and $G$ is Class $2$, then $G$ is critical, $G_{\Delta}$ is a disjoint union of cycles and $\delta(G)=\Delta(G)-1$, where $\delta(G)$ denotes the minimum degree of $G$, respectively. In this paper, we generalize this theorem to $f$-coloring of graphs. Also, we determine the $f$-chromatic index of a connected graph $G$ with $|G_{\Delta_f}|\le 4$. Keywords:$f$-coloring, $f$-Core, $f$-Class $1$Categories:05C15, 05C38

11. CMB Online first

Zhang, Jiao; Wang, Qing-Wen
 An Explicit Formula for the Generalized Cyclic Shuffle Map We provide an explicit formula for the generalized cyclic shuffle map for cylindrical modules. Using this formula we give a combinatorial proof of the generalized cyclic Eilenberg-Zilber theorem. Keywords:generalized Cyclic shuffle map, Cylindrical module, Eilenberg-Zilber theorem, Cyclic homologyCategories:19D55, 05E45

12. CMB 2013 (vol 57 pp. 210)

Zhang, Jiao; Wang, Qing-Wen
 An Explicit Formula for the Generalized Cyclic Shuffle Map We provide an explicit formula for the generalized cyclic shuffle map for cylindrical modules. Using this formula we give a combinatorial proof of the generalized cyclic Eilenberg-Zilber theorem. Keywords:generalized Cyclic shuffle map, Cylindrical module, Eilenberg-Zilber theorem, Cyclic homologyCategories:19D55, 05E45

13. CMB 2012 (vol 56 pp. 709)

Bartošová, Dana
 Universal Minimal Flows of Groups of Automorphisms of Uncountable Structures It is a well-known fact, that the greatest ambit for a topological group $G$ is the Samuel compactification of $G$ with respect to the right uniformity on $G.$ We apply the original description by Samuel from 1948 to give a simple computation of the universal minimal flow for groups of automorphisms of uncountable structures using FraÃ¯ssÃ© theory and Ramsey theory. This work generalizes some of the known results about countable structures. Keywords:universal minimal flows, ultrafilter flows, Ramsey theoryCategories:37B05, 03E02, 05D10, 22F50, 54H20

14. CMB 2011 (vol 55 pp. 418)

Vinh, Le Anh
 Maximal Sets of Pairwise Orthogonal Vectors in Finite Fields Given a positive integer $n$, a finite field $\mathbb{F}_q$ of $q$ elements ($q$ odd), and a non-degenerate symmetric bilinear form $B$ on $\mathbb{F}_q^n$, we determine the largest possible cardinality of pairwise $B$-orthogonal subsets $\mathcal{E} \subseteq \mathbb{F}_q^n$, that is, for any two vectors $\mathbf{x}, \mathbf{y} \in \mathcal{E}$, one has $B (\mathbf{x}, \mathbf{y}) = 0$. Keywords:orthogonal sets, zero-distance setsCategory:05B25

15. CMB 2011 (vol 56 pp. 265)

Chen, Yichao; Mansour, Toufik; Zou, Qian
 Embedding Distributions of Generalized Fan Graphs Total embedding distributions have been known for a few classes of graphs. Chen, Gross, and Rieper computed it for necklaces, close-end ladders and cobblestone paths. Kwak and Shim computed it for bouquets of circles and dipoles. In this paper, a splitting theorem is generalized and the embedding distributions of generalized fan graphs are obtained. Keywords:total embedding distribution, splitting theorem, generalized fan graphsCategory:05C10

16. CMB 2011 (vol 56 pp. 407)

 On Domination in Zero-Divisor Graphs We first determine the domination number for the zero-divisor graph of the product of two commutative rings with $1$. We then calculate the domination number for the zero-divisor graph of any commutative artinian ring. Finally, we extend some of the results to non-commutative rings in which an element is a left zero-divisor if and only if it is a right zero-divisor. Keywords:zero-divisor graph, dominationCategories:13AXX, 05C69

17. CMB 2011 (vol 55 pp. 462)

Campbell, Peter S.; Stokke, Anna
 Hook-content Formulae for Symplectic and Orthogonal Tableaux By considering the specialisation $s_{\lambda}(1,q,q^2,\dots,q^{n-1})$ of the Schur function, Stanley was able to describe a formula for the number of semistandard Young tableaux of shape $\lambda$ in terms of the contents and hook lengths of the boxes in the Young diagram. Using specialisations of symplectic and orthogonal Schur functions, we derive corresponding formulae, first given by El Samra and King, for the number of semistandard symplectic and orthogonal $\lambda$-tableaux. Keywords:symplectic tableaux, orthogonal tableaux, Schur functionCategories:05E05, 05E10

18. CMB 2011 (vol 55 pp. 410)

Service, Robert
 A Ramsey Theorem with an Application to Sequences in Banach Spaces The notion of a maximally conditional sequence is introduced for sequences in a Banach space. It is then proved using Ramsey theory that every basic sequence in a Banach space has a subsequence which is either an unconditional basic sequence or a maximally conditional sequence. An apparently novel, purely combinatorial lemma in the spirit of Galvin's theorem is used in the proof. An alternative proof of the dichotomy result for sequences in Banach spaces is also sketched, using the Galvin-Prikry theorem. Keywords:Banach spaces, Ramsey theoryCategories:46B15, 05D10

19. CMB 2011 (vol 54 pp. 217)

Chen, William Y. C.; Wang, Larry X. W.; Yang, Arthur L. B.
 Recurrence Relations for Strongly $q$-Log-Convex Polynomials We consider a class of strongly $q$-log-convex polynomials based on a triangular recurrence relation with linear coefficients, and we show that the Bell polynomials, the Bessel polynomials, the Ramanujan polynomials and the Dowling polynomials are strongly $q$-log-convex. We also prove that the Bessel transformation preserves log-convexity. Keywords:log-concavity, $q$-log-convexity, strong $q$-log-convexity, Bell polynomials, Bessel polynomials, Ramanujan polynomials, Dowling polynomialsCategories:05A20, 05E99

20. CMB 2011 (vol 54 pp. 255)

Dehaye, Paul-Olivier
 On an Identity due to Bump and Diaconis, and Tracy and Widom A classical question for a Toeplitz matrix with given symbol is how to compute asymptotics for the determinants of its reductions to finite rank. One can also consider how those asymptotics are affected when shifting an initial set of rows and columns (or, equivalently, asymptotics of their minors). Bump and Diaconis obtained a formula for such shifts involving Laguerre polynomials and sums over symmetric groups. They also showed how the Heine identity extends for such minors, which makes this question relevant to Random Matrix Theory. Independently, Tracy and Widom used the Wiener-Hopf factorization to express those shifts in terms of products of infinite matrices. We show directly why those two expressions are equal and uncover some structure in both formulas that was unknown to their authors. We introduce a mysterious differential operator on symmetric functions that is very similar to vertex operators. We show that the Bump-Diaconis-Tracy-Widom identity is a differentiated version of the classical Jacobi-Trudi identity. Keywords:Toeplitz matrices, Jacobi-Trudi identity, SzegÅ limit theorem, Heine identity, Wiener-Hopf factorizationCategories:47B35, 05E05, 20G05

21. CMB 2010 (vol 53 pp. 757)

Woo, Alexander
 Interval Pattern Avoidance for Arbitrary Root Systems We extend the idea of interval pattern avoidance defined by Yong and the author for $S_n$ to arbitrary Weyl groups using the definition of pattern avoidance due to Billey and Braden, and Billey and Postnikov. We show that, as previously shown by Yong and the author for $\operatorname{GL}_n$, interval pattern avoidance is a universal tool for characterizing which Schubert varieties have certain local properties, and where these local properties hold. Categories:14M15, 05E15

22. CMB 2010 (vol 53 pp. 425)

Chapoton, Frédéric
 Free Pre-Lie Algebras are Free as Lie Algebras We prove that the $\mathfrak{S}$-module $\operatorname{PreLie}$ is a free Lie algebra in the category of $\mathfrak{S}$-modules and can therefore be written as the composition of the $\mathfrak{S}$-module $\operatorname{Lie}$ with a new $\mathfrak{S}$-module $X$. This implies that free pre-Lie algebras in the category of vector spaces, when considered as Lie algebras, are free on generators that can be described using $X$. Furthermore, we define a natural filtration on the $\mathfrak{S}$-module $X$. We also obtain a relationship between $X$ and the $\mathfrak{S}$-module coming from the anticyclic structure of the $\operatorname{PreLie}$ operad. Categories:18D50, 17B01, 18G40, 05C05

23. CMB 2010 (vol 53 pp. 453)

Desgroseilliers, Marc; Larose, Benoit; Malvenuto, Claudia; Vincent, Christelle
 Some Results on Two Conjectures of Schützenberger We present some partial results concerning two conjectures of SchÃ¼tzenberger on evacuations of Young tableaux. Keywords:Evacuation of Standard Young tableauxCategories:05E10, 05A99

24. CMB 2009 (vol 53 pp. 3)

 A Combinatorial Reciprocity Theorem for Hyperplane Arrangements Given a nonnegative integer $m$ and a finite collection $\mathcal A$ of linear forms on $\mathcal Q^d$, the arrangement of affine hyperplanes in $\mathcal Q^d$ defined by the equations $\alpha(x) = k$ for $\alpha \in \mathcal A$ and integers $k \in [-m, m]$ is denoted by $\mathcal A^m$. It is proved that the coefficients of the characteristic polynomial of $\mathcal A^m$ are quasi-polynomials in $m$ and that they satisfy a simple combinatorial reciprocity law. Categories:52C35, 05E99
 A New Sufficient Condition for a Graph To Be $(g,f,n)$-Critical Let $G$ be a graph of order $p$, let $a$, $b$, and $n$ be nonnegative integers with $1\leq a\lt b$, and let $g$ and $f$ be two integer-valued functions defined on $V(G)$ such that $a\leq g(x)\lt f(x)\leq b$ for all $x\in V(G)$. A $(g,f)$-factor of graph $G$ is a spanning subgraph $F$ of $G$ such that $g(x)\leq d_F(x)\leq f(x)$ for each $x\in V(F)$. Then a graph $G$ is called $(g,f,n)$-critical if after deleting any $n$ vertices of $G$ the remaining graph of $G$ has a $(g,f)$-factor. The binding number $\operatorname{bind}(G)$ of $G$ is the minimum value of ${|N_G(X)|}/{|X|}$ taken over all non-empty subsets $X$ of $V(G)$ such that $N_G(X)\neq V(G)$. In this paper, it is proved that $G$ is a $(g,f,n)$-critical graph if $\operatorname{bind}(G)\gt \frac{(a+b-1)(p-1)}{(a+1)p-(a+b)-bn+2} \quad\text{and}\quad p\geq \frac{(a+b-1)(a+b-2)}{a+1}+\frac{bn}{a}.$ Furthermore, it is shown that this result is best possible in some sense. Keywords:graph, $(g,f)$-factor, $(g,f,n)$-critical graph, binding numberCategory:05C70