Matroid theory

Delta-matroid

In mathematics, a delta-matroid or Δ-matroid is a family of sets obeying an exchange axiom generalizing an axiom of matroids. A non-empty family of sets is a delta-matroid if, for every two sets and in the family, and for every element in their symmetric difference , there exists an such that is in the family. For the basis sets of a matroid, the corresponding exchange axiom requires in addition that and , ensuring that and have the same cardinality. For a delta-matroid, either of the two elements may belong to either of the two sets, and it is also allowed for the two elements to be equal.An alternative and equivalent definition is that a family of sets forms a delta-matroid when the convex hull of its indicator vectors (the analogue of a matroid polytope) has the property that every edge length is either one or the square root of two. Delta-matroids were defined by André Bouchet in 1987.Algorithms for matroid intersection and the matroid parity problem can be extended to some cases of delta-matroids. Delta-matroids have also been used to study constraint satisfaction problems. As a special case, an even delta-matroid is a delta-matroid in which either all sets have even number of elements, or all sets have an odd number of elements. If a constraint satisfaction problem has a Boolean variable on each edge of a planar graph, and if the variables of the edges incident to each vertex of the graph are constrained to belong to an even delta-matroid (possibly a different even delta-matroid for each vertex), then the problem can be solved in polynomial time. This result plays a key role in a characterization of the planar Boolean constraint satisfaction problems that can be solved in polynomial time. (Wikipedia).

Video thumbnail

Joseph Bonin: Delta-matroids as subsystems of sequences of Higgs lifts

Abstract: 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 t

From playlist Combinatorics

Video thumbnail

Foldable Polyhedron 2

Delta-Star is a polyhedral object which I invented in 1996. The type of Delta-Star corresponds to Deltahedrons. It expands and shrinks.

From playlist Handmade geometric toys

Video thumbnail

Kronecker delta and Levi-Civita symbol | Lecture 7 | Vector Calculus for Engineers

Definition of the Kronecker delta and the Levi-Civita symbol (sometimes called the permutation symbol or Levi-Civita tensor). The relationship between the Kronecker delta and the Levi-Civita symbol is discussed. Join me on Coursera: https://www.coursera.org/learn/vector-calculus-engin

From playlist Vector Calculus for Engineers

Video thumbnail

Foldable Polyhedron 1

Delta-Star is a polyhedral object which I invented in 1996. The type of Delta-Star corresponds to Deltahedrons. It expands and shrinks. Especially highly symmetric tetrahedron,octahedron,icosahedron types and hexahedron,decahedron types can transform smoothly.

From playlist Handmade geometric toys

Video thumbnail

Impulse (Delta) Functions

Reviews the intuitive notion of a continuous-time impulse or Dirac delta function and the sifting property. http://AllSignalProcessing.com for more great signal processing content, including concept/screenshot files, quizzes, MATLAB and data files.

From playlist Background Material

Video thumbnail

Calculus 3.03f - Derivative Example 6

Another of example of finding a derivative using the definition of the derivative.

From playlist Calculus Ch 3 - Derivatives

Video thumbnail

Laplace transform of f(t-a)u(t-a), the shifted unit step function

laplace transform of unit step function, Laplace transform of f(t-a)u(t-a), Laplace transform of the shifted unit step function, Laplace transform of f(t)u(t-a), Translation in t theorem, differential equation and laplace transform, www.blackpenredpen.com

From playlist Unit Step Functions & Translation in t (Nagle Sect7.6)

Video thumbnail

Connecting tropical intersection theory with polytope algebra in types A and B by Alex Fink

PROGRAM COMBINATORIAL ALGEBRAIC GEOMETRY: TROPICAL AND REAL (HYBRID) ORGANIZERS Arvind Ayyer (IISc, India), Madhusudan Manjunath (IITB, India) and Pranav Pandit (ICTS-TIFR, India) DATE & TIME: 27 June 2022 to 08 July 2022 VENUE: Madhava Lecture Hall and Online Algebraic geometry is t

From playlist Combinatorial Algebraic Geometry: Tropical and Real (HYBRID)

Video thumbnail

Introduction to the Dirac Delta Function

Please Subscribe here, thank you!!! https://goo.gl/JQ8Nys Introduction to the Dirac Delta Function

From playlist Differential Equations

Video thumbnail

Gyula Pap: Linear matroid matching in the oracle model

Gyula Pap: Linear matroid matching in the oracle model Linear matroid matching is understood as a special case of matroid matching when the matroid is given with a matrix representation. However, for certain examples of linear matroids, the matrix representation is not given, and actuall

From playlist HIM Lectures 2015

Video thumbnail

Lauren Williams - Combinatorics of the amplituhedron

The amplituhedron is the image of the positive Grassmannian under a map in- duced by a totally positive matrix. It was introduced by Arkani-Hamed and Trnka to compute scattering amplitudes in N=4 super Yang Mills. I’ll give a gentle introduction to the amplituhedron, surveying its connecti

From playlist Combinatorics and Arithmetic for Physics: Special Days 2022

Video thumbnail

Nonlinear algebra, Lecture 13: "Polytopes and Matroids ", by Mateusz Michalek

This is the thirteenth lecture in the IMPRS Ringvorlesung, the advanced graduate course at the Max Planck Institute for Mathematics in the Sciences.

From playlist IMPRS Ringvorlesung - Introduction to Nonlinear Algebra

Video thumbnail

The Two-Dimensional Discrete Fourier Transform

The two-dimensional discrete Fourier transform (DFT) is the natural extension of the one-dimensional DFT and describes two-dimensional signals like images as a weighted sum of two dimensional sinusoids. Two-dimensional sinusoids have a horizontal frequency component and a vertical frequen

From playlist Fourier

Video thumbnail

Yusuke Kobayashi: A weighted linear matroid parity algorithm

The lecture was held within the framework of the follow-up workshop to the Hausdorff Trimester Program: Combinatorial Optimization. Abstract: The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so gener

From playlist Follow-Up-Workshop "Combinatorial Optimization"

Video thumbnail

Victor Chepoi: Simple connectivity, local to global, and matroids

Victor Chepoi: Simple connectivity, local-to-global, and matroids A basis graph of a matroid M is the graph G(M) having the bases of M as the vertex-set and the pairs of bases differing by an elementary exchange as edges. Basis graphs of matroids have been characterized by S.B. Maurer, J.

From playlist HIM Lectures 2015

Video thumbnail

Anna De Mier: Approximating clutters with matroids

Abstract: 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 Λ, which are the matroidal clutters that are closest

From playlist Combinatorics

Video thumbnail

Zoltán Szigeti: Packing of arborescences with matroid constraints via matroid intersection

The lecture was held within the framework of the follow-up workshop to the Hausdorff Trimester Program: Combinatorial Optimization. Abstract: Edmonds characterized digraphs having a packing of k spanning arborescences in terms of connectivity and later in terms of matroid intersection. D

From playlist Follow-Up-Workshop "Combinatorial Optimization"

Video thumbnail

Cynthia Vinzant: Log concave polynomials and matroids

Strong log concavity is a functional property of a real multivariate polynomial that translates to useful conditions on its coefficients and features in the polynomials defining several common conic programs. Recent work by several independent authors shows that the multivariate basisgener

From playlist Workshop: Tropical geometry and the geometry of linear programming

Video thumbnail

Numerical Differentiation: Second Derivatives and Differentiating Data

This video explores how to numerically compute second derivatives and how to differentiate vectors of data. Examples are given in Python and Matlab. Playlist: https://www.youtube.com/playlist?list=PLMrJAkhIeNNTYaOnVI3QpH7jgULnAmvPA Course Website: http://faculty.washington.edu/sbrunton

From playlist Engineering Math: Differential Equations and Dynamical Systems

Related pages

Matroid polytope | Constraint satisfaction problem | Convex hull | Symmetric difference | Indicator vector | Matroid intersection | Family of sets | Matroid parity problem | Matroid