An official website of the United States government
We show that there is an absolute constant c > 0 c>0 such that the following holds. For every n > 1 n > 1 , there is a 5-uniform hypergraph on at least 2 2 c n 1 / 4 2^{2^{cn^{1/4}}} vertices with independence number at most n n , where every set of 6 vertices induces at most 3 edges. The double exponential growth rate for the number of vertices is sharp. By applying a stepping-up lemma established by the first two authors, analogous sharp results are proved for k k -uniform hypergraphs. This answers the penultimate open case of a conjecture in Ramsey theory posed by Erdős and Hajnal in 1972.
more »
« less
C5 ${C}_{5}$ is almost a fractalizer
Abstract We determine the maximum number of induced copies of a 5‐cycle in a graph on vertices for every . Every extremal construction is a balanced iterated blow‐up of the 5‐cycle with the possible exception of the smallest level where for , the Möbius ladder achieves the same number of induced 5‐cycles as the blow‐up of a 5‐cycle on eight vertices. This result completes the work of Balogh, Hu, Lidický, and Pfender, who proved an asymptotic version of the result. Similarly to their result, we also use the flag algebra method, but we use a new and more sophisticated approach which allows us to extend its use to small graphs.
more »
« less
- PAR ID:
- 10404137
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Journal of Graph Theory
- Volume:
- 104
- Issue:
- 1
- ISSN:
- 0364-9024
- Page Range / eLocation ID:
- p. 220-244
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract In 2003, Bohman, Frieze, and Martin initiated the study of randomly perturbed graphs and digraphs. For digraphs, they showed that for every$$\alpha \gt 0$$, there exists a constant$$C$$such that for every$$n$$-vertex digraph of minimum semi-degree at least$$\alpha n$$, if one adds$$Cn$$random edges then asymptotically almost surely the resulting digraph contains a consistently oriented Hamilton cycle. We generalize their result, showing that the hypothesis of this theorem actually asymptotically almost surely ensures the existence of every orientation of a cycle of every possible length, simultaneously. Moreover, we prove that we can relax the minimum semi-degree condition to a minimum total degree condition when considering orientations of a cycle that do not contain a large number of vertices of indegree$$1$$. Our proofs make use of a variant of an absorbing method of Montgomery.more » « less
-
Abstract A “double star” is a tree with two internal vertices. It is known that the Gyárfás–Sumner conjecture holds for double stars, that is, for every double star , there is a function such that if does not contain as an induced subgraph then (where are the chromatic number and the clique number of ). Here we prove that can be chosen to be a polynomial.more » « less
-
Abstract We present progress on three old conjectures about longest paths and cycles in graphs. The first pair of conjectures, due to Lovász from 1969 and Thomassen from 1978, respectively, states that all connected vertex‐transitive graphs contain a Hamiltonian path, and that all sufficiently large such graphs even contain a Hamiltonian cycle. The third conjecture, due to Smith from 1984, states that for in every ‐connected graph any two longest cycles intersect in at least vertices. In this paper, we prove a new lemma about the intersection of longest cycles in a graph, which can be used to improve the best known bounds toward all the aforementioned conjectures: First, we show that every connected vertex‐transitive graph on vertices contains a cycle (and hence path) of length at least , improving on from DeVos [arXiv:2302:04255, 2023]. Second, we show that in every ‐connected graph with , any two longest cycles meet in at least vertices, improving on from Chen, Faudree, and Gould [J. Combin. Theory, Ser. B,72(1998) no. 1, 143–149]. Our proof combines combinatorial arguments, computer search, and linear programming.more » « less
-
Abstract What are the unavoidable induced subgraphs of graphs with large treewidth? It is well‐known that the answer must include a complete graph, a complete bipartite graph, all subdivisions of a wall and line graphs of all subdivisions of a wall (we refer to these graphs as the “basic treewidth obstructions”). So it is natural to ask whether graphs excluding the basic treewidth obstructions as induced subgraphs have bounded treewidth. Sintiari and Trotignon answered this question in the negative. Their counterexamples, the so‐called “layered wheels,” contain wheels, where awheelconsists of ahole(i.e., an induced cycle of length at least four) along with a vertex with at least three neighbors in the hole. This leads one to ask whether graphs excluding wheels and the basic treewidth obstructions as induced subgraphs have bounded treewidth. This also turns out to be false due to Davies' recent example of graphs with large treewidth, no wheels and no basic treewidth obstructions as induced subgraphs. However, in Davies' example there exist holes and vertices (outside of the hole) with two neighbors in them. Here we prove that a hole with a vertex with at least two neighbors in it is inevitable in graphs with large treewidth and no basic obstruction. Our main result is that graphs in which every vertex has at most one neighbor in every hole (that does not contain it) and with the basic treewidth obstructions excluded as induced subgraphs have bounded treewidth.more » « less
