Partition theorems for parameter systems and graphs

By means of a new combinational structure—parameter systems—we prove that the class of finite ordered graphs has the partition property with respect to each object.     

Parity theorems for paths and cycles in graphs

We extend an elegant proof technique of A. G. Thomason, and deduce several parity theorems for paths and cycles in graphs. For example, a graph in which each vertex is of even degree has an even number of paths if and only if it is of even order, and a graph in which each vertex is of odd degree has an even number of paths if and only if its order is a multiple of four. Our results have implications for generalized friendship graphs and their conjectured nonexistence.     

Functional limit theorems for random regular graphs

Consider $d$ uniformly random permutation matrices on $n$ labels. Consider the sum of these matrices along with their transposes. The total can be interpreted as the adjacency matrix of a random regular graph of degree $2d$ on $n$ vertices. We consider limit theorems for various combinatorial and analytical properties of this graph (or the matrix) as $n$ grows to infinity, either when $d$ is kept fixed or grows slowly with $n$ . In a suitable weak convergence framework, we prove that the (finite but growing in length) sequences of the number of short cycles and of cyclically non-backtracking walks converge to distributional limits. We estimate the total variation distance from the limit using Stein’s method. As an application of these results we derive limits of linear functionals of the eigenvalues of the adjacency matrix. A key step in this latter derivation is an extension of the Kahn–Szemerédi argument for estimating the second largest eigenvalue for all values of $d$ and $n$ .     

Some theorems on graphs and posets

In this journal, Leclerc proved that the dimension of the partially ordered set consisting of all subtrees of a tree T, ordered by inclusion, is the number of end points of T. Leclerc posed the problem of determining the dimension of the partially ordered set P consisting of all induced connected subgraphs of a connected graph G for which P is a lattice.In this paper, we prove that the poset P consisting of all induced connected subgraphs of a nontrivial connected graph G, partially ordered by inclusion, has dimension n where n is the number of noncut vertices in G whether or not P is a lattice. We also determine the dimension of the distributive lattice of all subgraphs of a graph.     

Density theorems for bipartite graphs and related Ramsey-type results

In this paper, we present several density-type theorems which show how to find a copy of a sparse bipartite graph in a graph of positive density. Our results imply several new bounds for classical problems in graph Ramsey theory and improve and generalize earlier results of various researchers. The proofs combine probabilistic arguments with some combinatorial ideas. In addition, these techniques can be used to study properties of graphs with a forbidden induced subgraph, edge intersection patterns in topological graphs, and to obtain several other Ramsey-type statements. Research supported by an NSF Graduate Research Fellowship and a Princeton Centennial Fellowship. Research supported in part by NSF CAREER award DMS-0812005 and by USA-Israeli BSF grant.     

Turán theorems and convexity invariants for directed graphs

This paper is motivated by the desire to evaluate certain classical convexity invariants (specifically, the Helly and Radon numbers) in the context of transitive closure of arcs in the complete digraph. To do so, it is necessary to establish several new Turán type results for digraphs and characterize the associated extremal digraphs. In the case of the Radon number, we establish the following analogue for transitive closure in digraphs of Radon's classical convexity theorem [J. Radon, Mengen konvexer Körper, die einer gemeinsamen Punkt enthalten, Math. Ann. 83 (1921) 113-115]: in a complete digraph on n?7 vertices with >n²/4 arcs, it is possible to partition the arc set into two subsets whose transitive closures have an arc in common.     

Triangle-free partial graphs and edge covering theorems

In section 1 some lower bounds are given for the maximal number of edges ofa (p ? 1)- colorable partial graph. Among others we show that a graph on n vertices with m edges has a (p?1)-colorable partial graph with at least mT_n.p/(ⁿ₂) edges, where T_n.p denotes the so called Turán number. These results are used to obtain upper bounds for special edge covering numbers of graphs. In Section 2 we prove the following theorem: If G is a simple graph and μ is the maximal cardinality of a triangle-free edge set of G, then the edges of G can be covered by μ triangles and edges. In Section 3 related questions are examined.     

Flows and generalized coloring theorems in graphs

An (oriented) graph H is said to be F_k(k ≥ 2) iff there exists an integer flow in H with all edge-values in $\text{[1 ? k, ?1] ? [1, k ? 1]}$. It is known that a plane 2-edge-connected graph is face-colorable with k colors (k ≥ 2) iff it is F_k; W. T. Tutte has proposed [1] to seek for extensions to general graphs of coloring results known for planar graphs through the use of the F_k property. In this direction, we prove among other results that every 2-edge-connected graph is F₈.     

Duality theorems for regular homotopy of finite directed graphs

Dati uno spazio topologico normale e numerabilmente paracompattoS ed un grafo finito ed orientatoG si prova che tra gli insiemiQ(S, G) eQ ^*(S, G) delle classi dio-omotopia e dio ^*-omotopia esiste una biiezione naturale. Nelle stesse condizioni, seS′ è un sottospazio chiuso diS eG′ un sottografo diG, esiste ancora una biiezione naturale tra gli insiemiQ (S, S′; G, G′) eQ ^* (S, S′; G, G′) delle classi di omotopia. Si mostra infine che in condizioni meno restrittive per lo spazioS le precedenti biiezioni possono non sussistere.     

Some characterization theorems for circuit spaces associated with graphs

A circuit space is an independence space (or matroid) in which each basis is contained in a circuit. In this paper we consider various independence spaces associated with a graph and seek to discover for which graphs these spaces are circuit spaces and, in particular, truncated spaces. Some definitive results are obtained and some interesting questions are left open.     

Representation theorems for graphs whose the vertex set is partially ordered

Given a graph G = (X, E), we try to know when it is possible to consider G as the intersection graph of a finite hypergraph, when some restrictions are given on the inclusion order induced on the edge set of this hypergraph.We give some examples concerning the interval graphs and the circular graphs.     

Minimax theorems for infinite graphs with the ends as ideal points

For a set of pairwise disjoint sets of ends of an infinite graph, we define the concepts of -paths and of -separators, and we determine the maximum number of pairwise disjoint -path.     

Separator theorems and Turán-type results for planar intersection graphs

We establish several geometric extensions of the Lipton-Tarjan separator theorem for planar graphs. For instance, we show that any collection C of Jordan curves in the plane with a total of m crossings has a partition into three parts C=S∪C₁∪C₂ such that , , and no element of C₁ has a point in common with any element of C₂. These results are used to obtain various properties of intersection patterns of geometric objects in the plane. In particular, we prove that if a graph G can be obtained as the intersection graph of n convex sets in the plane and it contains no complete bipartite graph Kt,t as a subgraph, then the number of edges of G cannot exceed ctn, for a suitable constant ct.