Remarks on the second neighborhood problem

The second neighborhood conjecture of Seymour asserts that for any orientation G = (V,E), there exists a vertex υ ∈ V so that |N⁺(υ)| ≤ |N⁺⁺(υ)|. The conjecture was resolved by Fisher for tournaments. In this article, we prove the second neighborhood conjecture for several additional classes of dense orientations. We also prove some approximation results, and reduce an asymptotic version of the conjecture to a finite case. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 208–220, 2007     

On a Hypergraph Matching Problem

Let H = (V, E) be an r-uniform hypergraph and let A matching M of H is (α, )-perfect if for each F ∈ , at least α|F| vertices of F are covered by M. Our main result is a theorem giving sufficient conditions for an r-uniform hypergraph to have a -perfect matching. As a special case of our theorem we obtain the following result. Let K(n, r) denote the complete r-uniform hypergraph with n vertices. Let t and r be fixed positive integers where t≥r≥2. Then, K(n, r) can be packed with edge-disjoint copies of K(t, r) such that each vertex is incident with only o(n ^{r ?1}) unpacked edges. This extends a result of Rödl [9].     

Packing 4-Cycles in Eulerian and Bipartite Eulerian Tournaments with an Application to Distances in Interchange Graphs

We prove that every Eulerian orientation of K_m,n contains arc-disjoint directed 4-cycles, improving earlier lower bounds. Combined with a probabilistic argument, this result is used to prove that every regular tournament with n vertices contains arc-disjoint directed 4-cycles. The result is also used to provide an upper bound for the distance between two antipodal vertices in interchange graphs.Received February 6, 2004     

Packing Triangles in Regular Tournaments

We prove that a regular tournament with n vertices has more than pairwise arc‐disjoint directed triangles. On the other hand, we construct regular tournaments with a feedback arc set of size less than , so these tournaments do not have pairwise arc‐disjoint triangles.     

The hyperdeterminant and triangulations of the 4-cube

The hyperdeterminant of format is a polynomial of degree in unknowns which has terms. We compute the Newton polytope of this polynomial and the secondary polytope of the -cube. The regular triangulations of the -cube are classified into -equivalence classes, one for each vertex of the Newton polytope. The -cube has coarsest regular subdivisions, one for each facet of the secondary polytope, but only of them come from the hyperdeterminant.

     

Fractional decompositions of dense hypergraphs

A seminal result of Rödl (the Rödl nibble) assertsthat the edges of the complete r-uniform hypergraph can be packed, almost completely, with copiesof , where k is fixed.We prove that the same result holds in a dense hypergraph setting.It is shown that for every r-uniform hypergraph H₀, there existsa constant = (H₀) < 1 such that every r-uniform hypergraphH in which every (r – 1)-set is contained in at least n edges has an H₀-packing that covers |E(H)|(1 – o_n(1))edges. Our method of proof uses fractional decompositions andmakes extensive use of probabilistic arguments and additionalcombinatorial ideas.     

Resonant Capture and Separatrix Crossing in Dual-Spin Spacecraft

We consider the rotational motion of a spacecraft composed of two bodies which are free to rotate relative to one another about a common shaft S. A motor on one of the bodies provides a small constant internal torque which influences the relative motion of the two bodies, and which may influence the orientation of their common shaft S. Resonant capture refers to the phenomenon that the spacecraft may end up in one of several possible orientations, including a nearly flat spin (transverse to S), in addition to the expected simple rotation about S.The method of averaging is used to treat the original equations of motion, and it is shown that the essential mathematical problem involves separatrix crossing in a problem with slowly moving separatrices. Energy changes represented by Melnikov integrals are used to supplement the averaged equations in the neighborhood of the heteroclinic motions. The method is used to predict which initial conditions lead to capture into each of three distinct capture regions. The asymptotic results are compared to those obtained by direct numerical integration of the equations of motion.     

Large Monotone Paths in Graphs with Bounded Degree

 We prove that for every ε>0 and positive integer r, there exists Δ₀=Δ₀(ε) such that if Δ>Δ₀ and n>n(Δ,ε,r) then there exists a packing of K _n with ⌊(n−1)/Δ⌋ graphs, each having maximum degree at most Δ and girth at least r, where at most εn ² edges are unpacked. This result is used to prove the following: Let f be an assignment of real numbers to the edges of a graph G. Let α(G,f) denote the maximum length of a monotone simple path of G with respect to f. Let α(G) be the minimum of α(G,f), ranging over all possible assignments. Now let α_Δ be the maximum of α(G) ranging over all graphs with maximum degree at most Δ. We prove that Δ+1≥α_Δ≥Δ(1−o(1)). This extends some results of Graham and Kleitman [6] and of Calderbank et al. [4] who considered α(K _n ). Received: March 15, 1999?Final version received: October 22, 1999