Forcing graph

Last updated June 09, 2024

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] Forcing graphs play an important role in the study of pseudorandomness in graph sequences.

Definitions

Let $t(H, G) = .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}# labeled copies of H in G/v(G)v(H)$ , known as the subgraph density (in particular, $t (K 2, G)$ is the edge density of $G$ ). A sequence of graphs ${G n}$ is called quasi-random if, for all graphs $H$ , the edge density $t (K 2, G n)$ approaches some $p$ and $t (H, G n)$ approaches $p e(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 ${G n}$ where $t (K 2, G n)$ approaches $p$ as $n$ goes to infinity, ${G n}$ is quasi-random if $t (F, G n)$ approaches $p e (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.^[3]

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 (K 2, 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 ]}

Examples

The first forcing graph to be considered is the 4-cycle $C 4$ , 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 $C 2 t$ and complete bipartite graphs of the form $K 2, t$ with $t \geq 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^[3]

Forcing families

Forcing families provide a natural generalization of forcing graphs. A family of graphs F is forcing ${G n}$ is quasi-random whenever $t (F, G n)$ approaches $p e (F)$ for all $F \in$ F. Characterizing forcing families is much more challenging than characterizing forcing graphs, so there are few that are known. Known forcing families include:

${K 2, C 2 t}$ , where $t$ is a positive integer;
${C 2 s, C 2 t}$ , where $s$ and $t$ are positive integers with $s \neq t$ ;
${K 2, K 2, t}$ , where $t \geq 2$ ; and
${K 2, s, K 2, t}$ , where $s \neq t$ and $s, t \geq 2$ .^[1]

Forcing conjecture

The forcing conjecture was posed by Skokan and Thoma in 2004^[4] and formalized by Conlon, Fox, and Sudakov in 2010.^[3] 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, G n)$ approaches $p e (H)$ for every forest $H$ when ${G n}$ is a nearly regular (and not necessarily quasi-random) graph sequences.^[3] 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.^[3] Since trees are Sidorenko,^[5] all bipartite graphs would be Sidorenko.

Related Research Articles

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$ .)

Ronald Lewis Graham was an American mathematician credited by the American Mathematical Society as "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years". He was president of both the American Mathematical Society and the Mathematical Association of America, and his honors included the Leroy P. Steele Prize for lifetime achievement and election to the National Academy of Sciences.

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.

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.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of 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 mathematics, a universal graph is an infinite graph that contains every finite graph as an induced subgraph. A universal graph of this type was first constructed by Richard Rado and is now called the Rado graph or random graph. More recent work has focused on universal graphs for a graph family $F$ : that is, an infinite graph belonging to F that contains all finite graphs in $F$ . For instance, the Henson graphs are universal in this sense for the $i$ -clique-free graphs.

In mathematics, the Burr–Erdős conjecture was a problem concerning the Ramsey number of sparse graphs. The conjecture is named after Stefan Burr and Paul Erdős, and is one of many conjectures named after Erdős; it states that the Ramsey number of graphs in any sparse family of graphs should grow linearly in the number of vertices of the graph.

In graph theory, a factor of a graph G is a spanning subgraph, i.e., a subgraph that has the same vertex set as G. A k-factor of a graph is a spanning k-regular subgraph, and a k-factorization partitions the edges of the graph into disjoint k-factors. A graph G is said to be k-factorable if it admits a k-factorization. In particular, a 1-factor is a perfect matching, and a 1-factorization of a k-regular graph is a proper edge coloring with k colors. A 2-factor is a collection of cycles that spans all vertices of the graph.

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 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.$

Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it states that every bipartite polyhedral graph with three edges per vertex has a Hamiltonian cycle.

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 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.$

References

1 2 3 4 Chung, F. R. K.; Graham, R. L.; Wilson, R. M. (1989-12-01). "Quasi-random graphs". Combinatorica. 9 (4): 345–362. doi:10.1007/BF02125347. ISSN 1439-6912. S2CID 17166765.
↑ Hancock, Robert; Kabela, Adam; Král', Daniel; Martins, Taísa; Parente, Roberto; Skerman, Fiona; Volec, Jan (2023). "No additional tournaments are quasirandom-forcing". European Journal of Combinatorics. 108: Paper No. 103632, 10. arXiv: 1912.04243 . doi:10.1016/j.ejc.2022.103632. MR 4502205.
1 2 3 4 5 Conlon, David; Fox, Jacob; Sudakov, Benny (2010-10-20). "An Approximate Version of Sidorenko's Conjecture". Geometric and Functional Analysis. 20 (6): 1354–1366. arXiv: 1004.4236 . doi:10.1007/s00039-010-0097-0. ISSN 1016-443X. S2CID 1872674.
↑ Skokan, Jozef; Thoma, Lubos (2004-06-01). "Bipartite Subgraphs and Quasi-Randomness". Graphs and Combinatorics. 20 (2): 255–262. doi:10.1007/s00373-004-0556-1. ISSN 0911-0119. S2CID 2154492.
↑ SIDORENKO, A. F. (1992). "Inequalities for functionals generated by bipartite graphs". Discrete Mathematics and Applications. 2 (5). doi:10.1515/dma.1992.2.5.489. ISSN 0924-9265. S2CID 117471984.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:0-1] 1 2 3 4 Chung, F. R. K.; Graham, R. L.; Wilson, R. M. (1989-12-01). "Quasi-random graphs". Combinatorica. 9 (4): 345–362. doi:10.1007/BF02125347. ISSN 1439-6912. S2CID 17166765.

[2] Hancock, Robert; Kabela, Adam; Král', Daniel; Martins, Taísa; Parente, Roberto; Skerman, Fiona; Volec, Jan (2023). "No additional tournaments are quasirandom-forcing". European Journal of Combinatorics. 108: Paper No. 103632, 10. arXiv: 1912.04243 . doi:10.1016/j.ejc.2022.103632. MR 4502205.

[:1-3] 1 2 3 4 5 Conlon, David; Fox, Jacob; Sudakov, Benny (2010-10-20). "An Approximate Version of Sidorenko's Conjecture". Geometric and Functional Analysis. 20 (6): 1354–1366. arXiv: 1004.4236 . doi:10.1007/s00039-010-0097-0. ISSN 1016-443X. S2CID 1872674.

[4] Skokan, Jozef; Thoma, Lubos (2004-06-01). "Bipartite Subgraphs and Quasi-Randomness". Graphs and Combinatorics. 20 (2): 255–262. doi:10.1007/s00373-004-0556-1. ISSN 0911-0119. S2CID 2154492.

[5] SIDORENKO, A. F. (1992). "Inequalities for functionals generated by bipartite graphs". Discrete Mathematics and Applications. 2 (5). doi:10.1515/dma.1992.2.5.489. ISSN 0924-9265. S2CID 117471984.

[1]

[2]

[3]

[4]

[5]