Expand all Collapse all | Results 26 - 50 of 55 |
26. 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 |
27. CMB 2009 (vol 53 pp. 171)
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 |
28. CMB 2009 (vol 53 pp. 378)
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 Category:05C70 |
29. CMB 2009 (vol 52 pp. 416)
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 |
30. CMB 2009 (vol 52 pp. 451)
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 |
31. CMB 2008 (vol 51 pp. 584)
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 |
32. CMB 2008 (vol 51 pp. 535)
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 |
33. CMB 2008 (vol 51 pp. 413)
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 |
34. CMB 2008 (vol 51 pp. 424)
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 |
35. CMB 2008 (vol 51 pp. 47)
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.
Category:05D99 |
36. CMB 2007 (vol 50 pp. 504)
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 |
37. CMB 2007 (vol 50 pp. 632)
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 |
38. CMB 2007 (vol 50 pp. 535)
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 |
39. CMB 2006 (vol 49 pp. 281)
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 |
40. CMB 2005 (vol 48 pp. 445)
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 |
41. CMB 2005 (vol 48 pp. 460)
$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 |
42. CMB 2005 (vol 48 pp. 244)
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 |
43. CMB 2004 (vol 47 pp. 161)
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 |
44. CMB 2002 (vol 45 pp. 537)
45. CMB 2002 (vol 45 pp. 321)
$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 |
46. CMB 2001 (vol 44 pp. 370)
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 |
47. CMB 2000 (vol 43 pp. 397)
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. 385)
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 |
49. CMB 2000 (vol 43 pp. 108)
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 |
50. CMB 2000 (vol 43 pp. 3)
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 |