 | The topic of this article may not meet Wikipedia's general notability guideline .(June 2022) |
In graph theory, a forcing graph is one whose density determines whether a graph sequence is quasi-random. The term was first coined by Chung, Graham, and Wilson in 1989., [1] and forcing graphs play an important role in the study of pseudorandomness in graph sequences.
Let t(H, G) = # labeled copies of H in G/v(G)v(H), known as the subgraph density (in particular, t(K2, G) is the edge density of G). A sequence of graphs {Gn} is called quasi-random if, for all graphs H, the edge density t(K2, Gn) approaches some p and t(H, Gn) approaches pe(H) as n increases, where e(H) is the number of edges in H. Intuitively, this means that a graph sequence with a given edge density has the number of graph homomorphisms that one would expect in a random graph sequence. A graph F is called forcing if for all graph sequences {Gn} where t(K2, Gn) approaches p as n goes to infinity, {Gn} is quasi-random if t(F, Gn) approaches pe(F). In other words, one can verify that a sequence of graphs is quasi-random by just checking the homomorphism density of a single graph. [2]
There is a second definition of forcing graphs using the language of graphons. Formally, a graph is called forcing if every graphon W such that t(F, W) = t(K2, W)e(F) is constant. Intuitively, it makes sense that these definitions are related. The constant graphon W(x, y) = p represents the Erdős–Rényi random graph G(n, p), so one could expect it to have a close relationship with quasi-random graphs. In fact, these definitions are equivalent.[ citation needed ]
The first forcing graph to be considered is the 4-cycle C4, as it bears a close relationship with other conditions of quasi-randomness. It was shown in the same paper by Chung, Graham, and Wilson that every even cycle C2t and complete bipartite graphs of the form K2,t with t ≥ 2 are forcing. [1] Conlon, Fox, and Sudakov expanded this last result to include all bipartite graphs with two vertices in one part that are complete to the other part [2]
Forcing families provide a natural generalization of forcing graphs. A family of graphs F is forcing {Gn} is quasi-random whenever t(F, Gn) approaches pe(F) for all F∈F. Characterizing forcing families is much more challenging than characterizing forcing graphs, so there are few that are known. Known forcing families include:
The forcing conjecture was posed by Skokan and Thoma in 2004 [3] and formalized by Conlon, Fox, and Sudakov in 2010. [2] It provides a characterization for forcing graphs, formalized as follows:
A graph is forcing if and only if it is bipartite and contains a cycle.
One direction of this claim is well-known. Chung, Graham, and Wilson showed that if a graph has an odd cycle, it cannot be forcing, [1] so if a graph is forcing, then it must be bipartite. Also, Conlon, Fox, and Sudakov argued that t(H, Gn) approaches pe(H) for every forest H when {Gn} is a nearly regular (and not necessarily quasi-random) graph sequences. [2] Thus, a forcing graph must be bipartite and have at least one cycle. The other direction is yet to be proven, but no forcing graph that does not have both of these properties has been found.
The forcing conjecture also implies Sidorenko's conjecture, a long-standing conjecture in the field. It is known that all forcing graphs are Sidorenko, so if the forcing conjecture is true, then all bipartite graphs with at least one cycle would be Sidorenko. [2] Since trees are Sidorenko, [4] all bipartite graphs would be Sidorenko.
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices. (Here R(r, s) signifies an integer that depends on both r and s.)
Fan-Rong King Chung Graham, known professionally as Fan Chung, is an American mathematician who works mainly in the areas of spectral graph theory, extremal graph theory and random graphs, in particular in generalizing the Erdős–Rényi model for graphs with general degree distribution.
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges.
The Turán graph, denoted by , is a complete multipartite graph; it is formed by partitioning a set of vertices into subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to different subsets. Where and are the quotient and remainder of dividing by , the graph is of the form , and the number of edges is
Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local substructure. Results in extremal graph theory deal with quantitative connections between various graph properties, both global and local, and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy? A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objects of study in extremal graph theory.
In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices.
In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.
In graph theory, a graph is said to be a pseudorandom graph if it obeys certain properties that random graphs obey with high probability. There is no concrete definition of graph pseudorandomness, but there are many reasonable characterizations of pseudorandomness one can consider.
In mathematics, Paley graphs are undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, which yield an infinite family of symmetric conference matrices. Paley graphs allow graph-theoretic tools to be applied to the number theory of quadratic residues, and have interesting properties that make them useful in graph theory more generally.
In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.
In a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets S and T, such that the number of edges between S and T is as large as possible. Finding such a cut is known as the max-cut problem.
In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph , find the maximal number of edges an -vertex graph can have such that it does not have a subgraph isomorphic to . In this context, is called a forbidden subgraph.
In graph theory and statistics, a graphon is a symmetric measurable function , that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs.
David Conlon is an Irish mathematician who is a Professor of Mathematics at the California Institute of Technology. His research interests are in Hungarian-style combinatorics, particularly Ramsey theory, extremal graph theory, combinatorial number theory, and probabilistic methods in combinatorics. He proved the first superpolynomial improvement on the Erdős–Szekeres bound on diagonal Ramsey numbers. He won the European Prize in Combinatorics in 2011 for his work in Ramsey theory and for his progress on Sidorenko's conjecture, and the Whitehead Prize in 2019.
In the mathematical field of extremal graph theory, homomorphism density with respect to a graph is a parameter that is associated to each graph in the following manner:
Sidorenko's conjecture is a conjecture in the field of graph theory, posed by Alexander Sidorenko in 1986. Roughly speaking, the conjecture states that for any bipartite graph and graph on vertices with average degree , there are at least labeled copies of in , up to a small error term. Formally, it provides an intuitive inequality about graph homomorphism densities in graphons. The conjectured inequality can be interpreted as a statement that the density of copies of in a graph is asymptotically minimized by a random graph, as one would expect a fraction of possible subgraphs to be a copy of if each edge exists with probability .
In graph theory, the Graham–Pollak theorem states that the edges of an -vertex complete graph cannot be partitioned into fewer than complete bipartite graphs. It was first published by Ronald Graham and Henry O. Pollak in two papers in 1971 and 1972, in connection with an application to telephone switching circuitry.
In mathematics, a quasirandom group is a group that does not contain a large product-free subset. Such groups are precisely those without a small non-trivial irreducible representation. The namesake of these groups stems from their connection to graph theory: bipartite Cayley graphs over any subset of a quasirandom group are always bipartite quasirandom graphs.
In graph theory, an area of mathematics, common graphs belong to a branch of extremal graph theory concerning inequalities in homomorphism densities. Roughly speaking, is a common graph if it "commonly" appears as a subgraph, in a sense that the total number of copies of in any graph and its complement is a large fraction of all possible copies of on the same vertices. Intuitively, if contains few copies of , then its complement must contain lots of copies of in order to compensate for it.