En poursuivant votre navigation sur ce site, vous acceptez l'utilisation d'un simple cookie d'identification. Aucune autre exploitation n'est faite de ce cookie. OK

Documents 05B35 8 résultats

Filtrer
Sélectionner : Tous / Aucun
Q
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y

Approximating clutters with matroids - De Mier, Anna (Auteur de la Conférence) | CIRM H

Multi angle

There are several clutters (antichains of sets) that can be associated with a matroid, as the clutter of circuits, the clutter of bases or the clutter of hyperplanes. We study the following question: given an arbitrary clutter $\Lambda$, which are the matroidal clutters that are closest to $\Lambda$? To answer it we first decide on the meaning of closest, and select one of the different matroidal clutters.

We show that for almost all reasonable choices above there is a finite set of matroidal clutters that approximate $\Lambda$ and, moreover, that $\Lambda$ can be recovered from them by a suitable operation. We also link our work to results in lattice theory, and give algorithmic procedures to compute the approximations. We are also interested in the same questions when we further require that both the original clutter and the matroidal approximations have the same ground set. In this situation, it is often the case that $\Lambda$ cannot be recovered by the approximating matroidal clutters (if they exist), but we can characterize when it does.

Although our initial interest was in matroids, our framework is general and applies in any situation when one wishes to decompose the clutter $\Lambda$ with members of a favourite family of clutters, not necessarily a matroidal one.
(Joint work with Jaume Martí-Farré and José Luis Ruiz.)[-]
There are several clutters (antichains of sets) that can be associated with a matroid, as the clutter of circuits, the clutter of bases or the clutter of hyperplanes. We study the following question: given an arbitrary clutter $\Lambda$, which are the matroidal clutters that are closest to $\Lambda$? To answer it we first decide on the meaning of closest, and select one of the different matroidal clutters.

We show that for almost all reasonable ...[+]

05B35

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y
Delta-matroids generalize matroids. In a delta-matroid, the counterparts of bases, which are called feasible sets, can have different sizes, but they satisfy a similar exchange property in which symmetric differences replace set differences. One way to get a delta-matroid is to take a matroid L, a quotient Q of L, and all of the Higgs lifts of Q toward L; the union of the sets of bases of these Higgs lifts is the collection of feasible sets of a delta-matroid, which we call a full Higgs lift delta-matroid.

We give an excluded-minor characterization of full Higgs lift delta-matroids within the class of all delta-matroids. We introduce a class of full Higgs lift delta-matroids that arise from lattice paths and that generalize lattice path matroids. It follows from results of Bouchet that all delta-matroids can be obtained from full Higgs lift delta-matroids by removing certain feasible sets; to address which feasible sets can be removed, we give an excluded-minor characterization of delta-matroids within the more general structure of set systems. This result in turn yields excluded-minor characterizations of a number of related classes of delta-matroids.
(This is joint work with Carolyn Chun and Steve Noble.)[-]
Delta-matroids generalize matroids. In a delta-matroid, the counterparts of bases, which are called feasible sets, can have different sizes, but they satisfy a similar exchange property in which symmetric differences replace set differences. One way to get a delta-matroid is to take a matroid L, a quotient Q of L, and all of the Higgs lifts of Q toward L; the union of the sets of bases of these Higgs lifts is the collection of feasible sets of a ...[+]

05B35

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y

A matroid extension result - Oxley, James G. (Auteur de la Conférence) | CIRM H

Multi angle

Let $(A,B)$ be a $3$-separation in a matroid $M$. If $M$ is representable, then, in the underlying projective space, there is a line where the subspaces spanned by $A$ and $B$ meet, and $M$ can be extended by adding elements from this line. In general, Geelen, Gerards, and Whittle proved that $M$ can be extended by an independent set $\{p,q\}$ such that $\{p,q\}$ is in the closure of each of $A$ and $B$. In this extension, each of $p$ and $q$ is freely placed on the line $L$ spanned by $\{p,q\}$. This talk will discuss a result that gives necessary and sufficient conditions under which a fixed element can be placed on $L$.[-]
Let $(A,B)$ be a $3$-separation in a matroid $M$. If $M$ is representable, then, in the underlying projective space, there is a line where the subspaces spanned by $A$ and $B$ meet, and $M$ can be extended by adding elements from this line. In general, Geelen, Gerards, and Whittle proved that $M$ can be extended by an independent set $\{p,q\}$ such that $\{p,q\}$ is in the closure of each of $A$ and $B$. In this extension, each of $p$ and $q$ is ...[+]

05B35

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y
Some problems connected with the concatenation operation will be described.

05B35 ; 52C40

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y

Tverberg-type theorems with altered nerves - De Loera, Jesus A. (Auteur de la Conférence) | CIRM H

Multi angle

The classical Tverberg's theorem says that a set with sufficiently many points in $R^d$ can always be partitioned into m parts so that the (m - 1)-simplex is the (nerve) intersection pattern of the convex hulls of the parts. Our main results demonstrate that Tverberg's theorem is but a special case of a much more general situation. Given sufficiently many points, any tree or cycle, can also be induced by at least one partition of the point set. The proofs require a deep investigation of oriented matroids and order types.
(Joint work with Deborah Oliveros, Tommy Hogan, Dominic Yang (supported by NSF).)[-]
The classical Tverberg's theorem says that a set with sufficiently many points in $R^d$ can always be partitioned into m parts so that the (m - 1)-simplex is the (nerve) intersection pattern of the convex hulls of the parts. Our main results demonstrate that Tverberg's theorem is but a special case of a much more general situation. Given sufficiently many points, any tree or cycle, can also be induced by at least one partition of the point set. ...[+]

05B35 ; 52C40

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y

How many cubes are orientable? - Da Silva, Ilda P. F. (Auteur de la Conférence) | CIRM H

Multi angle

A cube is a matroid over $C^n=\{-1,+1\}^n$ that contains as circuits the usual rectangles of the real affine cube packed in such a way that the usual facets and skew-facets are hyperplanes of the matroid.
How many cubes are orientable? So far, only one: the oriented real affine cube. We review the results obtained so far concerning this question. They follow two directions:
1) Identification of general obstructions to orientability in this class. (da Silva, EJC 30 (8), 2009, 1825-1832).
2) (work in collaboration with E. Gioan) Identification of algebraic and geometric properties of recursive families of non-negative integer vectors defining hyperplanes of the real affine cube and the analysis of this question and of las Vergnas cube conjecture in small dimensions.[-]
A cube is a matroid over $C^n=\{-1,+1\}^n$ that contains as circuits the usual rectangles of the real affine cube packed in such a way that the usual facets and skew-facets are hyperplanes of the matroid.
How many cubes are orientable? So far, only one: the oriented real affine cube. We review the results obtained so far concerning this question. They follow two directions:
1) Identification of general obstructions to orientability in this ...[+]

05B35 ; 52A37 ; 52C40

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y

Generalizations of Crapo's Beta Invariant - Gordon, Gary (Auteur de la Conférence) ; McMahon, Liz (Auteur de la Conférence) | CIRM H

Multi angle

Crapo's beta invariant was defined by Henry Crapo in the 1960s. For a matroid $M$, the invariant $\beta(M)$ is the non-negative integer that is the coefficient of the $x$ term of the Tutte polynomial. Crapo proved that $\beta(M)>0$ if and only if $M$ is connected and $M$ is not a loop, and Brylawski proved that $M$ is the matroid of a series-parallel network if and only if $M$ is a co-loop or $\beta(M)=1.$ In this talk, we present several generalizations of the beta invariant to combinatorial structures that are not matroids. We concentrate on posets, chordal graphs, and finite subsets of Euclidean space. In each case, our definition of $\beta$ measures the number of "interior'' elements.[-]
Crapo's beta invariant was defined by Henry Crapo in the 1960s. For a matroid $M$, the invariant $\beta(M)$ is the non-negative integer that is the coefficient of the $x$ term of the Tutte polynomial. Crapo proved that $\beta(M)>0$ if and only if $M$ is connected and $M$ is not a loop, and Brylawski proved that $M$ is the matroid of a series-parallel network if and only if $M$ is a co-loop or $\beta(M)=1.$ In this talk, we present several ...[+]

05B35

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y
In general the computation of the weight enumerator of a code is hard and even harder so for the coset leader weight enumerator. Generalized Reed Solomon codes are MDS, so their weight enumerators are known and its formulas depend only on the length and the dimension of the code. The coset leader weight enumerator of an MDS code depends on the geometry of the associated projective system of points. We consider the coset leader weight enumerator of $F_{q}$-ary Generalized Reed Solomon codes of length q + 1 of small dimensions, so its associated projective system is a normal rational curve. For instance in case of the $\left [ q+1,3,q-1 \right ]_{q}$ code where the associated projective system of points consists of the q + 1 points of a plane conic, the answer depends whether the characteristic is odd or even. If the associated projective system of points of a $\left [ q+1,4,q-2 \right ]_{q}$ code consists of the q + 1 points of a twisted cubic, the answer depends on the value of the characteristic modulo 6.[-]
In general the computation of the weight enumerator of a code is hard and even harder so for the coset leader weight enumerator. Generalized Reed Solomon codes are MDS, so their weight enumerators are known and its formulas depend only on the length and the dimension of the code. The coset leader weight enumerator of an MDS code depends on the geometry of the associated projective system of points. We consider the coset leader weight enumerator ...[+]

94B05 ; 94B27 ; 14H50 ; 05B35

Sélection Signaler une erreur