Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Dimension bipartie

Publications associées (25)

Minimum d-blockers and d-transversals in graphs

Dominique de Werra

We consider a set V of elements and an optimization problem on V: the search for a maximum (or minimum) cardinality subset of V verifying a given property a"similar to. A d-transversal is a subset of V which intersects any optimum solution in at least d el ...

2011

Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid

Dominique de Werra, Bernard Ries

Given an undirected graph G = (V, E) with matching number nu(G), a d-blocker is a subset of edges B such that nu((V, E \ B))

Elsevier2010

A bipartite strengthening of the Crossing Lemma

János Pach

Let G = (V, E) be a graph with n vertices and m >= 4n edges drawn in the plane. The celebrated Crossing Lemma states that G has at least Omega(m(3)/n(2)) pairs of crossing edges; or equivalently, there is an edge that crosses Omega(m(2)/n(2)) other edges. ...

Elsevier2010

A separator theorem for string graphs and its applications

János Pach

A string graph is the intersection graph of a collection of continuous arcs in the plane. We show that any string graph with in edges can be separated into two parts of roughly equal size by the removal of O(m(3/4)root log m) vertices. This result is then ...

Cambridge University Press2010

Three-Sublattice Ordering of the SU(3) Heisenberg Model of Three-Flavor Fermions on the Square and Cubic Lattices

Frédéric Mila

Combining a semiclassical analysis with exact diagonalizations, we show that the ground state of the SU(3) Heisenberg model on the square lattice develops three-sublattice long-range order. This surprising pattern for a bipartite lattice with only nearest- ...

2010