text:
Clique problem

In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique (a clique with the largest possible number of vertices), finding a maximum weight clique in a weighted graph, listing all maximal cliques (cliques that cannot be enlarged), and solving the decision problem of testing whether a graph contains a clique larger than a given size.

The clique problem arises in the following real-world setting. Consider a social network, where the graph's vertices represent people, and the graph's edges represent mutual acquaintance. Then a clique represents a subset of people who all know each other, and algorithms for finding cliques can be used to discover these groups of mutual friends. Along with its applications in social networks, the clique problem also has many applications in bioinformatics, and computational chemistry.

Most versions of the clique problem are hard. The clique decision problem is NP-complete (one of Karp's 21 NP-complete problems). The problem of finding the maximum clique is both fixed-parameter intractable and hard to approximate. And, listing all maximal cliques may require exponential time as there exist graphs with exponentially many maximal cliques. Therefore, much of the theory about the clique problem is devoted to identifying special types of graph that admit more efficient algorithms, or to establishing the computational difficulty of the general problem in various models of computation.

To find a maximum clique, one can systematically inspect all subsets, but this sort of brute-force search is too time-consuming to be practical for networks comprising more than a few dozen vertices. Although no polynomial time algorithm is known for this problem, more efficient algorithms than the brute-force search are known. For instance, the Bron–Kerbosch algorithm can be used to list all maximal cliques in worst-case optimal time, and it is also possible to list them in polynomial time per clique.

History and applications
The study of complete subgraphs in mathematics predates the "clique" terminology. For instance, complete subgraphs make an early appearance in the mathematical literature in the graph-theoretic reformulation of Ramsey theory by. But the term "clique" and the problem of algorithmically listing cliques both come from the social sciences, where complete subgraphs are used to model social cliques, groups of people who all know each other. used graphs to model social networks, and adapted the social science terminology to graph theory. They were the first to call complete subgraphs "cliques". The first algorithm for solving the clique problem is that of, who were motivated by the sociological application. Social science researchers have also defined various other types of cliques and maximal cliques in social network, "cohesive subgroups" of people or actors in the network all of whom share one of several different kinds of connectivity relation. Many of these generalized notions of cliques can also be found by constructing an undirected graph whose edges represent related pairs of actors from the social network, and then applying an algorithm for the clique problem to this graph.

Since the work of Harary and Ross, many others have devised algorithms for various versions of the clique problem. In the 1970s, researchers began studying these algorithms from the point of view of worst-case analysis. See, for instance,, an early work on the worst-case complexity of the maximum clique problem. Also in the 1970s, beginning with the work of and, researchers began using the theory of NP-completeness and related intractability results to provide a mathematical explanation for the perceived difficulty of the clique problem. In the 1990s, a breakthrough series of papers beginning with showed that (assuming P ≠ NP) it is not even possible to approximate the problem accurately and efficiently.

Clique-finding algorithms have been used in chemistry, to find chemicals that match a target structure and to model molecular docking and the binding sites of chemical reactions. They can also be used to find similar structures within different molecules. In these applications, one forms a graph in which each vertex represents a matched pair of atoms, one from each of two molecules. Two vertices are connected by an edge if the matches that they represent are compatible with each other. Being compatible may mean, for instance, that the distances between the atoms within the two molecules are approximately equal, to within some given tolerance. A clique in this graph represents a set of matched pairs of atoms in which all the matches are compatible with each other. A special case of this method is the use of the modular product of graphs to reduce the problem of finding the maximum common induced subgraph of two graphs to the problem of finding a maximum clique in their product.

In automatic test pattern generation, finding cliques can help to bound the size of a test set. In bioinformatics, clique-finding algorithms have been used to infer evolutionary trees, predict protein structures, and find closely interacting clusters of proteins. Listing the cliques in a dependency graph is an important step in the analysis of certain random processes. In mathematics, Keller's conjecture on face-to-face tiling of hypercubes was disproved by, who used a clique-finding algorithm on an associated graph to find a counterexample.

Definitions
An undirected graph is formed by a finite set of vertices and a set of unordered pairs of vertices, which are called edges. By convention, in algorithm analysis, the number of vertices in the graph is denoted by $n$ and the number of edges is denoted by $m$. A clique in a graph $G$ is a complete subgraph of $G$. That is, it is a subset $K$ of the vertices such that every two vertices in $K$ are the two endpoints of an edge in $G$. A maximal clique is a clique to which no more vertices can be added. For each vertex $v$ that is not part of a maximal clique, there must be another vertex $w$ that is in the clique and non-adjacent to $v$, preventing $v$ from being added to the clique. A maximum clique is a clique that includes the largest possible number of vertices. The clique number $ω(G)$ is the number of vertices in a maximum clique of $G$.

Several closely related clique-finding problems have been studied. The first four of these problems are all important in practical applications. The clique decision problem is not of practical importance; it is formulated in this way in order to apply the theory of NP-completeness to clique-finding problems.
 * In the maximum clique problem, the input is an undirected graph, and the output is a maximum clique in the graph. If there are multiple maximum cliques, one of them may be chosen arbitrarily.
 * In the weighted maximum clique problem, the input is an undirected graph with weights on its vertices (or, less frequently, edges) and the output is a clique with maximum total weight. The maximum clique problem is the special case in which all weights are equal. As well as the problem of optimizing the sum of weights, other more complicated bicriterion optimization problems have also been studied.
 * In the maximal clique listing problem, the input is an undirected graph, and the output is a list of all its maximal cliques. The maximum clique problem may be solved using as a subroutine an algorithm for the maximal clique listing problem, because the maximum clique must be included among all the maximal cliques.
 * In the $k$-clique problem, the input is an undirected graph and a number $k$. The output is a clique with $k$ vertices, if one exists, or a special value indicating that there is no $k$-clique otherwise. In some variations of this problem, the output should list all cliques of size $k$.
 * In the clique decision problem, the input is an undirected graph and a number $k$, and the output is a Boolean value: true if the graph contains a $k$-clique, and false otherwise.

The clique problem and the independent set problem are complementary: a clique in $G$ is an independent set in the complement graph of $G$ and vice versa. Therefore, many computational results may be applied equally well to either problem, and some research papers do not clearly distinguish between the two problems. However, the two problems have different properties when applied to restricted families of graphs. For instance, the clique problem may be solved in polynomial time for planar graphs while the independent set problem remains NP-hard on planar graphs.

Finding a single maximal clique
A maximal clique, sometimes called inclusion-maximal, is a clique that is not included in a larger clique. Therefore, every clique is contained in a maximal clique. Maximal cliques can be very small. A graph may contain a non-maximal clique with many vertices and a separate clique of size 2 which is maximal. While a maximum (i.e., largest) clique is necessarily maximal, the converse does not hold. There are some types of graphs in which every maximal clique is maximum; these are the complements of the well-covered graphs, in which every maximal independent set is maximum. However, other graphs have maximal cliques that are not maximum.

A single maximal clique can be found by a straightforward greedy algorithm. Starting with an arbitrary clique (for instance, any single vertex or even the empty set), grow the current clique one vertex at a time by looping through the graph's remaining vertices. For each vertex $v$ that this loop examines, add $v$ to the clique if it is adjacent to every vertex that is already in the clique, and discard $v$ otherwise. This algorithm runs in linear time. Because of the ease of finding maximal cliques, and their potential small size, more attention has been given to the much harder algorithmic problem of finding a maximum or otherwise large clique. However, some research in parallel algorithms has studied the problem of finding a maximal clique. In particular, the problem of finding the lexicographically first maximal clique (the one found by the algorithm above) has been shown to be complete for the class of polynomial-time functions. This result implies that the problem is unlikely to be solvable within the parallel complexity class NC.

Cliques of fixed size
One can test whether a graph $G$ contains a $k$-vertex clique, and find any such clique that it contains, using a brute force algorithm. This algorithm examines each subgraph with $k$ vertices and checks to see whether it forms a clique. It takes time $O(n^{k} k^{2})$, as expressed using big O notation. This is because there are $O(n^{k})$ subgraphs to check, each of which has $O(k^{2})$ edges whose presence in $G$ needs to be checked. Thus, the problem may be solved in polynomial time whenever $k$ is a fixed constant. However, when $k$ does not have a fixed value, but instead may vary as part of the input to the problem, the time is exponential.

The simplest nontrivial case of the clique-finding problem is finding a triangle in a graph, or equivalently determining whether the graph is triangle-free. In a graph $G$ with $m$ edges, there may be at most $Θ(m^{3/2})$ triangles (using big theta notation to indicate that this bound is tight). The worst case for this formula occurs when $G$ is itself a clique. Therefore, algorithms for listing all triangles must take at least $Ω(m^{3/2})$ time in the worst case (using big omega notation), and algorithms are known that match this time bound. For instance, describe an algorithm that sorts the vertices in order from highest degree to lowest and then iterates through each vertex $v$ in the sorted list, looking for triangles that include $v$ and do not include any previous vertex in the list. To do so the algorithm marks all neighbors of $v$, searches through all edges incident to a neighbor of $v$ outputting a triangle for every edge that has two marked endpoints, and then removes the marks and deletes $v$ from the graph. As the authors show, the time for this algorithm is proportional to the arboricity of the graph (denoted $O(m^{3/2})$) multiplied by the number of edges, which is $O(m^{3/2})$. Since the arboricity is at most $a(G)$, this algorithm runs in time $O(m a(G))$. More generally, all $k$-vertex cliques can be listed by a similar algorithm that takes time proportional to the number of edges multiplied by the arboricity to the power $O(m^{1/2})$. For graphs of constant arboricity, such as planar graphs (or in general graphs from any non-trivial minor-closed graph family), this algorithm takes $O(m^{3/2})$ time, which is optimal since it is linear in the size of the input.

If one desires only a single triangle, or an assurance that the graph is triangle-free, faster algorithms are possible. As observe, the graph contains a triangle if and only if its adjacency matrix and the square of the adjacency matrix contain nonzero entries in the same cell. Therefore, fast matrix multiplication techniques can be applied to find triangles in time $(k − 2)$. used fast matrix multiplication to improve the $O(m)$ algorithm for finding triangles to $O(n^{2.376})$. These algorithms based on fast matrix multiplication have also been extended to problems of finding $k$-cliques for larger values of $k$.

Listing all maximal cliques
By a result of, every $n$-vertex graph has at most $O(m^{3/2})$ maximal cliques. They can be listed by the Bron–Kerbosch algorithm, a recursive backtracking procedure of. The main recursive subroutine of this procedure has three arguments: a partially constructed (non-maximal) clique, a set of candidate vertices that could be added to the clique, and another set of vertices that should not be added (because doing so would lead to a clique that has already been found). The algorithm tries adding the candidate vertices one by one to the partial clique, making a recursive call for each one. After trying each of these vertices, it moves it to the set of vertices that should not be added again. Variants of this algorithm can be shown to have worst-case running time $O(m^{1.41})$, matching the number of cliques that might need to be listed. Therefore, this provides a worst-case-optimal solution to the problem of listing all maximal cliques. Further, the Bron–Kerbosch algorithm has been widely reported as being faster in practice than its alternatives.

However, when the number of cliques is significantly smaller than its worst case, other algorithms might be preferable. As showed, it is also possible to list all maximal cliques in a graph in an amount of time that is polynomial per generated clique. An algorithm such as theirs in which the running time depends on the output size is known as an output-sensitive algorithm. Their algorithm is based on the following two observations, relating the maximal cliques of the given graph $G$ to the maximal cliques of a graph $3^{n/3}$ formed by removing an arbitrary vertex $v$ from $G$: Using these observations they can generate all maximal cliques in $K$ by a recursive algorithm that chooses a vertex $K$ arbitrarily and then, for each maximal clique $G$ in $O(3^{n/3})$, outputs both $G$ and the clique formed by adding $G$ to $G$ and removing the non-neighbors of $v$. However, some cliques of $G$ may be generated in this way from more than one parent clique of $G \ v$, so they eliminate duplicates by outputting a clique in $v$ only when its parent in $G \ v$ is lexicographically maximum among all possible parent cliques. On the basis of this principle, they show that all maximal cliques in $K$ may be generated in time $K ⋃ {v}$ per clique, where $v$ is the number of edges in $v$ and $K$ is the number of vertices. improve this to $G \ v$ per clique, where $G$ is the arboricity of the given graph. provide an alternative output-sensitive algorithm based on fast matrix multiplication. show that it is even possible to list all maximal cliques in lexicographic order with polynomial delay per clique. However, the choice of ordering is important for the efficiency of this algorithm: for the reverse of this order, there is no polynomial-delay algorithm unless P = NP.
 * For every maximal clique $v$ of $G \ v$, either $K$ continues to form a maximal clique in $K$, or $G \ v$ forms a maximal clique in $v$. Therefore, $K$ has at least as many maximal cliques as $G \ v$ does.
 * Each maximal clique in $v$ that does not contain $G$ is a maximal clique in $G \ v$, and each maximal clique in $G$ that does contain $G$ can be formed from a maximal clique $m$ in $G \ v$ by adding $G$ and removing the non-neighbors of $n$ from $a$.

On the basis of this result, it is possible to list all maximal cliques in polynomial time, for families of graphs in which the number of cliques is polynomially bounded. These families include chordal graphs, complete graphs, triangle-free graphs, interval graphs, graphs of bounded boxicity, and planar graphs. In particular, the planar graphs have $O(mn)$ cliques, of at most constant size, that can be listed in linear time. The same is true for any family of graphs that is both sparse (having a number of edges at most a constant times the number of vertices) and closed under the operation of taking subgraphs.

Finding maximum cliques in arbitrary graphs
It is possible to find the maximum clique, or the clique number, of an arbitrary n-vertex graph in time $O(ma)$ by using one of the algorithms described above to list all maximal cliques in the graph and returning the largest one. However, for this variant of the clique problem better worst-case time bounds are possible. The algorithm of solves this problem in time $O(n)$. It is a recursive backtracking scheme similar to that of the Bron–Kerbosch algorithm, but is able to eliminate some recursive calls when it can be shown that the cliques found within the call will be suboptimal. improved the time to $O(3^{n/3}) = O(1.4422^{n})$, and improved it to $O(2^{n/3}) = O(1.2599^{n})$ time, at the expense of greater space usage. Robson's algorithm combines a similar backtracking scheme (with a more complicated case analysis) and a dynamic programming technique in which the optimal solution is precomputed for all small connected subgraphs of the complement graph. These partial solutions are used to shortcut the backtracking recursion. The fastest algorithm known today is a refined version of this method by which runs in time $O(2^{0.304n}) = O(1.2346^{n})$.

There has also been extensive research on heuristic algorithms for solving maximum clique problems without worst-case runtime guarantees, based on methods including branch and bound, local search, greedy algorithms, and constraint programming. Non-standard computing methodologies that have been suggested for finding cliques include DNA computing and adiabatic quantum computation. The maximum clique problem was the subject of an implementation challenge sponsored by DIMACS in 1992–1993, and a collection of graphs used as benchmarks for the challenge, which is publicly available.

Special classes of graphs
Planar graphs, and other families of sparse graphs, have been discussed above: they have linearly many maximal cliques, of bounded size, that can be listed in linear time. In particular, for planar graphs, any clique can have at most four vertices, by Kuratowski's theorem.

Perfect graphs are defined by the properties that their clique number equals their chromatic number, and that this equality holds also in each of their induced subgraphs. For perfect graphs, it is possible to find a maximum clique in polynomial time, using an algorithm based on semidefinite programming. However, this method is complex and non-combinatorial, and specialized clique-finding algorithms have been developed for many subclasses of perfect graphs. In the complement graphs of bipartite graphs, Kőnig's theorem allows the maximum clique problem to be solved using techniques for matching. In another class of perfect graphs, the permutation graphs, a maximum clique is a longest decreasing subsequence of the permutation defining the graph and can be found using known algorithms for the longest decreasing subsequence problem. Conversely, every instance of the longest decreasing subsequence problem can be described equivalently as a problem of finding a maximum clique in a permutation graph. provide an alternative quadratic-time algorithm for maximum cliques in comparability graphs, a broader class of perfect graphs that includes the permutation graphs as a special case. In chordal graphs, the maximal cliques can be found by listing the vertices in an elimination ordering, and checking the clique neighborhoods of each vertex in this ordering.

In some cases, these algorithms can be extended to other, non-perfect, classes of graphs as well. For instance, in a circle graph, the neighborhood of each vertex is a permutation graph, so a maximum clique in a circle graph can be found by applying the permutation graph algorithm to each neighborhood. Similarly, in a unit disk graph (with a known geometric representation), there is a polynomial time algorithm for maximum cliques based on applying the algorithm for complements of bipartite graphs to shared neighborhoods of pairs of vertices.

The algorithmic problem of finding a maximum clique in a random graph drawn from the Erdős–Rényi model (in which each edge appears with probability $O(2^{0.276n}) = O(1.2108^{n})$, independently from the other edges) was suggested by. Because the maximum clique in a random graph has logarithmic size with high probability, it can be found by a brute force search in expected time $O(2^{0.249n}) = O(1.1888^{n})$. This is a quasi-polynomial time bound. Although the clique number of such graphs is usually very close to $1/2$, simple greedy algorithms as well as more sophisticated randomized approximation techniques only find cliques with size $2^{O(log^{2}n)}$, half as big. The number of maximal cliques in such graphs is with high probability exponential in $2 log_{2}n$, which prevents methods that list all maximal cliques from running in polynomial time. Because of the difficulty of this problem, several authors have investigated the planted clique problem, the clique problem on random graphs that have been augmented by adding large cliques. While spectral methods and semidefinite programming can detect hidden cliques of size $log_{2}n$, no polynomial-time algorithms are currently known to detect those of size $log^{2}n$ (expressed using little-o notation).

Approximation algorithms
Several authors have considered approximation algorithms that attempt to find a clique or independent set that, although not maximum, has size as close to the maximum as can be found in polynomial time. Although much of this work has focused on independent sets in sparse graphs, a case that does not make sense for the complementary clique problem, there has also been work on approximation algorithms that do not use such sparsity assumptions.

describes a polynomial time algorithm that finds a clique of size $Ω(\sqrt{n})$ in any graph that has clique number $o(\sqrt{n})$ for any constant $k$. By using this algorithm when the clique number of a given input graph is between $Ω((log n/log log n)^{2})$ and $Ω(n/log^{k}n)$, switching to a different algorithm of for graphs with higher clique numbers, and choosing a two-vertex clique if both algorithms fail to find anything, Feige provides an approximation algorithm that finds a clique with a number of vertices within a factor of $n/log n$ of the maximum. Although the approximation ratio of this algorithm is weak, it is the best known to date. The results on hardness of approximation described below suggest that there can be no approximation algorithm with an approximation ratio significantly less than linear.

NP-completeness
The clique decision problem is NP-complete. It was one of Richard Karp's original 21 problems shown NP-complete in his 1972 paper "Reducibility Among Combinatorial Problems". This problem was also mentioned in Stephen Cook's paper introducing the theory of NP-complete problems. Because of the hardness of the decision problem, the problem of finding a maximum clique is also NP-hard. If one could solve it, one could also solve the decision problem, by comparing the size of the maximum clique to the size parameter given as input in the decision problem.

Karp's NP-completeness proof is a many-one reduction from the Boolean satisfiability problem. It describes how to translate Boolean formulas in conjunctive normal form (CNF) into equivalent instances of the maximum clique problem. Satisfiability, in turn, was proved NP-complete in the Cook–Levin theorem. From a given CNF formula, Karp forms a graph that has a vertex for every pair $n/log^{3}n$, where $v$ is a variable or its negation and $c$ is a clause in the formula that contains $v$. Two of these vertices are connected by an edge if they represent compatible variable assignments for different clauses. That is, there is an edge from $O(n(log log n)^{2}/log^{3}n)$ to $(v,c)$ whenever $(v,c)$ and $u$ and $v$ are not each other's negations. If $k$ denotes the number of clauses in the CNF formula, then the $k$-vertex cliques in this graph represent consistent ways of assigning truth values to some of its variables in order to satisfy the formula. Therefore, the formula is satisfiable if and only if a $k$-vertex clique exists.

Some NP-complete problems (such as the travelling salesman problem in planar graphs) may be solved in time that is exponential in a sublinear function of the input size parameter $n$, significantly faster than a brute-force search. However, it is unlikely that such a subexponential time bound is possible for the clique problem in arbitrary graphs, as it would imply similarly subexponential bounds for many other standard NP-complete problems.

Circuit complexity
The computational difficulty of the clique problem has led it to be used to prove several lower bounds in circuit complexity. The existence of a clique of a given size is a monotone graph property, meaning that, if a clique exists in a given graph, it will exist in any supergraph. Because this property is monotone, there must exist a monotone circuit, using only and gates and or gates, to solve the clique decision problem for a given fixed clique size. However, the size of these circuits can be proven to be a super-polynomial function of the number of vertices and the clique size, exponential in the cube root of the number of vertices. Even if a small number of NOT gates are allowed, the complexity remains superpolynomial. Additionally, the depth of a monotone circuit for the clique problem using gates of bounded fan-in must be at least a polynomial in the clique size.

Decision tree complexity
The (deterministic) decision tree complexity of determining a graph property is the number of questions of the form "Is there an edge between vertex $k$ and vertex $n$?" that have to be answered in the worst case to determine whether a graph has a particular property. That is, it is the minimum height of a boolean decision tree for the problem. There are $(u,d)$ possible questions to be asked. Therefore, any graph property can be determined with at most $c ≠ d$ questions. It is also possible to define random and quantum decision tree complexity of a property, the expected number of questions (for a worst case input) that a randomized or quantum algorithm needs to have answered in order to correctly determine whether the given graph has the property.

Because the property of containing a clique is monotone, it is covered by the Aanderaa–Karp–Rosenberg conjecture, which states that the deterministic decision tree complexity of determining any non-trivial monotone graph property is exactly $k = 3$. For arbitrary monotone graph properties, this conjecture remains unproven. However, for deterministic decision trees, and for any $k$ in the range $n = 4$, the property of containing a $u$-clique was shown to have decision tree complexity exactly $n(n − 1)/2$ by. Deterministic decision trees also require exponential size to detect cliques, or large polynomial size to detect cliques of bounded size.

The Aanderaa–Karp–Rosenberg conjecture also states that the randomized decision tree complexity of non-trivial monotone functions is $n(n − 1)/2$. The conjecture again remains unproven, but has been resolved for the property of containing a $v$ clique for $n(n − 1)/2$. This property is known to have randomized decision tree complexity $2 ≤ k ≤ n$. For quantum decision trees, the best known lower bound is $n(n − 1)/2$, but no matching algorithm is known for the case of $Θ(n^{2})$.

Fixed-parameter intractability
Parameterized complexity is the complexity-theoretic study of problems that are naturally equipped with a small integer parameter $k$ and for which the problem becomes more difficult as $k$ increases, such as finding $k$-cliques in graphs. A problem is said to be fixed-parameter tractable if there is an algorithm for solving it on inputs of size $k$, and a function $k$, such that the algorithm runs in time $2 ≤ k ≤ n$. That is, it is fixed-parameter tractable if it can be solved in polynomial time for any fixed value of $k$ and moreover if the exponent of the polynomial does not depend on $n$.

For finding $f$-vertex cliques, the brute force search algorithm has running time $Θ(n^{2})$. Because the exponent of $k$ depends on $k$, this algorithm is not fixed-parameter tractable. Although it can be improved by fast matrix multiplication, the running time still has an exponent that is linear in $f$. Thus, although the running time of known algorithms for the clique problem is polynomial for any fixed $k$, these algorithms do not suffice for fixed-parameter tractability. defined a hierarchy of parametrized problems, the W hierarchy, that they conjectured did not have fixed-parameter tractable algorithms. They proved that independent set (or, equivalently, clique) is hard for the first level of this hierarchy, W[1]. Thus, according to their conjecture, clique has no fixed-parameter tractable algorithm. Moreover, this result provides the basis for proofs of W[1]-hardness of many other problems, and thus serves as an analogue of the Cook–Levin theorem for parameterized complexity.

showed that finding $n$-vertex cliques cannot be done in time $Ω(n)$ unless the exponential time hypothesis fails. Again, this provides evidence that no fixed-parameter tractable algorithm is possible.

Although the problems of listing maximal cliques or finding maximum cliques are unlikely to be fixed-parameter tractable with the parameter $k$, they may be fixed-parameter tractable for other parameters of instance complexity. For instance, both problems are known to be fixed-parameter tractable when parametrized by the degeneracy of the input graph.

Hardness of approximation
Weak results hinting that the clique problem might be hard to approximate have been known for a long time. observed that, because the clique number takes on small integer values and is NP-hard to compute, it cannot have a fully polynomial-time approximation scheme, unless P = NP. If too accurate an approximation were available, rounding its value to an integer would give the exact clique number. However, little more was known until the early 1990s, when several authors began to make connections between the approximation of maximum cliques and probabilistically checkable proofs. They used these connections to prove hardness of approximation results for the maximum clique problem. After many improvements to these results it is now known that, for every real number $k ≥ 3$, there can be no polynomial time algorithm that approximates the maximum clique to within a factor better than $f(k) n^{O(1)}$, unless P = NP.

The rough idea of these inapproximability results is to form a graph that represents a probabilistically checkable proof system for an NP-complete problem such as the Boolean satisfiability problem. In a probabilistically checkable proof system, a proof is represented as a sequence of bits. An instance of the satisfiability problem should have a valid proof if and only if it is satisfiable. The proof is checked by an algorithm that, after a polynomial-time computation on the input to the satisfiability problem, chooses to examine a small number of randomly chosen positions of the proof string. Depending on what values are found at that sample of bits, the checker will either accept or reject the proof, without looking at the rest of the bits. False negatives are not allowed: a valid proof must always be accepted. However, an invalid proof may sometimes mistakenly be accepted. For every invalid proof, the probability that the checker will accept it must be low.

To transform a probabilistically checkable proof system of this type into a clique problem, one forms a graph with a vertex for each possible accepting run of the proof checker. That is, a vertex is defined by one of the possible random choices of sets of positions to examine, and by bit values for those positions that would cause the checker to accept the proof. It can be represented by a partial word with a 0 or 1 at each examined position and a wildcard character at each remaining position. Two vertices are adjacent, in this graph, if the corresponding two accepting runs see the same bit values at every position they both examine. Each (valid or invalid) proof string corresponds to a clique, the set of accepting runs that see that proof string, and all maximal cliques arise in this way. One of these cliques is large if and only if it corresponds to a proof string that many proof checkers accept. If the original satisfiability instance is satisfiable, it will have a valid proof string, one that is accepted by all runs of the checker, and this string will correspond to a large clique in the graph. However, if the original instance is not satisfiable, then all proof strings are invalid, each proof string has only a small number of checker runs that mistakenly accept it, and all cliques are small. Therefore, if one could distinguish in polynomial time between graphs that have large cliques and graphs in which all cliques are small, or if one could accurately approximate the clique problem, then applying this approximation to the graphs generated from satisfiability instances would allow satisfiable instances to be distinguished from unsatisfiable instances. However, this is not possible unless P = NP.

Research articles

 * . Originally presented at the 1992 Symposium on Foundations of Computer Science,.
 * . Originally presented at the 1992 Symposium on Foundations of Computer Science,.
 * . Source code
 * . Originally presented at the 1992 Symposium on Foundations of Computer Science,.
 * . Originally presented at the 1992 Symposium on Foundations of Computer Science,.
 * . Source code
 * . Originally presented at the 1992 Symposium on Foundations of Computer Science,.
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code
 * . Source code

title: Clique problem


text:
Talk:Art Ross Trophy

Untitled
''This image is listed for deletion due to a suspected copyright breach. Unless its copyright status is clarified within one week it will be deleted from wikipedia. Any attempt to place this image onto any page in the absence of a clarification of its copyright status will be reverted and will be reported. It may be viewed as a bannable offence.''

Thornton
As we all know, this year the league faced for the first time a scoring champion/MVP-caliber player being traded during the season. This makes how to properly document this sort of thing more difficult. As near as I can tell, the league's press releases that list the winners simply say Thornton was a Shark this year. Should we list him as such as well, and delete the "Boston Bruins/"?

 * Keep keep both teams. see also Talk:Hart Memorial Trophy -- MrDolomite

Gretzky with a Rangers jersey?
He never won the Art Ross with the Rangers. A picture of him wearing an Oilers jersey would be far more appropriate. Let's not give the Rangers any credit here. :) —Preceding unsigned comment added by Ivand67 (talk • contribs) 03:48, 20 February 2008 (UTC)
 * Unfortunately, images have to be free to use and so far someone who took a picture of Gretzky in a oiler uniform has not released the copywrite on one for us to be able to use it. -Djsasso (talk) 21:41, 15 July 2008 (UTC)
 * Howabout in a Kings uniform? He's won the Art Ross with the Kings. GoodDay (talk) 23:00, 15 July 2008 (UTC)
 * The current picture is a FP, no need to change it. --Krm500 (talk) 00:11, 16 July 2008 (UTC)
 * It's gotta be changed, Gretz won the award as an Oiler & King; but not as a Ranger (or Blue, for that matter). GoodDay (talk) 21:00, 17 July 2008 (UTC)
 * Well then, find a FP quality picture of Gretzky in either one of those jerseys. Gretzky won the award, it doesn't really matter which image we use, him in a Ranger jersey, at a practice, or at the beach. Just that we use the best quality picture, and that is currently him in a Ranger jersey. --Krm500 (talk) 21:12, 17 July 2008 (UTC)
 * Howabout Mario Lemieux? anything's better then Wayne 'you were not allowed to hit him' Gretzky; ha ha. GoodDay (talk) 21:25, 17 July 2008 (UTC)
 * A little late here, but why not add the text to the picture below in this article; Shown playing with the rangers, Gretzky won the league scoring both with the kings and Oilers. Just a thoght Ottawa4ever (talk) 10:59, 11 December 2009 (UTC)

Malkin added
First 2-time winner since Jagr. Season's not officially over but I'm gonna go out on a limp and say Stamkos is not gonna score 13 points in today's game vs. Winnipeg... — Preceding unsigned comment added by 72.189.62.202 (talk) 23:45, 7 April 2012 (UTC)

External links modified
Hello fellow Wikipedians,

I have just modified 1 one external link on Art Ross Trophy. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
 * Added archive https://web.archive.org/web/20070807064352/http://www.legendsofhockey.net:80/html/silver_splashartross.htm to http://www.legendsofhockey.net/html/silver_splashartross.htm

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at ).

Cheers.— InternetArchiveBot  (Report bug) 07:24, 14 September 2016 (UTC)

External links modified
Hello fellow Wikipedians,

I have just modified 1 one external link on Art Ross Trophy. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
 * Added archive https://web.archive.org/web/20121019025506/http://www.iihf.com/nc/home-of-hockey/news/news-singleview/article/daniel-sedin-wins-art-ross.html to http://www.iihf.com/nc/home-of-hockey/news/news-singleview/article/daniel-sedin-wins-art-ross.html

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at ).

Cheers.— InternetArchiveBot  (Report bug) 18:00, 18 October 2016 (UTC)

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Talk:Art Ross Trophy


text:
Talk:David Ahenakew

Aboriginal?
I am not sure how to state his ethnicity if that is the correct term. The artivle should mention that he is 'aboriginal'. Is 'Aboriginal' a tribe, nation, ethnicity, something else? Is this a correct sentence: David Ahenakew is an Aborigine? Geo8rge (talk) 19:08, 25 February 2009 (UTC)

 * Indian or Aboriginal are both fine. WritersCramp (talk) 19:29, 14 March 2010 (UTC)

Was he born in Ontario or Saskatchewan?
Not clear from the references.Geo8rge (talk) 19:18, 25 February 2009 (UTC)

News articles

 * Jun 09, 2006 CTV News: Ahenakew's hate crime conviction overturned
 * Jun 08, 2006 CBC News: Judge orders new trial for David Ahenakew
 * Apr 03, 2006 CBC News: Ahenakew lawyer says controversial conversation was private
 * Apr 03, 2006 CTV News: Ahenakew to appeal conviction for promoting hate
 * Jul 08, 2005 CBC News: Ahenakew found guilty of promoting hatred; fined $1,000
 * Jul 07, 2005 CBC News: Disgraced Ahenakew to lose Order of Canada honour
 * Aug 14, 2003 CBC News: Ahenakew claims 'racial control' of media
 * Jun 11, 2003 CBC News: Ahenakew charged with spreading hate
 * Dec 17, 2002 CBC News: Ahenakew apologizes but may still face criminal charges
 * Dec 16, 2002 CBC News: Aboriginal groups try to distance themselves from anti-Semitic remarks
 * Dec 16, 2002 CTV News: Native leader blasted for antisemitic remarks

Judgements

 * June 8, 2006 Queens Bench For Saskatchewan
 * March 9, 2006 Queen's Bench For Saskatchewan
 * July 8, 2005 Provincial Court of Saskatchewan

External links modified
Hello fellow Wikipedians,

I have just modified 3 external links on David Ahenakew. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
 * Added archive https://web.archive.org/web/20080610074057/http://www.sicc.sk.ca/faces/mahenda.htm to http://www.sicc.sk.ca/faces/mahenda.htm
 * Added archive https://web.archive.org/web/20060827093351/http://www.thismagazine.ca/issues/2003/07/speaknoevil.php to http://www.thismagazine.ca/issues/2003/07/speaknoevil.php
 * Added archive https://web.archive.org/web/20080830031838/http://204.83.249.88/judgments/2006/QB2006/2006skqb272.pdf to http://204.83.249.88/judgments/2006/QB2006/2006skqb272.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

Cheers.— InternetArchiveBot  (Report bug) 05:57, 26 November 2017 (UTC)

External links modified
Hello fellow Wikipedians,

I have just modified one external link on David Ahenakew. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
 * Added archive https://web.archive.org/web/20100324015704/http://www.canada.com/news/Controversial+native+leader+David+Ahenakew+dies/2677874/story.html to http://www.canada.com/news/Controversial+native+leader+David+Ahenakew+dies/2677874/story.html

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

Cheers.— InternetArchiveBot  (Report bug) 12:44, 9 December 2017 (UTC)

title: Talk:David Ahenakew


text:
Talk:James Clerk Maxwell

Trinity
Maxwell believed in the Trinity. There is a good thoughtful post about this at https://www.cslewis.org/journal/physics-and-christian-theology-beauty-a-common-dialect/. This should be included in the article. ScientistBuilder (talk) 20:41, 16 February 2022 (UTC)
 * That post doesn't mention Maxwell. It doesn't mention the Trinity either. Schazjmd   (talk)  23:12, 16 February 2022 (UTC)
 * Actually it does. You have to click through the pages to find it, or else click on "all".  However, what was actually posted in the article was not "Maxwell believed in the Trinity", but that belief in the Trinity led to Maxwell's equations, which was why I reverted it.  I'm not sure that I understand why it is so important to state this was one of Maxwell's beliefs.  Surely that follows from his religion which is already well covered in the article?  I'm pretty sure he would have believed in Jesus too, but I don't see any need to state it explicitly.  Anyway, as I pointed out in detail on my talk page, that source is so full of nonsense there is no way we should treat it as reliable for anything. SpinningSpark 12:26, 17 February 2022 (UTC)
 * This article makes a logical argument. ScientistBuilder (talk) 13:22, 17 February 2022 (UTC)
 * http://silas.psfc.mit.edu/Maxwell/ ScientistBuilder (talk) 13:23, 17 February 2022 (UTC)
 * Thanks,, I didn't see that it was a multi-page article. Schazjmd   (talk)  15:22, 17 February 2022 (UTC)

Spelling error
Since article is locked, I guess I post here. Under: Scientific Legacy > Colour Vision "metameres" should just be "metamers" Cartler (talk) 02:46, 20 November 2022 (UTC)
 * Done. I've confirmed your account so you should be able to edit the page yourself now. But I think you only needed one more edit to be auto-confirmed anyway. SpinningSpark 17:06, 20 November 2022 (UTC)

Shoulders of Maxwell
"Einstein, when he visited the University of Cambridge in 1922, was told by his host that he had done great things because he stood on Newton's shoulders; Einstein replied: "No I don't. I stand on the shoulders of Maxwell." " On looking up the reference, it is discovered that the book attributes the story to something "recounted by the American physicist Frederick Seitz". Seitz was born in 1911 in the US and would have been 11 in 1922. It is not clear he ever went to Cambridge or who he got the story from. "The Fire i' the Flint" doesn't give a reference for Seitz's story. It sounds like the kind of thing people want Einstein to have said. Removed as it falls well short of Wikipedia's standards for reliable sources. It appears from Seitz's Wikipedia article that he was "a central figure amongst global warming deniers" and that he "played a key role... in helping the tobacco industry produce uncertainty concerning the health impacts of smoking." Burraron (talk) 14:36, 13 June 2023 (UTC)
 * A paper in the Proceedings of the American Philosophical Society gives a different version of the story, that Einstein made the statement to a group of reporters in England on his first visit after the war. Schazjmd   (talk)  14:51, 13 June 2023 (UTC)

science
James clerk maxwell explainition 64.226.63.194 (talk) 23:44, 18 November 2023 (UTC)

title: Talk:James Clerk Maxwell


text:
Talk:Don Budge

Untitled
''This image is listed for deletion due to a suspected copyright breach. Unless its copyright status is clarified within one week it will be deleted from wikipedia. Only images before 1923 are guaranteed free from copyright. A seventy year old age may still be the property of some newspaper and agency. Unless that source is stated for the records, fair use cannot be assured. Any attempt to place this image onto any page in the absence of a clarification of its copyright status will be reverted and will be reported. It may be viewed as a bannable offence.''

Nazi flag for von Cramm
The Nazi flag, someone set behind Gottfried von Cramm is an insult. Von Cramm was a known opponent of the Nazi regime, and was actually imprisoned by the Gestapo in 1938 for dubious reasons. The Nazis prevented him from winning Wimbledon in 1939, after he had beaten the eventual winner Riggs 6-2,6-1 at Queens. Later he was purposely sent into the line of fire on the Russian front. He got the Iron Cross there. In the last years of WW II he fled to his friend, the King of Sweden. After the war, von Cramm was the first German, who was gained entrance at an international sporting event, at Wimbledon in 1948.Please remove that sign (german friend 3.1.2007). —The preceding unsigned comment was added by 84.60.180.188 (talk) 16:39, 3 February 2007 (UTC).

 * It may be an insult, but that is the Wikipedia tradition that apparently has evolved for this sort of editorial entry: the flag for the individual in question is that used by the country he/she played for at the time. Other people have objected to the use of the Franco-Spain flag, the Nazi flag, and the Soviet communist flag, among others. But all of them have either been retained or restored in the other articles, so it will undoubtedly be the case here also. Hayford Peirce 18:46, 3 February 2007 (UTC)

 * I haven't noticed the German flag till today. Perhaps to follow the neutrality concept of Wikipedia one has to use the flag of the time but I recognize it's disturbing to watch it. von Cramm was arrested by the Gestapo because he was a true opponent of the Nazi regim. He was prevented from playing any tennis event from spring 1938 through spring 1939 and in particular he couldn't enter neither the Davis Cup in 1938 and 1939 nor the Slam tournaments those same years (except the Australian in 1938). Though von Cramm was Roland Garros titlist he couldn't enter the 1937 singles but was obliged to play the doubles with Henner Henkel, the future singles winner. One thing I would be enclined to do would be to suppress the "Von Cramm bowing to Hitler" photo in the von Cramm article. What's the interest of such a photo which sort of denigrates the German player ? Who wouldn't have bowed to Hitler in those circumstances apart from some extraterrestrial heroes ?

 * PS: though von Cramm's career was stopped by the Nazis and the war the German was still able to defeat Drobny in 1949 or 1950. Carlo Colussi 15:33, 5 February 2007 (UTC)

 * This is certainly one of those issues on which there will probably never be a consensus opinion. If you look at the list of Wimbledon winners, you will see the Nazi flag.  In the French and U.S. Opens you seen the present German flag used for Von Cramm.  So it appears to be a coin flip, as the issue can be argued either way.  As for the photo of Von Cramm and Hitler I think it should remain for historic interest, for the very reason you're against it -- here's the great tennis hero bowing to this awful man, showing just what Germany had come to during those terrible days.  It's not to degrade Von Cramm.... Hayford Peirce 17:45, 5 February 2007 (UTC)

 * Perhaps Carlo Colussi 08:35, 6 February 2007 (UTC)

I agree, it is bitter in particular for a man like von Cramm, to be linked that way with Hitler and the Nazi flag, because of all sportsmen in the Third Reich he didn't derserve it. His imprisonement was due to an affair with a Jewish actor, whom he helped to get out of Germany.By the way, Roderich Menzel, who gets a Czechoslovakian flag, was a German-Czech, and after Hitlers taking over of Böhmen in 1938, he became a German Davis Cup player. Formally, he played for the same flag then (german friend 6. Jan.).

Fair use rationale for Image:Don Budge Time Cover.jpg
Image:Don Budge Time Cover.jpg is being used on this article. I notice the image page specifies that the image is being used under fair use but there is no explanation or rationale as to why its use in this Wikipedia article constitutes fair use. In addition to the boilerplate fair use template, you must also write out on the image description page a specific explanation or rationale for why using this image in each article is consistent with fair use.

Please go to the image description page and edit it to include a fair use rationale. Using one of the templates at Fair use rationale guideline is an easy way to insure that your image is in compliance with Wikipedia policy, but remember that you must complete the template. Do not simply insert a blank template on an image page.

If there is other fair use media, consider checking that you have specified the fair use rationale on the other images used on this page. Note that any fair use images lacking such an explanation can be deleted one week after being tagged, as described on criteria for speedy deletion. If you have any questions please ask them at the Media copyright questions page. Thank you.

BetacommandBot (talk) 06:01, 2 January 2008 (UTC)

Archiving
Dear TennisExpert. The comments were over a year old and irrelevant to this article. Why, would you replace them? I don't see any point in archiving unsigned and/or irrelevant comments, Do you? -- Mjquin_id (talk) 05:39, 2 December 2008 (UTC)

 * See WP:TALK. Tennis expert (talk) 06:13, 2 December 2008 (UTC)

 * I have, and I understand it. Would this discussion be more appropriate on Von Cramm's page? I have been deleting a number of "unsigned" and "off-topic" discussions. Would "moving" the discussion to that page and referencing it here meet with your approval? It would seem coherent that people should look for an explanation there and not here. -- Mjquin_id (talk) 07:09, 2 December 2008 (UTC)

 * You should not be deleting "unsigned" or "off-topic" discussions. Nor should you be moving discussions from one page to another.  A discussion page should not be treated like an article.  Tennis expert (talk) 22:54, 2 December 2008 (UTC)

Records
These state that Budge has a 'stand alone' record for 14 consecutive tournament wins but the reference does not claim it to be an all time record and the Wikipedia article "All Time tennis records - men's singles" has Budge #4 on the list for this achievement - recommend remove this. There is something though that appears lacking here - by the FO 1938 Budge had achieved the non-calendar Grand Slam. While that was not something that got recognition until sometime later it is now considered a significant achievement and one that should be accorded to him as the first to achieve. Antipodenz (talk) 08:00, 25 September 2021 (UTC)

Please, please, help
I posted this on Djokovic page.

I see a logical inconsistency here accros all wikipedia. It says Djokovic is not standing alone with his "non-calendar grand slam achievement", rather he shares it with Budge? OK.

But if so, why isn't Budge listed as non-calendar grand slam winner in his own page? https://en.wikipedia.org/wiki/Don_Budge#Records

No sign of that there, it does not mention that he "shares non-calendar slam with Djokovic, in fact, there is no mention of non-calendar grand slam in Budge's page?

Why is non-calendar grand slam good achievement for Djokvovic to be credited with, but not good enough for Budge?

Also no mention that Budge has done/won non-calendar Grand Slam here, either? https://en.wikipedia.org/wiki/List_of_Grand_Slam_men%27s_singles_champions#Non-calendar_year_Grand_Slam

No Budge. The way I see it, Budge is not credited for his non-calendar slam, since the non-calendar grand slam streak is partially part of his Grand Slam strewak and perhaps it's double counting. I get that, but then it menans Djokovic is the only one with a non-calendar grand slam? Why does it then say he shares it with Budge?

I have nothing for, or against, either Budge or Djokovic, it just that I am amazed that we can invoke non-calendar grand slam so arbitrarily accross wikiepdia, depending on mood and preferences.

So I ask, does Budge indeed has a non-calendar grand slam, or has that been abolished (absorbed) into his Grand Slam?

Based on that reply/decision you should do a clean up and editing accross all wikipedia on this issue to force a logical consistency.

Thank you.

93.140.175.231 (talk) 08:02, 21 June 2023 (UTC) Leonardo the Voyager

title: Talk:Don Budge


text:
Talk:Steffi Graf

Error under Personal life
In the "Personal Life" section, the last sentence states that "Steffi is sister of racing driver Michael Graf and prior to Agassi, had a high profile seven year long relationship with Michael Bartels." I'm pretty sure that Steffi Graf's brother is not a racecar driver, and definitely not the person whose bio entry is linked to "Michael Graf" in the sentence. I know her brother is named Michael, but believes he in the advertisement industry and lives in the States. Could someone confirm and make the change? Thanks.

Poor wording in sentence
This sentence needs to be reworded: "She was ranked the Women's Tennis Association's No. 1 player for a record 377 weeks – the longest of any player, male or female, since rankings began.."

It implies that male players can be ranked by the Women's Tennis Association.

title: Talk:Steffi Graf


text:
Waitangi Day

Waitangi Day (Te Rā o Waitangi, the national day of New Zealand, marks the anniversary of the initial signing—on 6 February 1840—of the Treaty of Waitangi. The Treaty of Waitangi was an agreement towards British sovereignty by representatives of the Crown and indigenous Māori chiefs, and so is regarded by many as the founding document of the nation.

Waitangi Day was first celebrated in 1934, and it was made a national public holiday in 1974. The anniversary is marked annually on 6 February, and a public holiday is observed on the day, or if the date falls on a Saturday or Sunday then the following Monday is observed.

Ceremonies take place at Waitangi and elsewhere to commemorate the signing of the treaty. A variety of events are held, including parties, Māori hui (social gatherings), reflections on New Zealand history, official awards and citizenship ceremonies. The commemoration has also been the focus of protest by Māori activists, and is occasionally the focus of controversy.

History
The Treaty of Waitangi (Te Tiriti o Waitangi) was first signed on 6 February 1840 on the grounds of James Busby's house—now known as Treaty House—at Waitangi, in the Bay of Islands. The treaty was signed by representatives acting on behalf of the British Crown and, initially, by about 45 Māori chiefs. Over the course of the next seven months, copies of the treaty were toured around the New Zealand archipelago by the British, and eventually around 540 Māori chiefs would sign. The signing had the effect of securing British sovereignty over the islands of New Zealand, which was officially proclaimed by the Lieutenant-Governor of New Zealand, William Hobson, on 21 May 1840.

Previous celebrations
Prior to 1934, most celebrations of New Zealand's founding as a colony were held on 29 January, the date on which William Hobson arrived in the Bay of Islands to issue the proclamation of his appointment, which had been prepared by colonial office officials in England. Hobson had no draft treaty. From the British perspective the proclamation was the key legal document, "what the treaty said was less important".

In 1932, Governor-General Lord Bledisloe and his wife purchased and presented to the nation the run-down house of James Busby, where the treaty was initially signed. They subsequently donated GB£500 to restore the building. The Treaty House and grounds were made a public reserve, which was dedicated on 6 February 1934. This event is considered to be the first Waitangi Day.

In 1940, another event was held at the grounds, commemorating the 100th anniversary of the treaty signing. The event was a success and helped raise the profile of the treaty and its day of observance in the national consciousness.

Annual commemorations
Annual commemorations of the treaty signing began in 1947. The 1947 event was a Royal New Zealand Navy ceremony centring on a flagpole which the Navy had paid to erect in the grounds. The ceremony was brief and featured no Māori. The following year, a Māori speaker was added to the line-up, and subsequent additions to the ceremony were made nearly every year. From 1952, the governor-general attended, and from 1958 the prime minister also attended, although not every year. From the mid-1950s, a Māori cultural performance was usually given as part of the ceremony. Many of these early features remain a part of Waitangi Day ceremonies, including a naval salute, the Māori cultural performance (now usually a pōwhiri, a ceremonial welcome), and speeches from a range of Māori and Pākehā (non-Māori) dignitaries.

Proposed as public holiday
The Labour Party stated in its 1957 election manifesto that it would make Waitangi Day a public holiday. After winning that year's election, the party said that the country could not afford another public holiday (see the Black Budget). The Waitangi Day Act of 1960 allowed localities to transfer the holiday from their existing regional public holiday to Waitangi Day.

In 1963, after a change of government, the passing of the Waitangi Day Amendment Act transferred the holiday observed in Northland on Auckland Anniversary Day (the Monday closest to 29 January) to Waitangi Day, 6 February. This made Waitangi Day a holiday in Northland only.

Transition to public holiday
Waitangi Day became a nationwide public holiday on its observance in 1974 by first undergoing a name change. In 1971 the Labour shadow minister of Māori Affairs, Matiu Rata, introduced a private member's bill to make Waitangi Day a national holiday, to be called New Zealand Day. This was not passed into law.

After the 1972 election of the third Labour government under Prime Minister Norman Kirk, it was announced that from 1974, Waitangi Day would be a national holiday known as New Zealand Day. The New Zealand Day Act legislation was passed in 1973. For Kirk, the change was simply an acceptance that New Zealand was ready to move towards a broader concept of nationhood. Diplomatic posts had for some years marked the day, and it seemed timely in view of the country's increasing role on the international stage that the national day be known as New Zealand Day. At the 1974 commemorations, the Flag of New Zealand was flown for the first time at the top of the flagstaff at Waitangi, rather than the Union Jack, and a replica of the flag of the United Tribes of New Zealand was also flown.

The election of the third National government in 1975 led to the day being renamed Waitangi Day because the new prime minister, Robert Muldoon, did not like the name "New Zealand Day" and many Māori felt that it debased the treaty. Another Waitangi Day Act was passed in 1976 to change the name back to Waitangi Day and restore Northland's anniversary day holiday to that of Auckland.

Waitangi Day underwent 'Mondayisation' in legislation enacted in 2013, meaning the public holiday is observed on the following Monday if 6 February falls on a Saturday or Sunday.

At Waitangi
Commemorations at Waitangi usually commence two or three days before Waitangi Day. At Te Tii Waitangi marae, on the southern side of the Waitangi River, political dignitaries are welcomed onto the marae and hear speeches from the local iwi. These speeches often deal with the issues of the day, and vigorous and robust debate occurs. Politicians are usually granted speaking rights, but on occasion, the privilege has been withdrawn, as with Leader of the Opposition Helen Clark in 1999, Prime Ministers John Key in 2016, and Bill English in 2017. In recent years, the official pōwhiri, or welcome ceremony, for members of parliament has moved from Te Tii Waitangi (sometimes referred to as the "lower marae") to Te Whare Rūnanga (sometimes referred to as the "upper marae", even though it is not a true marae) at the treaty grounds, which are north of the Waitangi River. In 2018, Jacinda Ardern was the first Prime Minister to attend the commemorations in three years. According to The Guardian, "Under Ardern the celebration has taken on a more conciliatory tone, with the prime minister usually spending several days at the treaty grounds listening to Māori leaders and in 2018 memorably asking those gathered to hold her government to account."

On Waitangi Day, a public service is held at dawn, organised by the Waitangi National Trust, attended by Māori elders and leaders, religious leaders, politicians, members of the diplomatic corps, and defence force personnel. In 2021, this included hīmene (hymns), religious readings, and prayers in many languages. The Royal New Zealand Navy raised flags on the flagstaff in the treaty grounds. Since 2018, members of the government, including the prime minister and members of parliament and their families have served a barbeque breakfast to members of the public following the dawn service. Throughout the day, cultural displays such as kapa haka (Māori dance and song), wānanga (educational discussions), and other entertainment take place on stages throughout the treaty grounds. Several waka and sometimes a navy ship also take part in demonstrations in the harbour. The day closes with the flags being lowered by the Navy in a traditional ceremony.

Elsewhere in New Zealand

Some marae use the day as an open day and an educational experience for their local communities, giving them the opportunity to experience Māori culture and protocol, or as an opportunity to explain where they see Māori are and the way forward for Māori in New Zealand. Commemorations are largely muted in comparison to those seen on the national days of most countries. There are no mass parades or firework displays, nor truly widespread commemorations.

City councils, museums, libraries and galleries across New Zealand put on free programmes of public events commemorating Waitangi Day for example in 2023 Waikato Museum had Māori weaving demonstrations with Te Roopu Aroha Ki Te Raranga, live music and a film screening of the movie Whina. In Wellington there was a concert at Waitangi Park called Te Rā o Waitangi, an outdoor film event, waka salutes at Whairepo Lagoon, and bilingual tours of the exhibition Te Tohu at the National Library to see the original 1840 Te Tiriti o Waitangi document.

The governor-general hosts an annual garden party for invited guests at Government House in Wellington. At Government House in Auckland, citizenship ceremonies are usually held. As the day is a public holiday, and coincides with the warmest part of the New Zealand summer, many people take the opportunity to spend the day at the beach—an important part of New Zealand culture.

Since 2014, the New Zealand Society of Authors awards the Waitangi Day Literary Honours on Waitangi Day.

In Australia
At the Kingston Butter Factory in Kingston, Queensland, the Te Korowai Aroha (Cloak of Love) Association held a multicultural festival to mark Waitangi Day annually from 2002. In Sydney, an estimated 8,000 people attended the 2013 Waitangi Day Festival at Holroyd Gardens. The festival featured displays of artefacts, performance of a haka, and Māori culture (cuisine, tattooing and wood carving). 6 February 2015 saw the inaugural Waitangi Day Commemoration held at Nurragingy Reserve, where the focus is more on the document itself, the treaty process and the significance to Māori and Pākehā today. It was co-hosted by the Blacktown City Council and the New South Wales Māori Wardens.

In the United Kingdom
In London, England, which has one of the largest New Zealand expatriate populations, the national day is commemorated by the Waitangi Day Charitable Ball, held by the New Zealand Society. The ball also hosts the annual UK New Zealander of the Year awards, cultural entertainment from London-based Māori group Ngāti Rānana, and fine wine and cuisine from New Zealand. Additionally, a service is held by the society at the church of St Lawrence Jewry.

A tradition, observed for more than 30 years, takes place on the closest Saturday to 6 February: New Zealanders, predominately Pākehā, participate in a pub crawl using the London Underground's Circle Line. Controversy arises regularly after some Pākehā New Zealanders perform drunken and semi-incomprehensible imitations of haka, which has been considered to be offensive. This pub crawl has been criticised for degrading the mana ('honor') of the treaty.

Elsewhere in the world
In many other countries with a New Zealand expatriate population, Waitangi Day is commemorated privately. The day is officially commemorated by all New Zealand embassies and high commissions.

For Waitangi Day 2007, Air New Zealand commissioned a number of New Zealanders living in Los Angeles and Southern California to create a sand sculpture of a silver fern on the Santa Monica Beach, creating a stir in the surrounding area.

Controversy and protest
By 1971, Waitangi and Waitangi Day had become a focus of protest concerning treaty injustices, with Ngā Tamatoa leading early protests. After a walkout from the ceremony in 1972, Governor General Arthur Porritt responded saying "I just do not believe that racism or discrimination exists in this country," demonstrating the gap in mutual understanding. Activists initially called for greater recognition of the treaty, but by the early 1980s, they were also arguing that it was a fraud and the means by which Pākehā had conned Māori out of their land. Attempts were made by groups, including the Waitangi Action Committee, to halt the commemorations. A hīkoi travelled from Tūrangawaewae Marae to the treaty grounds in 1984, in protest of Waitangi Day celebrations. With support from the Waitangi Action Committee, the New Zealand Māori Council, the Māori Women's Welfare League and the Kīngitanga, the number of marchers grew to 2000 people. Growing protests led to confrontations between police and protesters, sometimes resulting in dozens of arrests.

When the treaty gained greater official recognition in the mid-1980s, emphasis switched back to calls to honour it, and protesters generally returned to the aim of raising awareness of it and what they saw as its neglect by the state. In 1990, a young Māori woman threw a wet black t-shirt at Queen Elizabeth II during her visit to Waitangi, in an effort to "galvanize the country’s attention toward Maori problems" and "get justice under the Treaty of Waitangi." In 1995, the threat of protests was so intense that security could not be assured and the ceremony was preempted.

Some New Zealand politicians and commentators, such as Paul Holmes, have felt that Waitangi Day is too controversial to be a national day and have sought to replace it with Anzac Day. Others, for example the United Future Party's Peter Dunne, have suggested that the name be changed back to New Zealand Day.

Recent activism
Waitangi Day celebrations have long been an opportunity for Māori to highlight issues important to Māori, including breaches of the treaty, persistent inequality, high Māori incarceration rates, and advocating for constitutional change which entrench the Treaty of Waitangi. In the past, attempts to vandalise the flagstaff have been an objective of these protests, carrying on a tradition that dates from the 19th century when Hone Heke chopped down the British flagstaff in nearby Russell. In 2004, protesters succeeded in flying the national Māori flag (known as the tino rangatiratanga flag, referring to Māori sovereignty) above the other flags on the flagstaff by flying it from the top of a nearby tree.

Because of the level of protest activity that had previously occurred at Waitangi, Prime Minister Helen Clark did not attend in 2000. The official commemorations were shifted from Waitangi to Wellington for 2001. Some Māori felt that this was an insult to them and to the treaty. In 2003 and 2004, the anniversary was again officially commemorated at the treaty grounds at Waitangi. In 2004, Leader of the Opposition Don Brash was hit with mud as he entered Te Tii Waitangi marae as a response to his controversial Orewa Speech that year.

On 5 February 2009, the day before Waitangi Day, as Prime Minister John Key was being escorted onto the marae, he was challenged and jostled by two nephews of Māori Party MP Hone Harawira. Both admitted to assault and were sentenced to 100 hours of community service. In 2011, the pair again heckled Key as he entered the marae. A wet T-shirt thrown at Queen Elizabeth II and other attacks on various prime ministers at Waitangi on 6 February have resulted in a large police presence and a large contingent of the armed forces on some years. In 2016 a nurse protesting against the proposed signing of the TPPA trade agreement threw a rubber dildo at Steven Joyce, the MP representing Prime Minister John Key, who had refused to attend, having been denied normal speaking rights. The woman was arrested but later released.

In 2018, Prime Minister Jacinda Ardern visited Waitangi for five days, the longest any prime minister has stayed. Titewhai Harawira, a Māori activist, greeted Ardern and escorted her onto the treaty grounds holding hands—a significant change from Harawira's response to Helen Clark's visit in 1998, which brought Clark to tears. Ardern is also the first female prime minister to be given speaking rights on the marae by Ngāpuhi, who also offered to bury her child's placenta on the treaty grounds. Ardern was praised for her speech during her visit where she said "one day I want to be able to tell my child that I earned the right to stand here, and only you can tell me when I have done that".

title: Waitangi Day


text:
Li Hongzhang

Li Hongzhang, Marquess Suyi (also Li Hung-chang; 15 February 1823 – 7 November 1901) was a Chinese statesman, general and diplomat of the late Qing dynasty. He quelled several major rebellions and served in important positions in the Qing imperial court, including the Viceroy of Zhili, Huguang and Liangguang.

Although he was best known in the West for his generally pro-modern stance and importance as a negotiator, Li antagonised the British with his support of Russia as a foil against Japanese expansionism in Manchuria and fell from favour with the Chinese after their defeat in the First Sino-Japanese War. His image in China remains controversial, with criticism on one hand for political and military defeats and praise on the other for his success against the Taiping Rebellion, his diplomatic skills defending Chinese interests in the era of unequal treaties, and his role pioneering China's industrial and military modernisation. He was presented the Royal Victorian Order by Queen Victoria. The French newspaper Le Siècle described him as "the yellow Bismarck."

Names
Li Hongzhang was also known by other names. His courtesy names were Zifu (子黻) and Jianfu (漸甫). His art names were Shaoquan (少荃), Yisou (儀叟) and Shengxin (省心). The posthumous name awarded to him by the Qing government was Wenzhong (文忠). He was also referred to as Li Zhongtang (李中堂) and Li Fuxiang (李傅相); "Zhongtang" and "Fuxiang" referred to his honorary appointments as Grand Secretary and Crown Prince's Grand Tutor respectively. He also held the noble peerage First Class Count Suyi (一等肅毅伯) and was posthumously honoured as First Class Marquis Suyi (一等肅毅侯).

Early life and career
Li was born in a scholar-gentry family in Qunzhi Village (群治村), Modian Township (磨店鄉), 14 km northeast of central Hefei, Anhui Province, China. In 1843, he sat for the entry-level imperial examination in Lu Prefecture and obtained a yougong (優貢; or gongsheng 貢生) position. His father, who was serving as an official in the imperial capital Beijing, was eager to see his son succeed, so he encouraged his son to come to Shuntian Prefecture to take the district-level examination. Li then travelled to Beijing. Along the way, he wrote ten poems under the collection Entering the Capital (入都) to express his feelings.

In 1844, Li obtained a juren (舉人) position in the district-level examination, but failed to make it in the metropolitan-level examination. He then started taking classes under Zeng Guofan. In 1847, he sat for the metropolitan-level examination again and obtained a jinshi (進士) position at the young age of 24, and was admitted to the Hanlin Academy as a shujishi (庶吉士). At the same time, he also continued taking classes under Zeng Guofan to improve his knowledge. Three years later, he took the sanguan (散館) examination in the academy and earned the position of a bianxiu (編修; an editor).

Suppressing the Taiping Rebellion
In January 1851, the God Worshipping Society led by Hong Xiuquan started the Taiping Rebellion in Guangxi Province. Within about two years, the rebels had conquered many territories in southern China and established the Taiping Heavenly Kingdom with Nanjing as their capital. In 1853, the rebels, advancing from Wuhan, captured Anqing and killed Jiang Wenqing (蔣文慶), the xunfu of Anhui Province. The Xianfeng Emperor commissioned Lü Xianji (呂賢基), the Left Vice Secretary of Works, to travel to Anhui Province and recruit civilians to form militias to counter the rebels. Lü Xianji knew that Li was familiar with the local situation in Anhui Province so he secured permission from the imperial court to bring Li along with him as an adviser and assistant. Li was later ordered to remain in Anhui to oversee the militia. In late 1853, the Taiping rebels defeated imperial forces and captured Shucheng County; Lü Xianji committed suicide. In the following year, Jiang Zhongyuan (江忠源), the xunfu of Anhui Province, committed suicide after Lu Prefecture fell to the rebels. Li then became a subordinate of Fu Fuji (福濟), the new xunfu, who ordered him to lead troops to attack the rebels, with Li often leading them in person. Li recaptured two counties and Lu Prefecture from the rebels within the following year. For his achievements, he earned the appointment of a daotai (道台; circuit administrator) and the privilege of wearing a single-eyed peacock feather in his hat. Later, he led troops into the Huai River area, but could not get along with his subordinates and was forced to abandon his mission.

In the winter of 1858, Li was reassigned to serve in Zeng Guofan's office, where he was in charge of drafting documents. Li led a carefree life, flouted rules and regulations, and often woke up late. Zeng Guofan once chided him, "Shaoquan, now that you're working in my office, I only have this piece of advice for you: 'Commitment' is the only thing that matters to us here." Li was shocked and he improved his behaviour after that. In the same year, Weng Tongshu (翁同書), the xunfu of Anhui, abandoned his post when he came under attack by the Taiping rebels. Zeng Guofan drew from Li's draft when he wrote a memorial to the imperial court to accuse Weng Tongshu of failing in his duty. The lines from Li's draft that were included in Zeng Guofan's actual memorial included: "It is my duty, as Your Majesty's subject, [to point out the failures of my colleague.] I do not dare to let this pass just because of Weng Tonghe's fame and prestige." Although Li earned Zeng Guofan's praise for drafting the memorial, he also caused Weng Tonghe (Weng Tongshu's brother) to bear a grudge against him for what he wrote. While serving under Zeng Guofan, he was put in charge of Yanjianshao Circuit (延建邵道) in Fujian Province but did not take up his appointment and remained with Zeng.

In 1860, Li was put in command of the naval forces in Anhui and Jiangsu provinces to counter the Taiping rebels. After Zeng Guofan's Xiang Army recaptured Anqing from the rebels in 1861, Zeng wrote a memorial to the imperial court to praise Li, calling him "a talent with great potential", and sent Li back to Hefei to form a militia. Li managed to recruit enough men to form five battalions in 1862. Zeng Guofan ordered him to bring his troops along with him to Shanghai. Li and his men sailed past rebel-controlled territory along the Yangtze River in British steamboats – the rebels did not attack because Britain was a neutral party – and arrived in Shanghai, where they were commissioned as the Huai Army. Zeng Guofan recommended Li to serve as the xunfu of Jiangsu Province. After gaining ground in Jiangsu, Li focused on enhancing the Huai Army's capabilities, including equipping them with Western firearms and artillery. Within two years, the Huai Army's strength increased from 6,000 to about 60–70,000 men. Li's Huai Army combined forces later with Zeng Guofan's Xiang Army and Charles George Gordon's Ever Victorious Army and prepared to attack the Taiping rebels.

From 1863 to 1864, Li led the Huai Army to attack and recapture Suzhou, Changzhou and other rebel-controlled territories. For his contributions, Li was awarded the honorary appointment Crown Prince's Grand Protector (太子太保) and an imperial yellow jacket. After retaking Changzhou, and capturing and executing the rebel leader Chen Kunshu, Li received a jiduwei peerage in recognition of his achievements. An incident connected with the surrender of Suzhou soured Li's relationship with Gordon. According to an earlier arrangement with Gordon, the rebel leaders agreed to yield Nanjing to imperial forces on the condition that their lives would be spared. However, after the capture of Nanjing, Li ordered the rebel leaders to be executed. This breach of faith infuriated Gordon so much that he grabbed a rifle and wanted to shoot Li, but Li fled. By the end of 1864, the Taiping Rebellion had basically been suppressed by imperial forces. Li was awarded a noble peerage as "First Class Count Suyi" (一等肅毅伯) and the privilege of wearing a double-eyed peacock feather in his hat.

As Viceroy of Zhili
After the suppression of the Taiping Rebellion in 1864, Li assumed a civil office as the xunfu of Jiangsu Province for about two years. However, on the outbreak of the Nian Rebellion in Henan and Shandong provinces in 1866, he was ordered to lead troops into battle again. After some misadventures, Li managed to suppress the movement. In recognition of his contributions, he was appointed as Assistant Grand Secretary (協辦大學士).

In 1867, Li was appointed as the Viceroy of Huguang, where he remained until 1870, when the Tianjin Massacre necessitated his transfer to Tianjin to handle the diplomatic crisis with the French. He was given the concurrent appointments as Viceroy of Zhili Province and Beiyang Trade Minister (北洋通商大臣) to oversee various issues in Zhili, Shandong and Fengtian provinces, including trade, tariffs, diplomacy, coastal defence, and modernisation. He was also conferred the honorary position of "Grand Secretary of Wenhua Hall" (文華殿大學士).

From the time he became Viceroy of Zhili and Beiyang Trade Minister until his death, with a few intervals of retirement, he shaped the Qing Empire's foreign policy to a large extent. In 1876, he signed the Yantai Treaty with Sir Thomas Wade to end a diplomatic crisis with Britain caused by the murder of Augustus Raymond Margary in Yunnan Province. He also arranged treaties with Peru and the Tianjin Convention with Japan, and directed Chinese foreign policy in Korea. Among Li's projects to open China to the world on Chinese terms was support for the Chinese Educational Mission, which sent Chinese boys to the United States for education, starting in 1872. The mission was aborted in 1881.

On the death of the Tongzhi Emperor in 1875, Li introduced a large army into the capital and effected a coup which placed the Guangxu Emperor on the throne under the regency of the Empress Dowagers Ci'an and Cixi. In 1879, Li was awarded the honorary appointment Crown Prince's Grand Tutor (太子太傅).

In 1886, on the conclusion of the Sino-French War, Li arranged a treaty with the French. Li was impressed with the necessity of strengthening the Qing Empire, and while he was Viceroy of Zhili, he raised a large well-drilled and well-armed force, and spent vast sums both in fortifying Port Arthur and the Dagu forts and in strengthening the navy. For years, he had watched the successful reforms effected in Japan and had a well-founded dread of coming into conflict with the Japanese.

Establishing military academies

In 1885, Li founded the Tianjin Military Academy (天津武備學堂) to train Chinese military officers as part of his military reforms. The move was supported by Huai Army commander Zhou Shengchuan. The academy was to serve Huai Army and Green Standard Army officers. Various practical military, mathematics and science subjects were taught at the academy. The instructors were German military officers. Another programme was started at the academy for five years in 1887 to train teenagers as new military officers. Mathematics, practical and technical subjects, sciences, foreign languages, Chinese classics and history were taught at the school. Students also took exams. The Weihaiwei and Shanhaiguan military schools copied the Tianjin Military Academy's curriculum. The maritime defence fund supplied the budget for the Tianjin Military Academy, which was shared with the Tianjin Naval Academy.

First Sino-Japanese War
Because of his prominent role in Chinese diplomacy in Korea and strong political connections in Manchuria, Li found himself directing Chinese forces during the First Sino-Japanese War of 1894–1895. In fact, it was mostly the armies that he established and controlled that did the fighting, whereas other Chinese troops led by his political rivals did not come to their aid. Rampant corruption further weakened the Chinese military. For instance, one official misappropriated ammunition funds for personal use. As a result, shells ran out during battle, forcing one navy captain, Deng Shichang, to resort to ordering his ship to ram an enemy ship. The defeat of Li's modernised armed forces by the Japanese undermined his political standing, as well as the wider cause of the Self-Strengthening Movement.

Li had received the privilege of wearing a three-eyed peacock feather in his hat – a rare exception because three-eyed peacock feathers had previously been restricted to only members of the imperial clan – during Empress Dowager Cixi's 60th birthday celebrations in 1894. However, after the Chinese defeat in the war, Li was disgraced and stripped of his peacock feather. The Qing imperial court initially wanted to send Zhang Yinhuan (張蔭桓) and Shao Youlian (邵友濂) as their representatives to negotiate with the Japanese, but the Japanese rejected them. Li was selected to take on this mission and was given back his peacock feather.

On 24 March 1895, while negotiating with Japan's Prime Minister Itō Hirobumi and Foreign Affairs Minister Mutsu Munemitsu in Shimonoseki, Li was attacked by an assassin, Koyama Toyotarō (小山豐太郎), who shot him in the left cheek. Koyama was arrested by Japanese police later and he claimed that he desired for the war to continue.

Due to the public embarrassment caused by the attack, the Japanese agreed to the immediate ceasefire Li had urged in the days before, though fighting would continue on Taiwan and in the Penghu Islands. On 17 April 1895, Li signed the Treaty of Shimonoseki with the Japanese, thus ending the First Sino-Japanese War.

Tour of Russia, Europe and North America

In 1896, Li attended the coronation of Nicholas II of the Russian Empire on behalf of the Qing Empire and toured Europe, Canada and the United States, where he advocated reform of the American immigration policies that had greatly restricted Chinese immigration after the Chinese Exclusion Act of 1882 (renewed in 1892).

In a famous interview published by The New York Times on September 3, 1896, Li was asked whether he favored the introduction of the newspaper into China as developed in the U.S. or in Europe. Li's answer was stunningly honest: "There are newspapers in China, but the Chinese editors, unfortunately, do not tell the truth. They do not, as your papers, tell 'the truth, whole truth, and nothing but the truth.' The editors in China are great economizers of the truth; they tell only a part of it. They do not have, therefore, the great circulations that your papers have. Because this economy of the truth, our papers fail in the mission of a great press, to be one of the means of civilization."

While in Britain, he toured parts of the country by train, keeping with his desire to inspire railway development in his own country while constantly fighting against the prejudices of conservative leaders. He visited the industrial area in Barrow, North West England, and toured Lake Windermere on the steamer Tern operated by the Furness Railway Company. He also witnessed the 1896 Royal Naval Fleet Review at Spithead. It was during his visit to Britain in 1896 that Queen Victoria made him a Knight Grand Cross of the Royal Victorian Order.

Boxer Rebellion and death
In 1900, Li once more played a major diplomatic role in negotiating a settlement with the Eight-Nation Alliance forces which had invaded Beijing to put down the Boxer Rebellion. His early position was that the Qing Empire was making a mistake by supporting the Boxers against the foreign powers. During the Siege of the International Legations, Sheng Xuanhuai and other provincial officials suggested that the Qing imperial court give Li full diplomatic power to negotiate with foreign powers. Li telegraphed back to Sheng Xuanhuai on 25 June, describing the declaration of war a "false edict". This tactic gave the "Southeast Mutual Protection" provincial officials a justification not to follow Empress Dowager Cixi's declaration of war. Li refused to accept orders from the government for more troops when they were needed to fight against the foreigners, which he had available. Li controlled the Chinese telegraph service, whose despatches asserted falsely that Chinese forces had exterminated all foreigners in the siege and convinced many foreign readers.

In 1901, Li was the principal Chinese negotiator with the foreign powers which captured Beijing. On 7 September 1901, he signed the Boxer Protocol ending the Boxer Rebellion, and obtained the departure of the Eight-Nation Alliance at the price of huge indemnities for the Chinese. Exhausted from the negotiations, he died from liver inflammation two months later at Xianliang Temple in Beijing. The Guangxu Emperor posthumously honoured Li as Marquis Suyi of the First Class (一等肅毅候). This peerage was inherited by Li Guojie, who was assassinated in Shanghai on 21February 1939, allegedly as a result of his support for the Nanking Reformed Government.

Family
Li's ancestral family name was actually Xǔ (許). His ancestors had migrated from Hukou, Jiangxi Province to Hefei, Anhui Province. Li's eighth-great-grandfather, Xu Yingxi (許迎溪), had given up his second son, Xu Shen (許慎), for adoption by a relative, Li Xinzhuang (李心莊). Xu Shen and his descendants had taken Li (李) to be their family name since then. Li's father, Li Wen'an (李文安; 1801–1855), obtained a jinshi degree in the imperial examination in 1838 – the same year as Zeng Guofan. Li Wen'an also served as a langzhong (郎中) in the Ministry of Justice.

Li had one elder brother and four younger brothers; he was the second son in his family. His elder brother, Li Hanzhang (李瀚章; 1821–1899), served as a xunfu and zongdu in a number of provinces. His third brother, Li Hezhang (李鶴章; 1825–1880), served as a military officer. His fourth brother was Li Yunzhang (李蘊章), his fifth brother was Li Fengzhang (李鳳章), and his sixth brother was Li Zhaoqing (李昭慶; 1835–1873).

Li's first primary spouse, Lady Zhou (周氏), bore him a son, Li Jingyu (李經毓), who died prematurely. Lady Zhou died of illness in 1861.

Li's second primary spouse, Zhao Xiaolian (趙小蓮), bore him another son, Li Jingshu (李經述). Li Jingshu inherited his father's peerage as Marquis Suyi (肅毅侯), but died early. Li Jingshu's son, Li Guojie (李國傑; 1881–1939), inherited the Marquis Suyi peerage and served in a number of official positions in the final years of the Qing dynasty. He became an official and industrialist in the Republic of China later. Li Guojie also married the daughter of Natong (那桐; 1857–1925), who served in the Grand Secretariat and Grand Council.

Li's secondary spouse, Lady Mo (莫氏), bore him three sons: Li Jingyuan (李經遠), Li Jingmai (李經邁; 1876–1938) and Li Jingjin (李經進). Among the three, only Li Jingmai survived into adulthood. He served as the Qing Empire's Ambassador to Austria-Hungary and a Right Vice Secretary (右侍郎) in the Ministry of Civil Affairs (民政部).

Li had three daughters. One of them, Li Ju'ou (李菊藕), married Zhang Peilun (1848–1903) and bore the father of the writer Eileen Chang (1920–1995). The other two daughters married Guo Enhou (郭恩垕), the magistrate of Weifang County, and Ren Dehe (任德和), the zhushi (主事) of Yixing County.

Li also adopted Li Jingfang (1855–1934), a son of his sixth brother Li Zhaoqing. Li Jingfang served as the Qing Empire's Ambassador to Japan and a Left Vice Secretary (左侍郎) in the Ministry of Post and Telecommunications (郵傳部).

Li's brother Li Hanzhang (李瀚章) had a daughter named Li Peisheng (李佩生).

His grandson, Li Shiu Tong, would become a sexologist known for his work and relationship with his mentor and romantic partner Magnus Hirschfeld, and would posthumously be recognized as a researcher in his own right following the rediscovery of his manuscripts.

Honours

 * Imperial Order of the Double Dragon (China)
 * Honorary Knight Grand Cross of the Royal Victorian Order (United Kingdom).
 * Grand Cross of the Order of the Red Eagle, in Diamonds (Germany), 14 June 1896

Legacy and assessment
Li left a word as his self-evaluation: "To know me and judge me is a task for the next millennium" (知我罪我，付之千載).

Li was regarded favourably in the United States, owing to his reputation for welcoming foreign influence and his 1896 visit to the country. He was wrongly credited with inventing the American Chinese dish chop suey during the visit. In 1913, William Francis Mannix wrote and published a fabricated Memoirs of Li Hung Chang which received widespread praise before being exposed as a forgery in 1923.

His biographer William J. Hail argued that Li "did perhaps all he could for a land where the conservatism of the people, a reactionary officialdom, and unrestrained international rivalry made each step forward a matter of great difficulty," and praised him as "always progressive, yet patient and conciliatory, it was his fate to bear blame for failures which might have been avoided if he had had his way." The leader of China's New Culture Movement, Hu Shih, was also sympathetic, remarking that if Li had been allowed the opportunity, his achievements for China might have equalled the achievements of his Japanese counterpart, Itō Hirobumi, at the 1895 Treaty of Shimonoseki.

Chinese nationalists criticised Li's relations with the Western powers and Japan. Liang Qichao's 1902 biography of Li blamed him for China's woes and set the tone for further castigation. In Liang's view, Li was the chief culprit for the Self-Strengthening Movement, which these nationalists condemned for collaborating with the European imperialists and suppressing the masses. Liang Qichao's son, Liang Sicheng, denounced Li in 1951 for "selling out" the country. History textbooks in the People's Republic of China labelled Li as a "feudalist" and a traitor to the Chinese people. It was not until the 1980s that mainland historians began a serious debate of the sort which had been taking place in Taiwan.

Bribery controversy
Sergei Witte dismissed some rumours during Li's visit to Europe that Li was bribed. However, according to the Russian account, Li had urged the Russian government to build a three-million rubles "Li Hongzhang Foundation" to make Li and Zhang Yinheng to support the Sino-Russia railway treaty and Lushun-Dalian Rent Treaty, and a payment of 0.5 million rubles was confirmed. Ma Wenzhong questioned whether the Russian account was reliable.

Works

 * Trade Charter Precedents Collection (通商約章成案彙編 1886)

title: Li Hongzhang