|
Meshulam's Game
In graph theory, Meshulam's game is a game used to explain a theorem of Roy Meshulam related to the homological connectivity of the independence complex of a graph, which is the smallest index ''k'' such that all reduced homological groups up to and including ''k'' are trivial. The formulation of this theorem as a game is due to Aharoni, Berger and Ziv. Description The game-board is a graph ''G.'' It is a zero-sum game for two players, CON and NON. CON wants to show that I(''G''), the independence complex of ''G'', has a high connectivity; NON wants to prove the opposite. At his turn, CON chooses an edge ''e'' from the remaining graph. NON then chooses one of two options: * ''Disconnection'' – remove the edge ''e'' from the graph. * ''Explosion'' – remove both endpoints of ''e'', together with all their neighbors and the edges incident to them. The score of CON is defined as follows: * If at some point the remaining graph has an isolated vertex, the score is infinity; * O ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are connected by '' edges'' (also called ''links'' or ''lines''). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics. Definitions Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures. Graph In one restricted but very common sense of the term, a graph is an ordered pair G=(V,E) comprising: * V, a set of vertices (also called nodes or points); * E \subseteq \, a set of edges (also called links or lines), which are unordered pairs of vertices (that is, an edge is associated with t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Homological Connectivity
In algebraic topology, homological connectivity is a property describing a topological space based on its homology groups. Definitions Background ''X'' is ''homologically-connected'' if its 0-th homology group equals Z, i.e. H_0(X)\cong \mathbb, or equivalently, its 0-th reduced homology group is trivial: \tilde(X)\cong 0. * For example, when ''X'' is a graph and its set of connected components is ''C'', H_0(X)\cong \mathbb^ and \tilde(X)\cong \mathbb^ (see graph homology). Therefore, homological connectivity is equivalent to the graph having a single connected component, which is equivalent to graph connectivity. It is similar to the notion of a connected space. ''X'' is ''homologically 1-connected'' if it is homologically-connected, and additionally, its 1-th homology group is trivial, i.e. H_1(X)\cong 0. * For example, when ''X'' is a connected graph with vertex-set ''V'' and edge-set ''E'', H_1(X) \cong \mathbb^. Therefore, homological 1-connectivity is equivale ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Independence Complex
The independence complex of a graph is a mathematical object describing the independent sets of the graph. Formally, the independence complex of an undirected graph ''G'', denoted by I(''G''), is an abstract simplicial complex (that is, a family of finite sets closed under the operation of taking subsets), formed by the sets of vertices in the independent sets of ''G''. Any subset of an independent set is itself an independent set, so I(''G'') is indeed closed under taking subsets. Every independent set in a graph is a clique in its complement graph, and vice versa. Therefore, the independence complex of a graph equals the clique complex of its complement graph, and vice versa. Homology groups Several authors studied the relations between the properties of a graph ''G'' = (''V'', ''E''), and the homology groups of its independence complex I(''G''). In particular, several properties related to the dominating sets in ''G'' guarantee that some reduced homology groups of I(''G'') ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph (discrete Mathematics)
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a Set (mathematics), set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called ''Vertex (graph theory), vertices'' (also called ''nodes'' or ''points'') and each of the related pairs of vertices is called an ''edge'' (also called ''link'' or ''line''). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics. The edges may be directed or undirected. For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any person ''A'' can shake hands with a person ''B'' only if ''B'' also shakes hands with ''A''. In contrast, if an edge from a person ''A'' to a person ''B'' m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Zero-sum Game
Zero-sum game is a mathematical representation in game theory and economic theory of a situation which involves two sides, where the result is an advantage for one side and an equivalent loss for the other. In other words, player one's gain is equivalent to player two's loss, therefore the net improvement in benefit of the game is zero. If the total gains of the participants are added up, and the total losses are subtracted, they will sum to zero. Thus, cutting a cake, where taking a more significant piece reduces the amount of cake available for others as much as it increases the amount available for that taker, is a zero-sum game if all participants value each unit of cake equally. Other examples of zero-sum games in daily life include games like poker, chess, and bridge where one person gains and another person loses, which results in a zero-net benefit for every player. In the markets and financial instruments, futures contracts and options are zero-sum games as well. In c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Connectivity (graph Theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network. Connected vertices and graphs In an undirected graph , two '' vertices'' and are called connected if contains a path from to . Otherwise, they are called disconnected. If the two vertices are additionally connected by a path of length , i.e. by a single edge, the vertices are called adjacent. A graph is said to be connected if every pair of vertices in the graph is connected. This means that there is a path between every pair of vertices. An undirected graph that is not connected is called disconnected. An undirected graph ''G'' is therefore disconnected if there exist two vertices ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
