Cartesian product

Summary

In mathematics, specifically set theory, the Cartesian product of two sets A and B, denoted A × B, is the set of all ordered pairs (a, b) where a is in A and b is in B. In terms of set-builder notation, that is : A\times B = {(a,b)\mid a \in A \ \mbox{ and } \ b \in B}. A table can be created by taking the Cartesian product of a set of rows and a set of columns. If the Cartesian product rows × columns is taken, the cells of the table contain ordered pairs of the form (row value, column value). One can similarly define the Cartesian product of n sets, also known as an n-fold Cartesian product, which can be represented by an n-dimensional array, where each element is an n-tuple. An ordered pair is a 2-tuple or couple. More generally still, one can define the Cartesian product of an indexed family of sets. The Cartesian product is named after René Descartes, whose formulation

Official source

https://en.wikipedia.org/wiki/Cartesian_product

About this result

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 (7)

Related publications

Related people

Related units

Related concepts (74)

Related concepts

Related courses (27)

Related courses

Related lectures (52)

Related lectures

Polynomials Vanishing On Cartesian Products: The Elekes-Szabo Theorem Revisited

Frank de Zeeuw

Let F 2 C[x; y; z] be a constant-degree polynomial, and let A; B; C subset of C be finite sets of size n. We show that F vanishes on at most O(n(11/6))points of the Cartesian product A X B X C, unless F has a special group-related form. This improves a theorem of Elekes and Szab and generalizes a result of Raz, Sharir, and Solymosi. The same statement holds over R, and a similar statement holds when A; B; C have different sizes (with a more involved bound replacing O(n(11/6)). This result provides a unified tool for improving bounds in various Erdos-type problems in combinatorial geometry, and we discuss several applications of this kind.

Duke Univ Press2016

Many problems in combinatorial geometry can be formulated in terms of curves or surfaces containing many points of a cartesian product. In 2000, Elekes and Rónyai proved that if the graph of a polynomial f(x, y) contains cn2 points of an n × n × n cartesian product in R3, then the polynomial has one of the forms f(x, y) = g(k(x) + l(y)) or f(x, y) = g(k(x)l(y)). They used this to prove a conjecture of Purdy which states that given two lines in R2 and n points on each line, if the number of distinct distances between pairs of points, one on each line, is at most cn, then the lines are parallel or orthogonal. We extend the Elekes-Rónyai Theorem to a less symmetric cartesian product. This leads to a proof of Purdy's conjecture with significantly fewer points on one of the lines. We also extend the Elekes-Rónyai Theorem to n × n × n × n cartesian products, again with an asymmetric version. We finish with a lower bound which shows that our result for asymmetric cartesian products in four dimensions is near-optimal. © 2013 Elsevier Inc.

Elsevier2013

Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration

Javad Ebrahimi Boroojeni, Damian Mateusz Straszak, Nisheeth Vishnoi

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.

Ieee2017

Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration

Javad Ebrahimi Boroojeni, Damian Mateusz Straszak, Nisheeth Vishnoi

Ieee2017