We show that if a sequence of dense graphs has the property that for every fixed graph , the density of copies of in tends to a limit, then there is a natural “limit object,” namely a symmetric measurable function . This limit object determines all the limits of subgraph densities. Conversely, every such function arises as a limit object. We also characterize graph parameters that are obtained as limits of subgraph densities by the “reflection positivity” property. Along the way we introduce a rather general model of random graphs, which seems to be interesting on its own right.
A weighting of the edges of a graph is called vertex-coloring if the weighted degrees of the vertices yield a proper coloring of the graph. In this paper we show that such a weighting is possible from the weight set for all graphs not containing components with exactly 2 vertices.
The main theorem of this paper provides partial results on some major open problems in graph theory, such as Tutteʼs 3-flow conjecture (from the 1970s) that every 4-edge connected graph admits a nowhere-zero 3-flow, the conjecture of Jaeger, Linial, Payan and Tarsi (1992) that every 5-edge-connected graph is -connected, Jaegerʼs circular flow conjecture (1984) that for every odd natural number , every -edge-connected graph has a modulo -orientation, etc. It was proved recently by Thomassen that, for every odd number , every -edge-connected graph has a modulo -orientation; and every 8-edge-connected graph is -connected and admits therefore a nowhere-zero 3-flow. In the present paper, Thomassenʼs method is refined to prove the following: . As a special case of the main result, 6 3 . Note that it was proved by Kochol (2001) that it suffices to prove the 3-flow conjecture for 5-edge-connected graphs.
A perfect matching in a 4-uniform hypergraph on vertices is a subset of disjoint edges. We prove that if is a sufficiently large 4-uniform hypergraph on vertices such that every vertex belongs to more than edges, then contains a perfect matching. A construction due to Hàn, Person, and Schacht shows that this result is the best possible.
We construct a polynomial-time algorithm to approximate the branch-width of certain symmetric submodular functions, and give two applications. The first is to graph “clique-width.” Clique-width is a measure of the difficulty of decomposing a graph in a kind of tree-structure, and if a graph has clique-width at most then the corresponding decomposition of the graph is called a “ -expression.” We find (for fixed ) an -time algorithm that, with input an -vertex graph, outputs either a -expression for the graph, or a witness that the graph has clique-width at least . (The best earlier algorithm, by Johansson [Ö. Johansson, -approximative -decomposition in time (extended abstract), in: Graph-Theoretic Concepts in Computer Science, Boltenhagen, 2001, in: Lecture Notes in Comput. Sci., vol. 2204, Springer, Berlin, 2001, pp. 229–240], constructs a -expression for graphs of clique-width at most .) It was already known that several graph problems, NP-hard on general graphs, are solvable in polynomial time if the input graph comes equipped with a -expression (for fixed ). As a consequence of our algorithm, the same conclusion follows under the weaker hypothesis that the input graph has clique-width at most (thus, we no longer need to be provided with an explicit -expression). Another application is to the area of matroid branch-width. For fixed , we find an -time algorithm that, with input an -element matroid in terms of its rank oracle, either outputs a branch-decomposition of width at most or a witness that the matroid has branch-width at least . The previous algorithm by Hliněný [P. Hliněný, A parametrized algorithm for matroid branch-width, SIAM J. Comput. 35 (2) (2005) 259–277] works only for matroids represented over a finite field.
We show that, for each natural number , every graph (possibly with multiple edges but with no loops) of edge-connectivity at least has an orientation with any prescribed outdegrees modulo provided the prescribed outdegrees satisfy the obvious necessary conditions. For the edge-connectivity 8 suffices. This implies the weak 3-flow conjecture proposed in 1988 by Jaeger (a natural weakening of Tutteʼs 3-flow conjecture which is still open) and also a weakened version of the more general circular flow conjecture proposed by Jaeger in 1982. It also implies the tree-decomposition conjecture proposed in 2006 by Bárat and Thomassen when restricted to stars. Finally, it is the currently strongest partial result on the -flow conjecture by Goddyn and Seymour.
A brick is a 3-connected graph such that the graph obtained from it by deleting any two distinct vertices has a perfect matching. A brick is minimal if for every edge the deletion of results in a graph that is not a brick. We prove a generation theorem for minimal bricks and two corollaries: (1) for , every minimal brick on 2 vertices has at most edges, and (2) every minimal brick has at least three vertices of degree three.
We introduce a new variant of graph coloring called which generalizes list coloring and allows for reductions previously only possible for ordinary coloring. Using this tool, we prove that excluding cycles of lengths 4 to 8 is sufficient to guarantee 3-choosability of a planar graph, thus answering a question of Borodin.
Let be a graph. A hypergraph is called if it can be obtained by replacing each edge in by a hyperedge containing it. Let be a family of graphs. The of the family Berge- is the maximum possible number of edges in an -uniform hypergraph on vertices containing no Berge- as a subhypergraph (for every ) and is denoted by . We determine the asymptotics for the Turán number of Berge- by showing for any given . We study the analogous question for linear hypergraphs and show We also prove general upper and lower bounds on the Turán numbers of a class of graphs including , , and for . Our bounds improve the results of Gerbner and Palmer , Füredi and Özkahya , Timmons , and provide a new proof of a result of Jiang and Ma .
The families are called if there are no pairwise disjoint satisfying . We determine for all values . The result provides a far-reaching generalization of an important classical result of Kleitman. The well-known Erdős Matching Conjecture suggests the largest size of a family with no pairwise disjoint sets. After more than 50 years its full solution is still not in sight. In the present paper we provide a Hilton–Milner-type stability theorem for the Erdős Matching Conjecture in a relatively wide range, in particular, for with depending on only. This is a considerable improvement of a classical result due to Bollobás, Daykin and Erdős. We apply our results to advance in the following anti-Ramsey-type problem, proposed by Özkahya and Young. Let be the minimum number of colors such that in any coloring of the -element subsets of with (non-empty) colors there is a of size , that is, sets of different colors that are pairwise disjoint. We prove a stability result for the problem, which allows to determine for all and . Some other consequences of our results are presented as well.
We consider a natural graph operation that is a certain inverse (formally: the right adjoint) to taking the -th power of a graph. We show that it preserves the topology (the -homotopy type) of the box complex, a basic tool in applications of topology in combinatorics. Moreover, we prove that the box complex of a graph admits a -map (an equivariant, continuous map) to the box complex of a graph if and only if the graph admits a homomorphism to , for high enough . This allows to show that if Hedetniemi's conjecture on the chromatic number of graph products is true, then the following analogous conjecture in topology is also true: If and are -spaces (finite -simplicial complexes) such that admits a -map to the -dimensional sphere, then or itself admits such a map. We discuss this and other implications, arguing the importance of the topological conjecture.
We prove that every sufficiently large 6-connected graph of bounded tree-width either has a K minor, or has a vertex whose deletion makes the graph planar. This is a step toward proving that the same conclusion holds for all sufficiently large 6-connected graphs. Jørgensen conjectured that it holds for all 6-connected graphs.
For two graphs and with no isolated vertices and for an integer , let denote the maximum possible number of copies of in an -free graph on vertices. The study of this function when is a single edge is the main subject of extremal graph theory. In the present paper we investigate the general function, focusing on the cases of triangles, complete graphs, complete bipartite graphs and trees. These cases reveal several interesting phenomena. Three representative results are: The first result improves (slightly) an estimate of Bollobás and Győri. The proofs combine combinatorial and probabilistic arguments with simple spectral techniques.
A two-coloring of the vertices of the hypergraph by red and blue has discrepancy if is the largest difference between the number of red and blue points in any edge. Let be the fewest number of edges in an -uniform hypergraph without a coloring with discrepancy 0. Erdős and Sós asked: is unbounded? N. Alon, D. J. Kleitman, C. Pomerance, M. Saks and P. Seymour proved upper and lower bounds in terms of the smallest non-divisor (snd) of (see ). We refine the upper bound as follows:
We prove that there exists a function such that for any positive integer , if is a strongly 4 -connected tournament with minimum out-degree at least , then is -linked. This resolves a conjecture of Pokrovskiy up to a factor of 2 of the required connectivity. Along the way, we show that a tournament with sufficiently large minimum out-degree contains a subdivision of a complete directed graph. This result may be of independent interest.
Let be a graph with possible multiple edges but no loops. The density of , denoted by , is defined as . Goldberg (1973) and Seymour (1974) independently conjectured that if the chromatic index satisfies then , which is commonly regarded as Goldberg's conjecture. An equivalent conjecture, usually credited to Jakobsen, states that for any odd integer , if then . The Tashkinov tree technique, a common generalization of Vizing fans and Kierstead paths for multigraphs, has emerged as the main tool to attack these two conjectures. On the other hand, Asplund and McDonald recently showed that there is a limitation to this method. In this paper, we will go beyond Tashkinov trees and provide a much larger extended structure, using which we see hope to tackle the conjecture. Applying this new technique, we show that the Goldberg's conjecture holds for graphs with or and the Jakobsen Conjecture holds for , where the previously known best bound is 23. We also improve a number of other related results.
Let be a positive integer at least 2. A graph is -critical if it can be colored in no fewer than colors and its proper subgraphs can be colored in fewer than colors. T. Gallai asked whether a -critical graph on vertices contains distinct -critical subgraphs. This paper gives an affirmative answer to Gallai's question restricted to 4-critical graphs by proving they contain at least odd cycles. For 2-connected nonbipartite graphs, it is shown that the cycle space of such a graph is generated by its odd cycles and that its cyclomatic number provides a sharp lower bound for the number of its odd cycles. For 3-connected nonbipartite graphs, it is shown that the cycle space of such a graph is generated by the set of odd cycles containing any fixed vertex. An initially bipartite ear decomposition is described and is used to show that these graphs contain a spanning 2-connected bipartite subgraph, and contain at least as many odd cycles as the number of their vertices.
We study the -decomposition threshold for a given graph . Here an -decomposition of a graph is a collection of edge-disjoint copies of in which together cover every edge of . (Such an -decomposition can only exist if is -divisible, i.e. if and each vertex degree of can be expressed as a linear combination of the vertex degrees of .) The -decomposition threshold is the smallest value ensuring that an -divisible graph on vertices with has an -decomposition. Our main results imply the following for a given graph , where is the fractional version of and : In particular, (i) implies that . Our proof involves further developments of the recent ‘iterative’ absorbing approach.