Canadian Mathematical Society
Canadian Mathematical Society
  location:  Publicationsjournals
Search results

Search: MSC category 05 ( Combinatorics )

  Expand all        Collapse all Results 26 - 50 of 54

26. CMB 2009 (vol 53 pp. 171)

Thomas, Hugh; Yong, Alexander
Multiplicity-Free Schubert Calculus
Multiplicity-free algebraic geometry is the study of subvarieties $Y\subseteq X$ with the ``smallest invariants'' as witnessed by a multiplicity-free Chow ring decomposition of $[Y]\in A^{\star}(X)$ into a predetermined linear basis. This paper concerns the case of Richardson subvarieties of the Grassmannian in terms of the Schubert basis. We give a nonrecursive combinatorial classification of multiplicity-free Richardson varieties, i.e., we classify multiplicity-free products of Schubert classes. This answers a question of W. Fulton.

Categories:14M15, 14M05, 05E99

27. CMB 2009 (vol 53 pp. 378)

Zhou, Sizhong
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 number

28. CMB 2009 (vol 52 pp. 416)

Malik, Shabnam; Qureshi, Ahmad Mahmood; Zamfirescu, Tudor
Hamiltonian Properties of Generalized Halin Graphs
A Halin graph is a graph $H=T\cup C$, where $T$ is a tree with no vertex of degree two, and $C$ is a cycle connecting the end-vertices of $T$ in the cyclic order determined by a plane embedding of $T$. In this paper, we define classes of generalized Halin graphs, called $k$-Halin graphs, and investigate their Hamiltonian properties.

Keywords:$k$-Halin graph, Hamiltonian, Hamiltonian connected, traceable
Categories:05C45, 05C38

29. CMB 2009 (vol 52 pp. 451)

Pach, János; Tardos, Gábor; Tóth, Géza
Indecomposable Coverings
We prove that for every $k>1$, there exist $k$-fold coverings of the plane (i) with strips, (ii) with axis-parallel rectangles, and (iii) with homothets of any fixed concave quadrilateral, that cannot be decomposed into two coverings. We also construct for every $k>1$ a set of points $P$ and a family of disks $\cal D$ in the plane, each containing at least $k$ elements of $P$, such that, no matter how we color the points of $P$ with two colors, there exists a disk $D\in{\cal D}$ all of whose points are of the same color.

Categories:52C15, 05C15

30. CMB 2008 (vol 51 pp. 584)

Purbhoo, Kevin; Willigenburg, Stephanie van
On Tensor Products of Polynomial Representations
We determine the necessary and sufficient combinatorial conditions for which the tensor product of two irreducible polynomial representations of $\GL(n,\mathbb{C})$ is isomorphic to another. As a consequence we discover families of Littlewood--Richardson coefficients that are non-zero, and a condition on Schur non-negativity.

Keywords:polynomial representation, symmetric function, Littlewood--Richardson coefficient, Schur non-negative
Categories:05E05, 05E10, 20C30

31. CMB 2008 (vol 51 pp. 535)

Csorba, Péter
On the Simple $\Z_2$-homotopy Types of Graph Complexes and Their Simple $\Z_2$-universality
We prove that the neighborhood complex $\N(G)$, the box complex $\B(G)$, the homomorphism complex $\Hom(K_2,G)$and the Lov\'{a}sz complex $\L(G)$ have the same simple $\Z_2$-homotopy type in the sense of Whitehead. We show that these graph complexes are simple $\Z_2$-universal.

Keywords:graph complexes, simple $\Z_2$-homotopy, universality
Categories:57Q10, 05C10, 55P10

32. CMB 2008 (vol 51 pp. 413)

Thé, L. Nguyen Van
Big Ramsey Degrees and Divisibility in Classes of Ultrametric Spaces
Given a countable set $S$ of positive reals, we study finite-dimensional Ramsey-theoretic properties of the countable ultrametric Urysohn space $\textbf{Q} _S$ with distances in $S$.

Keywords:Ramsey theory, Urysohn metric spaces, ultrametric spaces
Categories:05C50, 54E35

33. CMB 2008 (vol 51 pp. 424)

Novelli, Jean-Christophe; Thibon, Jean-Yves
Noncommutative Symmetric Bessel Functions
The consideration of tensor products of $0$-Hecke algebra modules leads to natural analogs of the Bessel $J$-functions in the algebra of noncommutative symmetric functions. This provides a simple explanation of various combinatorial properties of Bessel functions.

Categories:05E05, 16W30, 05A15

34. CMB 2008 (vol 51 pp. 47)

Croot, Ernie
The Minimal Number of Three-Term Arithmetic Progressions Modulo a Prime Converges to a Limit
How few three-term arithmetic progressions can a subset $S \subseteq \Z_N := \Z/N\Z$ have if $|S| \geq \upsilon N$ (that is, $S$ has density at least $\upsilon$)? Varnavides %\cite{varnavides} showed that this number of arithmetic progressions is at least $c(\upsilon)N^2$ for sufficiently large integers $N$. It is well known that determining good lower bounds for $c(\upsilon)> 0$ is at the same level of depth as Erd\" os's famous conjecture about whether a subset $T$ of the naturals where $\sum_{n \in T} 1/n$ diverges, has a $k$-term arithmetic progression for $k=3$ (that is, a three-term arithmetic progression). We answer a question posed by B. Green %\cite{AIM} about how this minimial number of progressions oscillates for a fixed density $\upsilon$ as $N$ runs through the primes, and as $N$ runs through the odd positive integers.


35. CMB 2007 (vol 50 pp. 504)

Dukes, Peter; Ling, Alan C. H.
Asymptotic Existence of Resolvable Graph Designs
Let $v \ge k \ge 1$ and $\lam \ge 0$ be integers. A \emph{block design} $\BD(v,k,\lambda)$ is a collection $\cA$ of $k$-subsets of a $v$-set $X$ in which every unordered pair of elements from $X$ is contained in exactly $\lambda$ elements of $\cA$. More generally, for a fixed simple graph $G$, a \emph{graph design} $\GD(v,G,\lambda)$ is a collection $\cA$ of graphs isomorphic to $G$ with vertices in $X$ such that every unordered pair of elements from $X$ is an edge of exactly $\lambda$ elements of $\cA$. A famous result of Wilson says that for a fixed $G$ and $\lambda$, there exists a $\GD(v,G,\lambda)$ for all sufficiently large $v$ satisfying certain necessary conditions. A block (graph) design as above is \emph{resolvable} if $\cA$ can be partitioned into partitions of (graphs whose vertex sets partition) $X$. Lu has shown asymptotic existence in $v$ of resolvable $\BD(v,k,\lambda)$, yet for over twenty years the analogous problem for resolvable $\GD(v,G,\lambda)$ has remained open. In this paper, we settle asymptotic existence of resolvable graph designs.

Keywords:graph decomposition, resolvable designs
Categories:05B05, 05C70, 05B10

36. CMB 2007 (vol 50 pp. 632)

Zelenyuk, Yevhen; Zelenyuk, Yuliya
Transformations and Colorings of Groups
Let $G$ be a compact topological group and let $f\colon G\to G$ be a continuous transformation of $G$. Define $f^*\colon G\to G$ by $f^*(x)=f(x^{-1})x$ and let $\mu=\mu_G$ be Haar measure on $G$. Assume that $H=\Imag f^*$ is a subgroup of $G$ and for every measurable $C\subseteq H$, $\mu_G((f^*)^{-1}(C))=\mu_H(C)$. Then for every measurable $C\subseteq G$, there exist $S\subseteq C$ and $g\in G$ such that $f(Sg^{-1})\subseteq Cg^{-1}$ and $\mu(S)\ge(\mu(C))^2$.

Keywords:compact topological group, continuous transformation, endomorphism, Ramsey theoryinversion,
Categories:05D10, 20D60, 22A10

37. CMB 2007 (vol 50 pp. 535)

Hohlweg, Christophe
Generalized Descent Algebras
If $A$ is a subset of the set of reflections of a finite Coxeter group $W$, we define a sub-$\ZM$-module $\DC_A(W)$ of the group algebra $\ZM W$. We discuss cases where this submodule is a subalgebra. This family of subalgebras includes strictly the Solomon descent algebra, the group algebra and, if $W$ is of type $B$, the Mantaci--Reutenauer algebra.

Keywords:Coxeter group, Solomon descent algebra, descent set
Categories:20F55, 05E15

38. CMB 2006 (vol 49 pp. 281)

Ragnarsson, Carl Johan; Suen, Wesley Wai; Wagner, David G.
Correction to a Theorem on Total Positivity
A well-known theorem states that if $f(z)$ generates a PF$_r$ sequence then $1/f(-z)$ generates a PF$_r$ sequence. We give two counterexamples which show that this is not true, and give a correct version of the theorem. In the infinite limit the result is sound: if $f(z)$ generates a PF sequence then $1/f(-z)$ generates a PF sequence.

Keywords:total positivity, Toeplitz matrix, Pólya frequency sequence, skew Schur function
Categories:15A48, 15A45, 15A57, 05E05

39. CMB 2005 (vol 48 pp. 445)

Patras, Frédéric; Reutenauer, Christophe; Schocker, Manfred
On the Garsia Lie Idempotent
The orthogonal projection of the free associative algebra onto the free Lie algebra is afforded by an idempotent in the rational group algebra of the symmetric group $S_n$, in each homogenous degree $n$. We give various characterizations of this Lie idempotent and show that it is uniquely determined by a certain unit in the group algebra of $S_{n-1}$. The inverse of this unit, or, equivalently, the Gram matrix of the orthogonal projection, is described explicitly. We also show that the Garsia Lie idempotent is not constant on descent classes (in fact, not even on coplactic classes) in $S_n$.

Categories:17B01, 05A99, 16S30, 17B60

40. CMB 2005 (vol 48 pp. 460)

Sommers, Eric N.
$B$-Stable Ideals in the Nilradical of a Borel Subalgebra
We count the number of strictly positive $B$-stable ideals in the nilradical of a Borel subalgebra and prove that the minimal roots of any $B$-stable ideal are conjugate by an element of the Weyl group to a subset of the simple roots. We also count the number of ideals whose minimal roots are conjugate to a fixed subset of simple roots.

Categories:20F55, 17B20, 05E99

41. CMB 2005 (vol 48 pp. 244)

McLeod, Alice; Moser, William
Counting Multiple Cyclic Choices Without Adjacencies
We give a particularly elementary solution to the following well-known problem. What is the number of $k$-subsets $X \subseteq I_n=\{1,2,3,\dots,n\}$ satisfying ``no two elements of $X$ are adjacent in the circular display of $I_n$''? Then we investigate a new generalization (multiple cyclic choices without adjacencies) and apply it to enumerating a class of 3-line latin rectangles.

Categories:05A19, 05A05

42. CMB 2004 (vol 47 pp. 161)

Alspach, Brian; Du, Shaofei
Suborbit Structure of Permutation $p$-Groups and an Application to Cayley Digraph Isomorphism
Let $P$ be a transitive permutation group of order $p^m$, $p$ an odd prime, containing a regular cyclic subgroup. The main result of this paper is a determination of the suborbits of $P$. The main result is used to give a simple proof of a recent result by J.~Morris on Cayley digraph isomorphisms.

Categories:20B25, 05C60

43. CMB 2002 (vol 45 pp. 537)

44. CMB 2002 (vol 45 pp. 321)

Brenken, Berndt
$C^{\ast}$-Algebras of Infinite Graphs and Cuntz-Krieger Algebras
The Cuntz-Krieger algebra $\mathcal{O}_B$ is defined for an arbitrary, possibly infinite and infinite valued, matrix $B$. A graph $C^{\ast}$-algebra $G^{\ast} (E)$ is introduced for an arbitrary directed graph $E$, and is shown to coincide with a previously defined graph algebra $C^{\ast} (E)$ if each source of $E$ emits only finitely many edges. Each graph algebra $G^{\ast} (E)$ is isomorphic to the Cuntz-Krieger algebra $\mathcal{O}_B$ where $B$ is the vertex matrix of~$E$.

Categories:46LXX, 05C50

45. CMB 2001 (vol 44 pp. 370)

Weston, Anthony
On Locating Isometric $\ell_{1}^{(n)}$
Motivated by a question of Per Enflo, we develop a hypercube criterion for locating linear isometric copies of $\lone$ in an arbitrary real normed space $X$. The said criterion involves finding $2^{n}$ points in $X$ that satisfy one metric equality. This contrasts nicely to the standard classical criterion wherein one seeks $n$ points that satisfy $2^{n-1}$ metric equalities.

Keywords:normed spaces, hypercubes
Categories:46B04, 05C10, 05B99

46. CMB 2000 (vol 43 pp. 385)

Bluskov, I.; Greig, M.; Heinrich, K.
Infinite Classes of Covering Numbers
Let $D$ be a family of $k$-subsets (called blocks) of a $v$-set $X(v)$. Then $D$ is a $(v,k,t)$ covering design or covering if every $t$-subset of $X(v)$ is contained in at least one block of $D$. The number of blocks is the size of the covering, and the minimum size of the covering is called the covering number. In this paper we consider the case $t=2$, and find several infinite classes of covering numbers. We also give upper bounds on other classes of covering numbers.

Categories:05B40, 05D05

47. CMB 2000 (vol 43 pp. 397)

Bonato, Anthony; Cameron, Peter; Delić, Dejan
Tournaments and Orders with the Pigeonhole Property
A binary structure $S$ has the pigeonhole property ($\mathcal{P}$) if every finite partition of $S$ induces a block isomorphic to $S$. We classify all countable tournaments with ($\mathcal{P}$); the class of orders with ($\mathcal{P}$) is completely classified.

Keywords:pigeonhole property, tournament, order
Categories:05C20, 03C15

48. CMB 2000 (vol 43 pp. 108)

Sanders, Daniel P.; Zhao, Yue
On the Entire Coloring Conjecture
The Four Color Theorem says that the faces (or vertices) of a plane graph may be colored with four colors. Vizing's Theorem says that the edges of a graph with maximum degree $\Delta$ may be colored with $\Delta+1$ colors. In 1972, Kronk and Mitchem conjectured that the vertices, edges, and faces of a plane graph may be simultaneously colored with $\Delta+4$ colors. In this article, we give a simple proof that the conjecture is true if $\Delta \geq 6$.

Categories:05C15, 05C10

49. CMB 2000 (vol 43 pp. 3)

Adin, Ron; Blanc, David
Resolutions of Associative and Lie Algebras
Certain canonical resolutions are described for free associative and free Lie algebras in the category of non-associative algebras. These resolutions derive in both cases from geometric objects, which in turn reflect the combinatorics of suitable collections of leaf-labeled trees.

Keywords:resolutions, homology, Lie algebras, associative algebras, non-associative algebras, Jacobi identity, leaf-labeled trees, associahedron
Categories:18G10, 05C05, 16S10, 17B01, 17A50, 18G50

50. CMB 1999 (vol 42 pp. 386)

Polat, Norbert
Minimal Separators
A separator of a connected graph $G$ is a set of vertices whose removal disconnects $G$. In this paper we give various conditions for a separator to contain a minimal one. In particular we prove that every separator of a connected graph that has no thick end, or which is of bounded degree, contains a minimal separator.

   1 2 3    

© Canadian Mathematical Society, 2014 :