ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Conjecture 4.

  1. (Behzad, Chartrand, Wall [2]) The minimum number of vertices in an r-regular digraph G with girth g is r(g − 1) + 1.

Behzad, Chartrand and Wall give an example achieving this by placing r(g − 1) + 1 vertices on a circle with each vertex having edges to the next r vertices in clockwise order. The Caccetta-H¨ aggkvist Conjecture is a generalization of this earlier conjecture. The Behzad-Chartrand-Wall conjecture was proved for the following special cases: 3• r = 2 by Behzad [1]

• r = 3 by Bermond [3]

• Vertex-transitive graphs by Hamidoune [16]

• If δ+

G

≥ r, then g ≤ 3d n

r

ln( 2+ √7

3

)e ≈ 1.312 n

r

by Shen [31].

5 Related Results

Theorem 5.

  1. (Shen [30]) For a digraph G on n vertices, if δ+

G

≥ r, and n ≥ 2r2 − 3r + 1,then G has a cycle of length at most d n

r

e.

In a graph G, for u, v ∈ V (G), κ(u, v ) denotes the maximum number of internally disjoint paths between u and v. If G is a digraph, κ counts the maximum number of internally disjoint directed paths from u to v.In a graph G, for u, v ∈ V (G), λ(u, v ) denotes the maximum number of edge-disjoint paths between u and v. If G is a digraph, λ counts the maximum number of edge-disjoint directed paths from u to v.

Theorem 5. 2. (Thomassen [34]) For all positive integers r, there is a digraph D without digons with δ+

D

≥ r and δ−

D

≥ r such that: i. no vertex v ∈ V (D) is contained in three openly disjoint circuits (that is, three circuits which pairwise share only v)ii. no edge (x, y ) ∈ E(D) has κ(y, x ) ≥ 3.

Theorem 5. 3. (Mader [25]) For every integer k ≥ 0, If G has |V (G)| > k 2(k + 1) and at most

k2(k + 1) vertices of G have out-degree at most k3(k + 1), then there are vertices x 6 = y so that

κ(x, y ) > k.

#5.1 Undirected Graph Theorems

Theorem 5. 4. (Mader [22]) Every graph G with δG ≥ r contains vertices x, y with κ(x, y ) ≥ r

when r ≥ 1.

Theorem 5. 5. (Mader [23]) Every graph G with δG ≥ r contains r + 1 vertices v1,..., v r+1

with λ(vi, v j ) ≥ r for all i 6 = j.

#5.2 Additive Number Theory Results

Given an additive group Γ, and sets A, B ⊆ Γ, let A + B:= {a + b | a ∈ A, b ∈ B}, and A ˆ+B:= {a + b | a ∈ A, b ∈ B, a 6 = b}. Finally, for a positive integer r, let rB:= {b1 + · · · + bh| all

bi ∈ B, not necessarily distinct }.

Theorem 5. 6. (Cauchy [6] and Davenport [10], [11]) Let p be a prime, and A, B ⊆ Z/p Z be nonempty. Then |A + B| ≥ min( p, |A| + |B| − 1).

4Theorem 5. 7. (I. Chowla [8]) Let m be a positive integer, and A, B ⊆ Z/m Z such that 0 ∈ B

and gcd (b, m ) = 1 for all nonzero b ∈ B. Then |A + B| ≥ min( m, |A| + |B| − 1).

Theorem 5. 8. (Dias de Silva and Hamidoune [33]) The Erd¨ os-Heilbronn Conjecture: Let

A ⊆ Z/p Z, with p prime. Then |A ˆ+A| ≥ min(2 |A| − 3, p ).

For a multiplicative group Γ and sets A, B ⊆ Γ, let AB:= {ab | a ∈ A, b ∈ B}.

Lemma 5. 9. (Kemperman [21]) Given a group Γ and finite non-empty subsets A, B ⊆ Γ, if

1 ∈ A, B but (1, 1) is the only pair (a, b ) with a ∈ A, b ∈ B such that ab = 1, then |AB | ≥ |A| + |B| − 1.

We say G is a layered digraph if G is a digraph with V (G) = ∪hi=0 Vi with Vi 6 = ∅, and Vi ∩ Vj = ∅

for all i 6 = j, and ( u, v ) ∈ E(G) implies u ∈ Vi−1, v ∈ Vi for some i ∈ { 1,..., h }.A Pl¨ unnecke graph is a layered digraph G with the following two properties: 1. If u, v, w 1,..., w k are vertices of G with ( u, v ), (v, w 1),..., (v, w k) ∈ E(G), then there are distinct vertices v1,..., v k so that ( u, v i), (vi, w i) ∈ E(G) for i = 1,..., k.2. If v, w, u 1,..., u k are vertices of G with ( v, w ), (u1, v ),..., (uk, v ) ∈ E(G), then there are distinct vertices v1,..., v k so that ( ui, v i), (vi, w ) ∈ E(G) for i = 1,..., k.Let G be a digraph, and X, Y nonempty subsets of V (G). Then

Im(X,Y):= {y ∈ Y | there is a directed path from X to y}. The magnification ratio D(X,Y) is

D(X, Y ):= min

Z⊆X,Z 6=∅

{|Im (Z, Y )|

|Z|

}.

Theorem 5. 1 0. (Pl¨ unnecke [28]) In a Pl¨ unnecke graph, let Di = D(V0, V i). Then

D1 ≥ D 1

2 2

≥ · · · ≥ D 1

h h.

The following are consequences of applying Pl¨ unnecke's Inequalities to a special graph created from subsets A, B of a group:

Theorem 5.11. For sets A, B ⊂ Γ:1. |iB | 1

i

≥ | hB | 1

h

for all 0 ≤ i < h.2. If |B| = k, and |B + B| ≤ ck, then |hB | ≤ chk.3. If |A| = n, and |A + B| < cn then for all k, ∈ Z+, we have that |kB −B | ≤ ck+`n where

kB − `B denotes the set of all elements expressable as (b1 + · · · + bk) − (b′

1

  • · · · + b′

`

) where all bi, b ′

i

are in B.

Theorem 5.12. (generalization of Erd¨ os-Heilbronn (Thm. 5.8)) Let A, B ⊆ Z/p Z, with p prime and |A| 6 = |B|. Let C = A ˆ+B. Then |C| ≥ min( |A| + |B| − 2, p ).

56 Open Problems and Conjectures

#6.1 Rainbow Conjectures

6.1.1 A Colored Generalization of Seymour's Second Neighborhood

Given a digraph G = ( V, E ) with each edge e ∈ E having a set Se of labels in {1, 2,..., k G}, a

rainbow structure H in G (such as a path or cycle) means one in which there is a way to assign each edge e ∈ E(H) a label (e) ∈ Se so that ell (e) 6 = (f ) for all edges e 6 = f in E(H).

Record

Added
Links

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.