**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Partition of a set

Summary

In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that every element is included in exactly one subset.
Every equivalence relation on a set defines a partition of this set, and every partition defines an equivalence relation. A set equipped with an equivalence relation or a partition is sometimes called a setoid, typically in type theory and proof theory.
Definition and notation
A partition of a set X is a set of non-empty subsets of X such that every element x in X is in exactly one of these subsets (i.e., the subsets are nonempty mutually disjoint sets).
Equivalently, a family of sets P is a partition of X if and only if all of the following conditions hold:
*The family P does not contain the empty set (that is \emptyset \notin P).
*The union of the sets in P is equal to X (that is \textstyle\bigcup_{A\in P} A = X). The sets in P are said to exhaust or cover X. See also collectively exh

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related people

Related units

No results

No results

Related publications (2)

Loading

Loading

Related concepts (22)

Combinatorics

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many

Equivalence relation

In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equiva

Set (mathematics)

A set is the mathematical model for a collection of different things; a set contains elements or members, which can be mathematical objects of any kind: numbers, symbols, points

Related lectures (21)

Related courses (13)

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, discrete structures & algorithmic thinking.

MATH-101(g): Analysis I

Étudier les concepts fondamentaux d'analyse et le calcul différentiel et intégral des fonctions réelles d'une variable.

MATH-110(a): Advanced linear algebra I

L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et de démontrer rigoureusement les résultats principaux de ce sujet.

, ,

Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors v(1), ..., v(m) is an element of R-d and a constraint family B subset of 2([m]), find a set S. B that maximizes the squared volume of the simplex spanned by the vectors in S. A motivating example is the ubiquitous data-summarization problem in machine learning and information retrieval where one is given a collection of feature vectors that represent data such as documents or images. The volume of a collection of vectors is used as a measure of their diversity, and partition or matroid constraints over [m] are imposed in order to ensure resource or fairness constraints. Even with a simple cardinality constraint (B = (([m])(r))), the problem becomes NP-hard and has received much attention starting with a result by Khachiyan [1] who gave an r(O(r)) approximation algorithm for this problem. Recently, Nikolov and Singh [2] presented a convex program and showed how it can be used to estimate the value of the most diverse set when there are multiple cardinality constraints (i.e., when B corresponds to a partition matroid). Their proof of the integrality gap of the convex program relied on an inequality by Gurvits [3], and was recently extended to regular matroids [4], [5]. The question of whether these estimation algorithms can be converted into the more useful approximation algorithms - that also output a set - remained open. The main contribution of this paper is to give the first approximation algorithms for both partition and regular matroids. We present novel formulations for the subdeterminant maximization problem for these matroids; this reduces them to the problem of finding a point that maximizes the absolute value of a nonconvex function over a Cartesian product of probability simplices. The technical core of our results is a new anti-concentration inequality for dependent random variables that arise from these functions which allows us to relate the optimal value of these nonconvex functions to their value at a random point. Unlike prior work on the constrained subdeterminant maximization problem, our proofs do not rely on real-stability or convexity and could be of independent interest both in algorithms and complexity where anti-concentration phenomena has recently been deployed.

Rate and diversity impose a fundamental trade-off in wireless communication. High-rate space-time codes come at a cost of lower reliability (diversity), and high reliability (diversity) implies a lower rate. However, wireless networks need to support applications with very different Quality-of-Service (QoS) requirements, and it is natural to ask what characteristics should be built into the physical layer link in order to accomodate them. In this paper we de- sign high-rate space-time codes that have a high-diversity code embedded within them. This allows a form of communication where the high-rate code opportunistically takes advantage of good channel realizations while the embedded high-diversity code provides guarantees that at least part of the information is received reliably. We provide constructions of linear and non-linear codes for a fixed transmit alphabet constraint. The non-linear constructions are a natural generalization to wireless channels of multilevel codes developed for the AWGN chan- nel that are matched to binary partitions of QAM and PSK constellations. The importance of set-partitioning to code design for the wireless channel is that it provides a mechanism for translating constraints in the binary domain into lower bounds on diversity protection in the complex domain. We investigate the systems implications of embedded diversity codes by examining value to unequal error protection, rate opportunism and packet delay optimiza- tion. These applications demonstrate that diversity-embedded codes have the potential to outperform traditional single-layer codes in moderate SNR regimes.

2008