On the falsity of a conjecture on orthogonal steiner triple systems

A pair of orthogonal Steiner triple systems of order ν = 27 is constructed, thus showing the conjecture about the non-existence of a pair of orthogonal Steiner triple systems of orders ν ≡ 3 (mod 6) to be false.     

Two proofs of the Bermond-Thomassen conjecture for tournaments with bounded minimum in-degree

The Bermond-Thomassen conjecture states that, for any positive integer r, a digraph of minimum out-degree at least 2r−1 contains at least r vertex-disjoint directed cycles. Thomassen proved that it is true when r=2, and very recently the conjecture was proved for the case where r=3. It is still open for larger values of r, even when restricted to (regular) tournaments. In this paper, we present two proofs of this conjecture for tournaments with minimum in-degree at least 2r−1. In particular, this shows that the conjecture is true for (almost) regular tournaments. In the first proof, we prove auxiliary results about union of sets contained in another union of sets, that might be of independent interest. The second one uses a more graph-theoretical approach, by studying the properties of a maximum set of vertex-disjoint directed triangles.     

The reconstruction conjecture and edge ideals

Given a simple graph G on n vertices, we prove that it is possible to reconstruct several algebraic properties of the edge ideal from the deck of G, that is, from the collection of subgraphs obtained by removing a vertex from G. These properties include the Krull dimension, the Hilbert function, and all the graded Betti numbers β_i,j where j<n. We also state many further questions that arise from our study.     

Reductions of the graph reconstruction conjecture

In this note we shall show that the Graph Reconstruction Conjecture (also called the Kelly-Ulam conjecture [1, p. 11]) is equivalent to a conjecture about the algebraic properties of certain directed trees and their homomorphic images. We shall show the the Greph Reconstruction Conjecture is equivalent to recognizing the (abstract) group of a graph from the tree (generalized “deck”) of the graph.     

Counterexamples to the edge reconstruction conjecture for infinite graphs

For every infinite cardinal α, there exists a graph with α edges which is not uniquely reconstructible from its family of edge-deleted subgraphs.     

Hamilton decompositions of regular expanders: A proof of Kelly’s conjecture for large tournaments

A long-standing conjecture of Kelly states that every regular tournament on n$n$ vertices can be decomposed into (n−1)/2$(n-1)/2$ edge-disjoint Hamilton cycles. We prove this conjecture for large n$n$. In fact, we prove a far more general result, based on our recent concept of robust expansion and a new method for decomposing graphs. We show that every sufficiently large regular digraph G$G$ on n$n$ vertices whose degree is linear in n$n$ and which is a robust outexpander has a decomposition into edge-disjoint Hamilton cycles. This enables us to obtain numerous further results, e.g. as a special case we confirm a conjecture of Erd?s on packing Hamilton cycles in random tournaments. As corollaries to the main result, we also obtain several results on packing Hamilton cycles in undirected graphs, giving e.g. the best known result on a conjecture of Nash-Williams. We also apply our result to solve a problem on the domination ratio of the Asymmetric Travelling Salesman problem, which was raised e.g. by Glover and Punnen as well as Alon, Gutin and Krivelevich.     

Operator decomposition of graphs and the reconstruction conjecture

We present the method of proving the reconstructibility of graph classes based on the new type of decomposition of graphs — the operator decomposition. The properties of this decomposition are described. Using this decomposition we prove the following. Let P and Q be two hereditary graph classes such that P is closed with respect to the operation of join and Q is closed with respect to the operation of disjoint union. Let M be a module of graph G with associated partition (A,B,M), where A∼M and B⁄∼M, such that G[A]∈P, G[B]∈Q and G[M] is not (P,Q)-split. Then the graph G is reconstructible.     

Disproof of a conjecture in graph reconstruction theory

In his thesis [3] B. D. Thatte conjectured that ifG=G ₁,G ₂,...G _n is a sequence of finitely many simple connected graphs (isomorphic graphs may occur in the sequence) with the same number of vertices and edges then their shuffled edge deck uniquely determines the graph sequence (up to a permutation). In this paper we prove that there are such sequences of graphs with the same shuffled edge deck.This research was partially supported by Hungarian National Foundation of Scientific Research Grant no. 1812     

A well-quasi-order for tournaments

A digraph H is immersed in a digraph G if the vertices of H are mapped to (distinct) vertices of G, and the edges of H are mapped to directed paths joining the corresponding pairs of vertices of G, in such a way that the paths are pairwise edge-disjoint. For graphs the same relation (using paths instead of directed paths) is a well-quasi-order; that is, in every infinite set of graphs some one of them is immersed in some other. The same is not true for digraphs in general; but we show it is true for tournaments (a tournament is a directed complete graph).     

Score certificates for tournaments

The score of a vertex in a tournament is its out-degree. A score certificate for a labeled tournament T is a labeled subdigraph D of T which together with the score sequence of T allows errorless reconstruction of T. In this paper we prove a general lower bound on the sizes of score certificates. Our main theorem can be stated as follows: Except for the regular tournaments on 3 and 5 vertices, every tournament T on n vertices requires at least n−1 arcs in a score certificate for T. This is best possible since every transitive tournament on n vertices has a score certificate with exactly n−1 arcs. © 1997 John Wiley & Sons, Inc.     

On a conjecture of He concerning the spectral reconstruction of matrices

This paper is concerned with a recent conjecture of He (Electron. J. Comb. 14(1), 2007) on the spectral reconstruction of matrices. A counterexample is provided by using Hadamard matrices. We also give some results to the above mentioned conjecture (with slight modifications) in the positive direction.     

The selection efficiency of tournaments

We discuss tournaments in terms of their efficiency as probabilistic mechanisms that select high-quality alternatives (“players”) in a noisy environment. We characterize the selection efficiency of three such mechanisms – contests, binary elimination tournaments, and round-robin tournaments – depending on the shape of the distribution of players’ quality, the number of players, and noise level. The results have implications as to how, and under what circumstances, the efficiency of tournament-based selection can be manipulated.     

The reconstruction conjecture is true if all 2-connected graphs are reconstructible

It is shown that the Reconstruction Conjecture is true for all finite graphs if it is true for the 2-connected ones.     

The Conley conjecture for the cotangent bundle

We prove the Conley conjecture for cotangent bundles of oriented, closed manifolds, and Hamiltonians which are quadratic at infinity, i.e., we show that such Hamiltonians have infinitely many periodic orbits. For the conservative systems, similar results have been proven by Lu and Mazzucchelli using convex Hamiltonians and Lagrangian methods. Our proof uses Floer homological methods from Ginzburg’s proof of the Conley conjecture for closed symplectically aspherical manifolds.     

The Lalonde-McDuff conjecture for nilmanifolds

We prove that any Hamiltonian bundle whose fiber is a nilmanifold c-splits.