In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory equivalent to the statement that a Cartesian product of a collection of non-empty sets is non-empty. Informally put, the axiom of choice says that given any collection of sets, each containing at least one element, it is possible to construct a new set by choosing one element from each set, even if the collection is infinite. Formally, it states that for every indexed family of nonempty sets, there exists an indexed set such that for every . The axiom of choice was formulated in 1904 by Ernst Zermelo in order to formalize his proof of the well-ordering theorem.
In mathematics, the Hausdorff maximal principle is an alternate and earlier formulation of Zorn's lemma proved by Felix Hausdorff in 1914. It states that in any partially ordered set, every totally ordered subset is contained in a maximal totally ordered subset, where "maximal" is with respect to set inclusion.
Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory. It states that a partially ordered set containing upper bounds for every chain necessarily contains at least one maximal element.
Arrow's impossibility theorem is a key result in social choice, discovered by Kenneth Arrow, showing that no ranked voting rule can behave rationally. Specifically, any such rule violates independence of irrelevant alternatives (IIA), the idea that a choice between and should not depend on the quality of a third, unrelated option . The result is most often cited in election science and voting theory, where is called a spoiler candidate. In this context, Arrow's theorem can be restated as showing that no ranked voting rule can eliminate the spoiler effect.
The Smith or Schwartz set, sometimes called the top-cycle, generalizes the idea of a Condorcet winner to cases where no such winner exists. It does so by allowing cycles of candidates to be treated jointly, as if they were a single Condorcet winner.
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
In combinatorics, a greedoid is a type of set system. It arises from the notion of the matroid, which was originally introduced by Whitney in 1935 to study planar graphs and was later used by Edmonds to characterize a class of optimization problems that can be solved by greedy algorithms. Around 1980, Korte and Lovász introduced the greedoid to further generalize this characterization of greedy algorithms; hence the name greedoid. Besides mathematical optimization, greedoids have also been connected to graph theory, language theory, order theory, and other areas of mathematics.
In combinatorics, an abstract simplicial complex (ASC), often called an abstract complex or just a complex, is a family of sets that is closed under taking subsets, i.e., every subset of a set in the family is also in the family. It is a purely combinatorial description of the geometric notion of a simplicial complex. For example, in a 2-dimensional simplicial complex, the sets in the family are the triangles, their edges, and their vertices.
In an election, a candidate is called a majority winner or majority-preferred candidate if more than half of all voters would support them in a one-on-one race against any one of their opponents. Voting systems where a majority winner will always win are said to satisfy the majority-rule principle, because they extend the principle of majority rule to elections with multiple candidates.
In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that:
Any set of d + 2 points in Rd can be partitioned into two sets whose convex hulls intersect.
In graph theory, a tournament is a directed graph with exactly one edge between each two vertices, in one of the two possible directions. Equivalently, a tournament is an orientation of an undirected complete graph. The name tournament comes from interpreting the graph as the outcome of a round-robin tournament, a game where each player is paired against every other exactly once. In a tournament, the vertices represent the players, and the edges between players point from the winner to the loser.
Social choice theory is a branch of welfare economics that analyzes methods of combining individual opinions, beliefs, or preferences to reach a collective decision or create measures of social well-being. It contrasts with political science in that it is a normative field that studies how societies should make decisions, whereas political science is descriptive. Social choice incorporates insights from economics, mathematics, philosophy, political science, and game theory to find the best ways to combine individual preferences into a coherent whole, called a social welfare function.
In the study of electoral systems, the uncovered set is a set of candidates that generalizes the notion of a Condorcet winner whenever there is a Condorcet paradox. The Landau set can be thought of as the Pareto frontier for a set of candidates, when the frontier is determined by pairwise victories.
In graph theory and statistics, a graphon is a symmetric measurable function , that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs.
In functional analysis, a branch of mathematics, a selection theorem is a theorem that guarantees the existence of a single-valued selection function from a given set-valued map. There are various selection theorems, and they are important in the theories of differential inclusions, optimal control, and mathematical economics.
In cooperative game theory and social choice theory, the Nakamura number measures the degree of rationality of preference aggregation rules, such as voting rules. It is an indicator of the extent to which an aggregation rule can yield well-defined choices.
In the mathematics of infinite graphs, an end of a graph represents, intuitively, a direction in which the graph extends to infinity. Ends may be formalized mathematically as equivalence classes of infinite paths, as havens describing strategies for pursuit–evasion games on the graph, or as topological ends of topological spaces associated with the graph.
In the mathematical theory of matroids, the rank of a matroid is the maximum size of an independent set in the matroid. The rank of a subset S of elements of the matroid is, similarly, the maximum size of an independent subset of S, and the rank function of the matroid maps sets of elements to their ranks.
Maximal lotteries refers to a probabilistic voting rule. The method uses preferential ballots and returns a probability distribution of candidates that a majority of voters would weakly prefer to any other.
In computational complexity theory, a planted clique or hidden clique in an undirected graph is a clique formed from another graph by selecting a subset of vertices and adding edges between each pair of vertices in the subset. The planted clique problem is the algorithmic problem of distinguishing random graphs from graphs that have a planted clique. This is a variation of the clique problem; it may be solved in quasi-polynomial time but is conjectured not to be solvable in polynomial time for intermediate values of the clique size. The conjecture that no polynomial time solution exists is called the planted clique conjecture; it has been used as a computational hardness assumption.
Mathematicsportal 
![A tournament on 4 vertices:
A
=
{
1
,
2
,
3
,
4
}
{\displaystyle A=\{1,2,3,4\}}
,
[?]=
{
(
1
,
2
)
,
(
1
,
4
)
,
(
2
,
4
)
,
{\displaystyle \succ =\{(1,2),(1,4),(2,4),}
(
3
,
1
)
,
(
3
,
2
)
,
(
4
,
3
)
}
{\displaystyle (3,1),(3,2),(4,3)\}} 4-tournament.svg](http://upload.wikimedia.org/wikipedia/commons/thumb/8/89/4-tournament.svg/220px-4-tournament.svg.png)
