Let P be the Gelfand–Tsetlin polytope defined by the skew shape λ/μ and weight w. In the case corresponding to a standard Young tableau, we completely characterize for which shapes λ/μ the polytope P ...is integral. Furthermore, we show that P is a compressed polytope whenever it is integral and corresponds to a standard Young tableau. We conjecture that a similar property holds for arbitrary w, namely that P has the integer decomposition property whenever it is integral.
Finally, a natural partial ordering on GT-polytopes is introduced that provides information about integrality and the integer decomposition property, which implies the conjecture for certain shapes.
We introduce k-stellated spheres and consider the class Wk(d) of triangulated d-manifolds, all of whose vertex links are k-stellated, and its subclass Wk∗(d), consisting of the (k+1)-neighbourly ...members of Wk(d). We introduce the mu-vector of any simplicial complex and show that, in the case of 2-neighbourly simplicial complexes, the mu-vector dominates the vector of Betti numbers componentwise; the two vectors are equal precisely for tight simplicial complexes. We are able to estimate/compute certain alternating sums of the components of the mu-vector of any 2-neighbourly member of Wk(d) for d≥2k. As a consequence of this theory, we prove a lower bound theorem for such triangulated manifolds, and we determine the integral homology type of members of Wk∗(d) for d≥2k+2. As another application, we prove that, when d≠2k+1, all members of Wk∗(d) are tight. We also characterize the tight members of Wk∗(2k+1) in terms of their kth Betti numbers. These results more or less answer a recent question of Effenberger, and also provide a uniform and conceptual tightness proof for all except two of the known tight triangulated manifolds.
We also prove a lower bound theorem for homology manifolds in which the members of W1(d) provide the equality case. This generalizes a result (the d=4 case) due to Walkup and Kühnel. As a consequence, it is shown that every tight member of W1(d) is strongly minimal, thus providing substantial evidence in favour of a conjecture of Kühnel and Lutz asserting that tight homology manifolds should be strongly minimal.
Let
H
=
(
V
,
E
)
be a hypergraph with vertex set
V
and edge set
E
of order
n
H
=
|
V
|
and size
m
H
=
|
E
|
. A transversal in
H
is a subset of vertices in
H
that has a nonempty intersection with ...every edge of
H
. The transversal number
τ
(
H
)
of
H
is the minimum size of a transversal in
H
. A dominating set in
H
is a subset of vertices
D
⊆
V
such that for every vertex
v
∈
V
∖
D
there exists an edge
e
∈
E
for which
v
∈
e
and
e
∩
D
≠
0̸
. The domination number
γ
(
H
)
is the minimum cardinality of a dominating set in
H
. A hypergraph
H
is
k
-uniform if every edge of
H
has size
k
. We establish the following relationship between the transversal number and the domination number of uniform hypergraphs. For any two nonnegative reals
a
and
b
and for every integer
k
≥
3
the equality
sup
H
∈
H
k
γ
(
H
)
/
(
a
n
H
+
b
m
H
)
=
sup
H
∈
H
k
−
1
τ
(
H
)
/
(
a
n
H
+
(
a
+
b
)
m
H
)
holds, where
H
k
denotes the class of all
k
-uniform hypergraphs containing no isolated vertices. As a consequence of this result, we establish upper bounds on the domination number of a
k
-uniform hypergraph with minimum degree at least 1. In particular, we show that if
k
≥
3
, then
γ
(
H
)
≤
(
n
H
+
⌊
k
−
3
2
⌋
m
H
)
/
⌊
3
(
k
−
1
)
2
⌋
for all
H
∈
H
k
, and this bound is sharp. More generally, for
k
=
2
and
k
=
3
we prove that all the essential upper bounds can be written in the unified form
γ
(
H
)
≤
(
a
n
H
+
b
m
H
)
/
(
a
k
+
b
)
for constants
b
≥
0
and
a
>
−
b
/
k
.
► Let
H
be a hypergraph with
n
H
vertices and
m
H
edges. ► Let
H
k
be the class of
k
-uniform hypergraphs containing no isolated vertices. ► Let
τ
(
H
)
and
γ
(
H
)
denote the transversal number and domination number of
H
, respectively. ► For
k
≥
3
an integer and for reals
a
,
b
≥
0
, the equality
sup
H
∈
H
k
γ
(
H
)
/
(
a
n
H
+
b
m
H
)
=
sup
H
∈
H
k
−
1
τ
(
H
)
/
(
a
n
H
+
(
a
+
b
)
m
H
)
holds.
Nous étudions la possibilité de recouvrir certains graphes par des chaînes Hamiltoniennes. Nous appliquons les résultats obtenus au cas particulier du graphe divisoriel pour obtenir des réponses ...nouvelles à un problème posé par P. Erdös.
We study the possibility of covering some graphs with Hamiltonian chains. The results are applied to the particular case of the divisorial graph to give some new answers to a question asked by P. Erdös.
An upper bound on permutation codes of lengthnis given. This bound is a solution of a certain linear programming problem and is based on the well-developed theory of association schemes. Several ...examples are presented. For instance, the 255 values of the bound forn≤ 8 are tabulated. It turns out that, forn≤ 8, the Kiyota bound for group codes also holds for unrestricted codes at least in 178 cases. Also an easier (but weaker) polynomial version of the bound is given. It is obtained by showing that the mappingsFk(θ) (0≤k≤n/2), whereFkis the Charlier polynomial of degreekand θ the natural character of the symmetric groupSn, are mutually orthogonal characters ofSn.
La correspondance de Robinson–Schensted envoie une permutation sur une paire de tableaux standard de Young de même forme. La forme de ces deux tableaux est aussi appellée
forme de la permutation. ...Récemment, à l’aide de la théorie de Kazhdan–Luszitg, Hohlweg a caractérisé les permutations ayant le nombre d’inversions minimal sur l’ensemble des permutations de forme fixée. Dans cette Note on montre, par un argument combinatoire, que cette caractérisation est une conséquence de l’algorithme géométrique que Viennot avait construit pour la correspondance de Robinson–Schensted.
The Robinson–Schensted correspondence maps a permutation onto a pair of standard Young tableaux of the same shape. The shape of the two tableaux is referred to as the
shape of the permutation. By using the theory of Kazhdan–Luszitg, Hohlweg has recently characterized the permutations with a fixed shape and a minimal inversion number. The present note provides a combinatorial proof of this result by using Viennot’s geometric algorithm of the Robinson–Schensted correspondence.
Treillis de codes quasi-cycliques Bracco, Anne Desideri
European journal of combinatorics,
05/2004, Volume:
25, Issue:
4
Journal Article
Peer reviewed
Open access
Nous présentons une construction graphique de codes quasi-cycliques. Cette construction par treillis généralise la construction cubique de Forney et elle correspond à un cas particulier de I’approche ...algébrique proposée par Ling et Solé. Des codes binaires auto-duaux et extrêmaux de paramètres 24, 12, 8, 40, 20, 8 et 72, 36, 12 sont contruits en exemple.
PDF