Civil Rights
Movements, leaders, victories and the continuing fight for equality.
q2K BHP
Black History Portal
THE BHP WIRE —
HIDDEN TRUTHS
What's New!
Explore the people, places, events, achievements, struggles and stories that shaped our journey.
Movements, leaders, victories and the continuing fight for equality.
Innovation, patents, science, technology and world-changing contributions.
Pioneers, champions, Negro Leagues, records, activism and excellence.
Meet the people whose lives, choices and achievements shaped the journey.
Black towns, communities, institutions and places where history happened.
Moments that changed communities, movements, institutions and the nation.
In August 1908, a white mob attacked Springfield, Illinois’s Black community, destroying homes and businesses and lynching two Black men. National outrage over the violence helped spur the movement that created the NAACP the following year.
MORE →Reflects the personal views, recollections, and perspective of the author, Mike Davis.
This is a personal recollection on the Move fire on May 13, 1985
In graph theory, the Henson graph Gi is an undirected infinite graph, the unique countable homogeneous graph that does not contain an i-vertex clique but that does contain all Ki-free finite graphs as induced subgraphs. For instance, G3 is a triangle-free graph that contains all finite triangle-free graphs.
These graphs are named after C. Ward Henson, who published a construction for them (for all i ≥ 3) in 1971.[1] The first of these graphs, G3, is also called the homogeneous triangle-free graph or the universal triangle-free graph.
To construct these graphs, Henson orders the vertices of the Rado graph into a sequence with the property that, for every finite set S of vertices, there are infinitely many vertices having S as their set of earlier neighbors. (Only the Rado graph has such a sequence.) He then defines Gi to be the induced subgraph of the Rado graph formed by removing the final vertex (in the sequence ordering) of every i-clique of the Rado graph.[1]
With this construction, each graph Gi is an induced subgraph of Gi + 1, and the union of this chain of induced subgraphs is the Rado graph itself. Because each graph Gi omits at least one vertex from each i-clique of the Rado graph, there can be no i-clique in Gi.
Any finite or countable i-clique-free graph H can be found as an induced subgraph of Gi by building it one vertex at a time, at each step adding a vertex whose earlier neighbors in Gi match the set of earlier neighbors of the corresponding vertex in H. That is, Gi is a universal graph for the family of i-clique-free graphs.
Because there exist i-clique-free graphs of arbitrarily large chromatic number, the Henson graphs have infinite chromatic number. More strongly, if a Henson graph Gi is partitioned into any finite number of induced subgraphs, then at least one of these subgraphs includes all i-clique-free finite graphs as induced subgraphs.[1]
Like the Rado graph, G3 contains a bidirectional Hamiltonian path such that any symmetry of the path is a symmetry of the whole graph. However, this is not true for Gi when i > 3: for these graphs, every automorphism of the graph has more than one orbit.[1]
Source: Wikipedia. Article content is retrieved live through the MediaWiki API.
In graph theory, the Henson graph Gi is an undirected infinite graph, the unique countable homogeneous graph that does not contain an i-vertex clique but that does contain all Ki-free finite graphs as induced subgraphs. For instance, G3 is a triangle-free graph that contains all finite triangle-free graphs. These graphs are named after C. Ward Henson, who published a construction for them (for all i ≥ 3) in 1971. The first of these graphs, G3, is also called the homogeneous triangle-free graph or the universal triangle-free graph.
In mathematics, a universal graph is an infinite graph that contains every finite (or at-most-countable) graph as an induced subgraph. A universal graph of this type was first constructed by Richard Rado and is now called the Rado graph or random graph. More recent work has focused on universal graphs for a graph family F: that is, an infinite graph belonging to F that contains all finite graphs in F. For instance, the Henson graphs are universal in this sense for the i-clique-free graphs. A universal graph for a family F of graphs can also refer to a member of a sequence of finite graphs that contains all graphs in F; for instance, every finite tree is a subgraph of a sufficiently large hypercube graph so a hypercube can be said to be a universal graph for trees. However it is not the smallest such graph: it is known that there is a universal graph for n-vertex trees, with only n vertices and O(n log n) edges, and that this is optimal. A construction based on the planar separator theorem can be used to show that n-vertex planar graphs have universal graphs with O(n3/2) edges, and that bounded-degree planar graphs have universal graphs with O(n log n) edges. It is also possible to construct universal graphs for planar graphs that have n1+o(1) vertices. Sumner's conjecture states that tournaments are universal for polytrees, in the sense that every tournament with 2n − 2 vertices contains every polytree with n vertices as a subgraph. A family F of graphs has a universal graph of polynomial size, containing every n-vertex graph as an induced subgraph, if and only if it has an adjacency labelling scheme in which vertices may be labeled by O(log n)-bit bitstrings such that an algorithm can determine whether two vertices are adjacent by examining their labels. For, if a universal graph of this type exists, the vertices of any graph in F may be labeled by the identities of the corresponding vertices in the universal graph, and conversely if a labeling scheme exists then a universal graph may be constructed having a vertex for every possible label. In older mathematical terminology, the phrase "universal graph" was sometimes used to denote a complete graph. The notion of universal graph has been adapted and used for solving mean payoff games.
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs. By Turán's theorem, the n-vertex triangle-free graph with the maximum number of edges is a complete bipartite graph in which the numbers of vertices on each side of the bipartition are as equal as possible.
In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed (with probability one) by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann (1937). The Rado graph can also be constructed non-randomly, as a graph whose vertices are hereditarily finite sets (finite sets whose elements are hereditarily finite) with edges representing set membership, as a graph whose vertices are natural numbers and whose edges are given by the BIT predicate that uses the smaller of two numbers as an index into the binary representation of the other number, or as a graph of certain prime numbers that are connected by edges when one number is a square modulo another. Every finite or countably infinite graph is an induced subgraph of the Rado graph, and can be found as an induced subgraph by a greedy algorithm that builds up the subgraph one vertex at a time. The Rado graph is uniquely defined, among countable graphs, by an extension property that guarantees the correctness of this algorithm: no matter which vertices have already been chosen to form part of the induced subgraph, and no matter what pattern of adjacencies is needed to extend the subgraph by one more vertex, there will always exist another vertex with that pattern of adjacencies that the greedy algorithm can choose. The Rado graph is highly symmetric: any isomorphism of its finite induced subgraphs can be extended to a symmetry of the whole graph. The first-order logic sentences that are true of the Rado graph are also true of almost all random finite graphs, and the sentences that are false for the Rado graph are also false for almost all finite graphs. In model theory, the Rado graph is an example of the unique countable model of an ω-categorical theory.
Before the 1921 destruction of Tulsa’s Greenwood District, Black residents had created a remarkable center of business and community life. The district included stores, professional offices, entertainment venues and homes owned by Black citizens. Understanding Greenwood means learning what was built—not only what was burned.
MORE →Shirley Chisholm, elected in 1968.