Search

AbstractFix an integer $r \ge 3$. We consider metric spaces on npoints such that the distance between any two points lies in $\left\{ {1, \ldots ,r} \right\}$. Our main result describes their approximate structure for large n. As a consequence, we show that the number of these metric spaces is $\left\lceil {{{r + 1} \over 2}} \right\rceil ^{\left( {\matrix{ n \cr 2 \cr } } \right) + o\left( {n^2 } \right)} .$Related results in the continuous setting have recently been proved by Kozma, Meyerovitch, Peled, and Samotij [34]. When ris even, our structural characterization is more precise and implies that almost all such metric spaces have all distances at least $r/2$. As an easy consequence, when ris even, we improve the error term above from $o\left( {n^2 } \right)$to $o\left( 1 \right)$, and also show a labeled first-order 0-1 law in the language ${\cal L}_r $, consisting of rbinary relations, one for each element of $[r]$. In particular, we show the almost sure theory Tis the theory of the Fraïssé limit of the class of all finite simple complete edge-colored graphs with edge colors in $\left\{ {r/2, \ldots ,r} \right\}$.Our work can be viewed as an extension of a long line of research in extremal combinatorics to the colored setting, as well as an addition to the collection of known structures that admit logical 0-1 laws.

We consider the maximum chromatic number of hypergraphs consisting of cliques that have pairwise small intersections. Designs of the appropriate parameters produce optimal constructions, but these are generally known to exist only when the number of cliques is exponential in the clique size (Glock, Kühn, Lo, and Osthus, Mem. Amer. Math. Soc. 284(2023) v+131 pp; Keevash, Preprint; Rödl, Eur. J. Combin. 6 (1985) 69–78). We construct near designs where the number of cliques is polynomial in the clique size, and show that they have large chromatic number. The case when the cliques have pairwise intersections of size at most one seems particularly challenging. Here, we give lower bounds by analyzing a random greedy hypergraph process. We also consider the related question of determining the maximum number of caps in a finite projective/affine plane and obtain nontrivial upper and lower bounds.

Motivated by the Erdős–Szekeres convex polytope conjecture in Rd, we initiate the study of the following induced Ramsey problem for hypergraphs. Given integers n>k⩾5, what is the minimum integer gk(n)such that any k‐uniform hypergraph on gk(n)vertices with the property that any set of k+1vertices induces 0, 2, or 4 edges, contains an independent set of size n. Our main result shows that gk(n)>2cnk−4, where c=c(k).

A book of size bin a graph is an edge that lies in btriangles. Consider a graph Gwith nvertices and ⌋n2/4⌋; + 1 edges. Rademacher proved that Gcontains at least ⌋n/2⌋; triangles, and several authors proved that Gcontains a book of size at least n/6. We prove the following “linear combination” of these two results. Suppose that and the maximum size of a book in Gis less than αn/2. Then Gcontains at least triangles as n→Ȟ. This is asymptotically sharp. On the other hand, for every , there exists β>0 such that Gcontains at least βn3triangles. It remains an open problem to determine the largest possible β in terms of α. Our short proof uses the triangle removal lemma, although there is another approach which avoids this. © 2011 Wiley Periodicals, Inc. J Graph Theory

The Erdős‐Rényi and Projective Norm graphs are algebraically defined graphs that have proved useful in supplying constructions in extremal graph theory and Ramsey theory. Their eigenvalues have been computed and this yields an upper bound on their independence number. Here we show that in many cases, this upper bound is sharp in the order of magnitude. Our result for the Erdős‐Rényi graph has the following reformulation: the maximum size of a family of mutually non‐orthogonal lines in a vector space of dimension three over the finite field of order qis of order q3/2. We also prove that every subset of vertices of size greater than q2/2+ q3/2+ O(q) in the Erdős‐Rényi graph contains a triangle. This shows that an old construction of Parsons is asymptotically sharp. Several related results and open problems are provided. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 113–127, 2007

We explicitly construct four infinite families of irreducible triple systems with Ramsey‐Turán density less than the Turán density. Two of our families generalize isolated examples of Sidorenko 14, and the first author and Rödl 12. Our constructions also yield two infinite families of irreducible triple systems whose Ramsey‐Turán densities are exactly determined. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 211–216, 2006

For an l-graph $$ {\user1{\mathcal{G}}} $$, the Turán number $$ {\text{ex}}{\left( {n,{\user1{\mathcal{G}}}} \right)} $$is the maximum number of edges in an n-vertex l-graph $$ {\user1{\mathcal{H}}} $$containing no copy of $$ {\user1{\mathcal{G}}} $$. The limit $$ \pi {\left( {\user1{\mathcal{G}}} \right)} = \lim _{{n \to \infty }} {\text{ex}}{\left( {n,{\user1{\mathcal{G}}}} \right)}/{\left( {^{n}_{l} } \right)} $$is known to exist [8]. The Ramsey–Turán density $$ p{\left( {\user1{\mathcal{G}}} \right)} $$is defined similarly to $$ \pi {\left( {\user1{\mathcal{G}}} \right)} $$except that we restrict to only those $$ {\user1{\mathcal{H}}} $$with independence number o(n). A result of Erdős and Sós [3] states that $$ \pi {\left( {\user1{\mathcal{G}}} \right)} = p{\left( {\user1{\mathcal{G}}} \right)} $$as long as for every edge Eof $$ {\user1{\mathcal{G}}} $$there is another edge E′of $$ {\user1{\mathcal{G}}} $$for which |E∩E′|≥2. Therefore a natural question is whether there exists $$ {\user1{\mathcal{G}}} $$for which $$ p{\left( {\user1{\mathcal{G}}} \right)} < \pi {\left( {\user1{\mathcal{G}}} \right)} $$.For an l-graph $$ {\user1{\mathcal{G}}} $$, the Turán number $$ {\text{ex}}{\left( {n,{\user1{\mathcal{G}}}} \right)} $$is the maximum number of edges in an n-vertex l-graph $$ {\user1{\mathcal{H}}} $$containing no copy of $$ {\user1{\mathcal{G}}} $$. The limit $$ \pi {\left( {\user1{\mathcal{G}}} \right)} = \lim _{{n \to \infty }} {\text{ex}}{\left( {n,{\user1{\mathcal{G}}}} \right)}/{\left( {^{n}_{l} } \right)} $$is known to exist [8]. The Ramsey–Turán density $$ p{\left( {\user1{\mathcal{G}}} \right)} $$is defined similarly to $$ \pi {\left( {\user1{\mathcal{G}}} \right)} $$except that we restrict to only those $$ {\user1{\mathcal{H}}} $$with independence number o(n). A result of Erdős and Sós [3] states that $$ \pi {\left( {\user1{\mathcal{G}}} \right)} = p{\left( {\user1{\mathcal{G}}} \right)} $$as long as for every edge Eof $$ {\user1{\mathcal{G}}} $$there is another edge E′of $$ {\user1{\mathcal{G}}} $$for which |E∩E′|≥2. Therefore a natural question is whether there exists $$ {\user1{\mathcal{G}}} $$for which $$ p{\left( {\user1{\mathcal{G}}} \right)} < \pi {\left( {\user1{\mathcal{G}}} \right)} $$.

A triangle is a family of three sets A,B,Csuch that A∩B, B∩C, C∩Aare each nonempty, and . Let be a family of r-element subsets of an n-element set, containing no triangle. Our main result implies that for r≥ 3 and n≥ 3r/2, we have This settles a longstanding conjecture of Erdős [7], by improving on earlier results of Bermond, Chvátal, Frankl, and Füredi. We also show that equality holds if and only if consists of all r-element subsets containing a fixed element.

We construct an incidence structure using certain points and lines in finite projective spaces. The structural properties of the associated bipartite incidence graphs are analyzed. These n× nbipartite graphs provide constructions of C6‐free graphs with Ω(n4/3edges, C10‐free graphs with Ω(n6/5) edges, and Θ(7,7,7)‐free graphs with Ω(n8/7) edges. Each of these bounds is sharp in order of magnitude. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 1–10, 2005

An explicit coloring of the edges of K n is constructed such that every copy of K 4 has at least four colors on its edges. As n ? 8, the number of colors used is n 1/2+ o(1). This improves upon the previous bound of O( n 2/3) due to Erdos and Gyárfás obtained by probabilistic methods. The exponent 1/2 is optimal, since it is known that at least O( n 1/2) colors are required in such a coloring. The coloring is related to constructions giving lower bounds for the multicolor Ramsey number r k( C 4). It is more complicated however, because of restrictions imposed on interactions between color classes.

In this paper we show that every simple cubic graph on nvertices has a set of at least ⌈ n/4 ⌉ disjoint 2‐edge paths and that this bound is sharp. Our proof provides a polynomial time algorithm for finding such a set in a simple cubic graph. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 57–79, 2003

In this paper we show that every simple cubic graph on n vertices has a set of at least ⌈ n/4 ⌉ disjoint 2-edge paths and that this bound is sharp. Our proof provides a polynomial time algorithm for finding such a set in a simple cubic graph. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 57–79, 2003

Let f(n) be the minimum number of colors required to color the edges of Kn,n such that every copy of K3,3 receives at least three colors on its edges. We prove that $$(0.62+o(1))\sqrt{n}< \, f(n)< \, (1+o(1))\sqrt{n}$$, where the upper bound is obtained by an explicit edge-coloring. This complements earlier results of Axenovich, Füredi, and Mubayi [1]. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 193–198, 2003

Let f(n) be the minimum number of colors required to color the edges of Kn,nsuch that every copy of K3,3receives at least three colors on its edges. We prove that $$(0.62+o(1))\sqrt{n}< \, f(n)< \, (1+o(1))\sqrt{n}$$, where the upper bound is obtained by an explicit edge‐coloring. This complements earlier results of Axenovich, Füredi, and Mubayi [1]. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 193–198, 2003

Abstract.:  We prove that for every family of n pairwise intersecting simple closed planar curves in general position, at least (4/5)n 2−O(n) points lie on more than one curve. This improves the previous lower bound of (3/4)n 2−O(n) due to Richter and Thomassen.

Abstract.:  A mixed hypergraph is a triple ℋ=(X, ?, ?), where X is the vertex set, and each of ?, ? is a list of subsets of X. A strict k-coloring of ℋ is a surjection c:X→{1,…,k} such that each member of ? has two vertices assigned a common value and each member of ? has two vertices assigned distinct values. The feasible set of H is {k: H has a strict k-coloring}. Among other results, we prove that a finite set of positive integers is the feasible set of some mixed hypergraph if and only if it omits the number 1 or is an interval starting with 1. For the set {s,t} with 2≤s≤t−2, the smallest realization has 2t−s vertices. When every member of ?∪? is a single interval in an underlying linear order on the vertices, the feasible set is also a single interval of integers.

Given a family ℱ of r-graphs, let ex(n, ℱ) be the maximum number of edges in an n-vertex r-graph containing no member of ℱ. Let C(r) 4 denote the family of r-graphs with distinct edges A, B, C, D, such that A ∩ B = C ∩ D = Ø and A ∪ B = C ∪ D. For s1  …  sr, let K(r) (s1,…,sr) be the complete r-partite r-graph with parts of sizes s1,…,sr. Füredi conjectured over 15 years ago that ex(n,C(3)4)  (n2) for sufficiently large n. We prove the weaker result ex(n, {C(3)4, K(3)(1,2,4)})  (n2). Generalizing a well-known conjecture for the Turán number of bipartite graphs, we conjecture that ex(n, K(r)(s1,…,sr)) = Θ(nr−1/s), where s = Πr−1i=1 si. We prove this conjecture when s1 = … = sr−2 = 1 and (i) sr−1 = 2, (ii) sr−1 = sr = 3, (iii)sr > (sr−1−1)!. In cases (i) and (ii), we determine the asymptotic value of ex(n,K(r)(s1,…,sr)). We also provide an explicit construction giving ex(n,K(3)(2,2,3)) > (1/6−o(1))n8/3. This improves upon the previous best lower bound of Ω(n29/11) obtained by probabilistic methods. Several related open problems are also presented.

For a graph G, let a(G) denote the maximum size of a subset of vertices that induces a forest. Suppose that G is connected with n vertices, e edges, and maximum degree Δ. Our results include: (a) if Δ ≤ 3, and G ≠ K4, then a(G) ≥ n − e/4 − 1/4 and this is sharp for all permissible e ≡ 3 (mod 4); and (b) if Δ ≥ 3, then a(G) ≥ α(G) + (n − α(G))/(Δ − 1)². Several problems remain open. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 113–123, 2001

For a graph G, let a(G) denote the maximum size of a subset of vertices that induces a forest. Suppose that G is connected with n vertices, e edges, and maximum degree Δ. Our results include: (a) if Δ ≤ 3, and G ≠ K4, then a(G) ≥ n − e/4 − 1/4 and this is sharp for all permissible e ≡ 3 (mod 4); and (b) if Δ ≥ 3, then a(G) ≥ α(G) + (n − α(G))/(Δ − 1)². Several problems remain open. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 113–123, 2001

For a graph G, let a(G) denote the maximum size of a subset of vertices that induces a forest. Suppose that Gis connected with nvertices, eedges, and maximum degree Δ. Our results include: (a) if Δ ≤ 3, and G≠ K4, then a(G) ≥ n− e/4 − 1/4 and this is sharp for all permissible e≡ 3 (mod 4); and (b) if Δ ≥ 3, then a(G) ≥ α(G) + (n− α(G))/(Δ − 1)2. Several problems remain open. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 113–123, 2001

An (r, l)‐system is an r‐uniform hypergraph in which every set of lvertices lies in at most one edge. Let mk(r, l) be the minimum number of edges in an (r, l)‐system that is not k‐colorable. Using probabilistic techniques, we prove that$$a_{r,l}(k^{r-1}{\rm ln}k)^{l/(l-1)}\leq m_k(r,l)\leq b_{r,l}(k^{r-1}{\rm ln}k)^{l/(l-1)},$$where br, lis explicitly defined and ar, lis sufficiently small. We also give a different argument proving (for even k)$$m_k(r,l)\leq a'_{r,l}k^{(r-1)l/(l-1)}.$$where a′r, l=(r−l+1)/r(2r−1re)−l/(l−1).

Let nand kbe fixed positive integers. A collection Cof k-sets of [n] is a completely separating system if, for all distinct i, j∈[n], there is an S∈Cfor which i∈Sand j∉S. Let R(n, k) denote the minimum size of such a C. Our results include showing that if nkis a sequence with k⪡nk⪡k1+εfor every ε>0, then[formula]

Abstract.: The eccentricity of a vertex v in a graph is the maximum of the distances from v to all other vertices. The diameter of a graph is the maximum of the eccentricities of its vertices. Fix the parameters n, d, c. Over all graphs with order n and diameter d, we determine the maximum (within 1) and the minimum of the number of vertices with eccentricity c.

An edge‐labeling fof a graph Gis an injection from E(G) to the set of integers. The edge‐bandwidthof Gis B′(G) = minf{B′(f)} where B′(f) is the maximum difference between labels of incident edges of G. The theta graphΘ(l1,…,lm) is the graph consisting of mpairwise internally disjoint paths with common endpoints and lengths l1≤ ··· ≤ lm. We determine the edge‐bandwidth of all theta graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 89–98, 2000

An edge-labeling f of a graph G is an injection from E(G) to the set of integers. The edge-bandwidth of G is B'(G) = minf {B'(f)} where B'(f) is the maximum difference between labels of incident edges of G. The theta graph Θ(l1,…,lm) is the graph consisting of m pairwise internally disjoint paths with common endpoints and lengths l1 ≤ ··· ≤ lm. We determine the edge-bandwidth of all theta graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 89–98, 2000

Given graphs H1,…, Hk, let f(H1,…, Hk) be the minimum order of a graph Gsuch that for each i, the induced copies of Hiin Gcover V(G). We prove constructively that f(H1, H2) ≤ 2(n(H1) + n(H2) − 2); equality holds when H1= H2= Kn. We prove that f(H1, Kn) = n+ 2√δ(H1)n+ O(1) as n→ ∞. We also determine f(K1, m−1, Kn) exactly. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 180–190, 2000

Given graphs H1,…, Hk, let f(H1,…, Hk) be the minimum order of a graph G such that for each i, the induced copies of Hi in G cover V(G). We prove constructively that f(H1, H2) ≤ 2(n(H1) + n(H2) − 2); equality holds when H1 = H2 = Kn. We prove that f(H1, Kn) = n + 2√δ(H1)n + O(1) as n → ∞. We also determine f(K1, m −1, Kn) exactly. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 180–190, 2000

Given graphs G and H, a coloring of E(G) is called an (H,q)-coloring if the edges of every copy of H⊆G together receive at least q colors. Let r(G, H, q) denote the minimum number of colors in an (H, q)-coloring of G. We determine, for fixed p, the smallest q for which r(Kn, n, Kp, p, q) is linear in n, the smallest q for which it is quadratic in n. We also determine the smallest q for which r(Kn, n, Kp, p, q)=n2−O(n), and the smallest q for which r(Kn, n, Kp, p, q)=n2−O(1). Our results include showing that r(Kn, n, K2, t+1, 2) and r(Kn, K2, t+1, 2) are both (1+o(1)) n/t as n→∞, thereby proving a special case of a conjecture of Chung and Graham. Finally, we determine the exact value of r(Kn, n, K3, 3, 8), and prove that 2n/3r(Kn, n, C4, 3)n+1. Several problems remain open.

We prove that for k≥ 5, every (2k+ 2)‐element graphic sequence of positive terms with sum at least 4k(k− 1) can be realized by a graph containing Kk+1. Also, this bound is sharp. Furthermore, for 2k+ 3 ≤ n≤ k(5k− 11)/(2k− 4), we construct a graphic n‐element positive sequence with sum (2k− 4)(2k− 1) + 2(n− 1) that has no realization containing Kk+1. This construction partially answers a question of Erdős et al. in the negative. © John Wiley & Sons, Inc. J Graph Theory 34: 20–29, 2000

We prove that for k ≥ 5, every (2k + 2)-element graphic sequence of positive terms with sum at least 4k(k − 1) can be realized by a graph containing Kk+1. Also, this bound is sharp. Furthermore, for 2k + 3 ≤ n ≤ k(5k − 11)/(2k − 4), we construct a graphic n-element positive sequence with sum (2k − 4)(2k − 1) + 2(n − 1) that has no realization containing Kk+1. This construction partially answers a question of Erdős et al. in the negative. © John Wiley & Sons, Inc. J Graph Theory 34: 20–29, 2000

: with colors in which the edges of every copy of together receive at least 3 colors. We prove that this construction also has the property that at least colors appear on the edges of every copy of for .

f: (l,k) be the minimum n with the property that every coloring yields either with , or with all distinct. We prove that if , then as . This supports the conjecture of Lefmann, Rödl, and Thomas that .

Suppose Gis a graph on nvertices with minimum degree r. Using standard random methods it is shown that there exists a two-coloring of the vertices of Gwith colors, +1 and −1, such that all closed neighborhoods contain more 1's than −1's, and all together the number of 1's does not exceed the number of −1's by more than (4logr/r+1/r)n. For large rthis greatly improves earlier results and is almost optimal, since starting with an Hadamard matrix of order r, a bipartite r-regular graph is constructed on 4rvertices with signed domination number at least (1/2) r−O(1). The determination of limn→∞γs(G)/nremains open and is conjectured to be Θ(1/r).

A (k; g)‐cageis a graph of minimum order among k‐regular graphs with girth g. We show that for every cutset Sof a (k; g)‐cage G, the induced subgraph G[S] has diameter at least ⌊g/2⌋, with equality only when distance ⌊g/2⌋ occurs for at least two pairs of vertices in G[S]. This structural property is used to prove that every (k; g)‐cage with k≥ 3 is 3‐connected. This result supports the conjecture of Fu, Huang, and Rodger that every (k; g)‐cage is k‐connected. A nonseparating g‐cycle Cin a graph Gis a cycle of length gsuch that G− V(C) is connected. We prove that every (k; g)‐cage contains a nonseparating g‐cycle. For even g, we prove that every g‐cycle in a (k; g)‐cage is nonseparating. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 35–44, 1998

A (k; g)-cage is a graph of minimum order among k-regular graphs with girth g. We show that for every cutset S of a (k; g)-cage G, the induced subgraph G[S] has diameter at least ⌊g/2⌋, with equality only when distance ⌊g/2⌋ occurs for at least two pairs of vertices in G[S]. This structural property is used to prove that every (k; g)-cage with k ≥ 3 is 3-connected. This result supports the conjecture of Fu, Huang, and Rodger that every (k; g)-cage is k-connected. A nonseparating g-cycle C in a graph G is a cycle of length g such that G − V(C) is connected. We prove that every (k; g)-cage contains a nonseparating g-cycle. For even g, we prove that every g-cycle in a (k; g)-cage is nonseparating. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 35–44, 1998

: is constructed such that every copy of has at least three colors on its edges. As , the number of colors used is . This improves upon the previous probabilistic bound of due to Erdős and Gyrfs.