A note on minimum graphs with girth pair (4, 2l + 1)

We show that the size of a smallest connected k-regular graph with girth pair (4, 2l + 1) is within a constant of (2l + 1) k/2. In so doing we disprove a conjecture of Harary and Kovacs.     

Cayley Cages

A (k,g)-Cayley cage is a k-regular Cayley graph of girth g and smallest possible order. We present an explicit construction of (k,g)-Cayley graphs for all parameters k≥2 and g≥3 and generalize this construction to show that many well-known small k-regular graphs of girth g can be constructed in this way. We also establish connections between this construction and topological graph theory, and address the question of the order of (k,g)-Cayley cages.     

An Algorithm to Construct <Emphasis Type="BoldItalic">k</Emphasis>-Regular <Emphasis Type="BoldItalic">k</Emphasis>-Connected Graphs with the Maximum <Emphasis Type="BoldItalic">k</Emphasis>-Diameter

 Let f(2m,k) be the Maximum k-diameter of k-regular k-connected graphs on 2m vertices. In this paper we give an algorithm and prove that we can construct k-regular k-connected graphs on 2m vertices with the maximum k-diameter using it. We also prove some known results about f(2m,k) and verify that we can get some unknown values of f(2m,k) by our algorithm. Received: December 1, 2000 Final version received: March 12, 2002 Acknowledgments. We thank the referee for many useful suggestions.     

On the chromatic number of set systems

An (r, l)‐system is an r‐uniform hypergraph in which every set of l vertices lies in at most one edge. Let m_k(r, l) be the minimum number of edges in an (r, l)‐system that is not k‐colorable. Using probabilistic techniques, we prove that where b_{r, l} is explicitly defined and a_{r, l} is sufficiently small. We also give a different argument proving (for even k) where a′_{r, l}=(r?l+1)/r(2^r?1re)^?l/(l?1). Our results complement earlier results of Erd?s and Lovász [10] who mainly focused on the case l=2, k fixed, and r large. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 87–98, 2001     

What is a Quotient Map with Respect to a Closure Operator?

It is shown that there is no good answer to the question of the title, even if we restrict our attention to S et-based topological categories. Although very closely related, neither the natural notion of c-finality (designed in total analogy to c-initiality) nor the notion of c-quotient (modelled after the behaviour of topological quotient maps) provide universally satisfactory concepts. More dramatically, in the category T op with its natural Kuratowski closure operator k, the class of k-final maps cannot be described as the class of c-quotient maps for any closure operator c, and the class of k-quotients cannot be described as the class of c-final maps for any c. We also discuss the behaviour of c-final maps under crossing with an identity map, as in Whitehead's Theorem. In T op, this gives a new stability theorem for hereditary quotient maps.     

On a Formula Relating Volumes of Medial Sections of Simplices

Talata’s medial sections of simplices can be classified into families according to how many vertices of the simplex lie on one side of the hyperplane determining the section. Defining a (k,l)-medial section to be one in which k vertices lie on one side and l=d+1−k on the other, we show that for any d-simplex the ratio of the sum of the squared volumes of the (k,l)-medial sections to the sum of the squared volumes of the (κ,λ)-medial sections is independent of the geometry of the simplex, depending only on d, k, and κ. We give a formula for the ratio.     

Minimum monopoly in regular and tree graphs

In this paper we consider a graph optimization problem called minimum monopoly problem, in which it is required to find a minimum cardinality set S⊆V, such that, for each u∈V, |N[u]∩S|?|N[u]|/2 in a given graph G=(V,E). We show that this optimization problem does not have a polynomial-time approximation scheme for k-regular graphs (k?5), unless P=NP. We show this by establishing two L-reductions (an approximation preserving reduction) from minimum dominating set problem for k-regular graphs to minimum monopoly problem for 2k-regular graphs and to minimum monopoly problem for (2k-1)-regular graphs, where k?3. We also show that, for tree graphs, a minimum monopoly set can be computed in linear time.     

Quasi‐random hypergraphs revisited

The quasi‐random theory for graphs mainly focuses on a large equivalent class of graph properties each of which can be used as a certificate for randomness. For k ‐graphs (i.e., k ‐uniform hypergraphs), an analogous quasi‐random class contains various equivalent graph properties including the k ‐discrepancy property (bounding the number of edges in the generalized induced subgraph determined by any given (k ‐ 1) ‐graph on the same vertex set) as well as the k ‐deviation property (bounding the occurrences of “octahedron”, a generalization of 4 ‐cycle). In a 1990 paper (Chung, Random Struct Algorithms 1 (1990) 363‐382), a weaker notion of l ‐discrepancy properties for k ‐graphs was introduced for forming a nested chain of quasi‐random classes, but the proof for showing the equivalence of l ‐discrepancy and l ‐deviation, for 2 ≤ l < k, contains an error. An additional parameter is needed in the definition of discrepancy, because of the rich and complex structure in hypergraphs. In this note, we introduce the notion of (l,s) ‐discrepancy for k ‐graphs and prove that the equivalence of the (k,s) ‐discrepancy and the s ‐deviation for 1 ≤ s ≤ k. We remark that this refined notion of discrepancy seems to point to a lattice structure in relating various quasi‐random classes for hypergraphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Isometric embeddings of Johnson graphs in Grassmann graphs

Let V be an n-dimensional vector space (4≤n<∞) and let G_k(V){\mathcal{G}}_{k}(V) be the Grassmannian formed by all k-dimensional subspaces of V. The corresponding Grassmann graph will be denoted by Γ _k (V). We describe all isometric embeddings of Johnson graphs J(l,m), 1<m<l−1 in Γ _k (V), 1<k<n−1 (Theorem 4). As a consequence, we get the following: the image of every isometric embedding of J(n,k) in Γ _k (V) is an apartment of G_k(V){\mathcal{G}}_{k}(V) if and only if n=2k. Our second result (Theorem 5) is a classification of rigid isometric embeddings of Johnson graphs in Γ _k (V), 1<k<n−1.     

John's decompositions: Selecting a large part

We extend the invertibility principle of J. Bourgain and L. Tzafriri to operators acting on arbitrary decompositionsid = ∑x _j ⊕x _j , rather than on the coordinate one. The John's decomposition brings this result to the local theory of Banach spaces. As a consequence, we get a new lemma of Dvoretzky-Rogers type, where the contact points of the unit ball with its maximal volume ellipsoid play a crucial role. We then apply these results to embeddings ofl _∞ ^k into finite dimensional spaces.     

Embedding into l ∞2 Is Easy, Embedding into l ∞3 Is?NP-Complete

We give a new algorithm for enumerating all possible embeddings of a metric space (i.e., the distances between every pair within a set of n points) into ℝ² Cartesian space preserving their l _∞ (or l ₁) metric distances. Its expected time is (i.e., within a poly-log of the size of the input) beating the previous algorithm. In contrast, we prove that detecting l _∞³ embeddings is NP-complete. The problem is also NP-complete within l ₁² or l _∞² with the added constraint that the locations of two of the points are given or alternatively that the two dimensions are curved into a three-dimensional sphere. We also refute a compaction theorem by giving a metric space that cannot be embedded in l _∞³; however, it can be embedded if any single point is removed. This research is partially supported by NSERC grants. I would like to thank Steven Watson for his extensive help on this paper.     

Results on <Emphasis Type="Italic">F</Emphasis>-continuous graphs

For any nontrivial connected graph F and any graph G, the F-degree of a vertex v in G is the number of copies of F in G containing v. G is called F-continuous if and only if the F-degrees of any two adjacent vertices in G differ by at most 1; G is F-regular if the F-degrees of all vertices in G are the same. This paper classifies all P ₄-continuous graphs with girth greater than 3. We show that for any nontrivial connected graph F other than the star K _1,k , k ⩾ 1, there exists a regular graph that is not F-continuous. If F is 2-connected, then there exists a regular F-continuous graph that is not F-regular.      

Embeddings ofl p m intol ∞ n , 1≦p≦2

Isomorphic embeddings ofl _l ^m intol _∞ ⁿ are studied, and ford(n, k)=inf{‖T ‖ ‖T ⁻¹ ‖;T varies over all isomorphic embeddings ofl ₁ ^[klog2n] intol _∞ ⁿ we have that lim _n→∞ d(n, k)=γ(k)⁻¹,k>1, whereγ(k) is the solution of (1+γ)ln(1+γ)+(1 −γ)ln(1 −γ)=k ⁻¹ln4. Here [x] denotes the integer part of the real numberx.     

On the edge-coloring problem for a class of 4-regular maps

A (plane) 4-regular map G is called C-simple if it arises as a superposition of simple closed curves (tangencies are not allowed); in this case σ (G) is the smallest integer k such that the curves of G can be colored with k colors in such a way that no two curves of the same color intersect. We prove that if σ (G) ≤ 4, G is edge colorable with 4 colors. Moreover we show that a similar result for maps G with σ(G) ≤ 5 would imply the Four-Color Theorem.     

Geometric realization of Adams maps

Let G/P be a homogenous space with G a compact connected Lie group and P a connected subgroup of G of equal rank. As the rational cohomology ring of G/P is concentrated in even dimensions, for an integer k we can define the Adams map of type k to be l _k : H*(G/P, ℚ) → H*(G/P, ℚ), l _k (u) = k ⁱ u, u ∈ H ²ⁱ (G/P, ℚ). We show that if k is prime to the order of the Weyl group of G, then l _k can be induced by a self map of G/P. We also obtain results which imply the condition that k is prime to the order of the Weyl group of G is necessary.     

Counting connected graphs asymptotically

We find the asymptotic number of connected graphs with k vertices and k−1+l edges when k,l approach infinity, re-proving a result of Bender, Canfield and McKay. We use the probabilistic method, analyzing breadth-first search on the random graph G(k,p) for an appropriate edge probability p. Central is the analysis of a random walk with fixed beginning and end which is tilted to the left.     

Equations resolving a conjecture of Rado on partition regularity

A linear equation L is called k-regular if every k-coloring of the positive integers contains a monochromatic solution to L. Richard Rado conjectured that for every positive integer k, there exists a linear equation that is (k−1)-regular but not k-regular. We prove this conjecture by showing that the equation has this property.This conjecture is part of problem E14 in Richard K. Guy's book “Unsolved Problems in Number Theory”, where it is attributed to Rado's 1933 thesis, “Studien zur Kombinatorik”.     

New regular embeddings of n‐cubes Qn

We investigate highly symmetrical embeddings of the n‐dimensional cube Q_n into orientable compact surfaces which we call regular embeddings of Q_n. We derive some general results and construct some new families of regular embeddings of Q_n. In particular, for n = 1, 2,3(mod 4), we classify the regular embeddings of Q_n which can be expressed as balanced Cayley maps. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 297–312, 2004     

Regular factors of regular graphs

Given r ? 3 and 1 ? λ ? r, we determine all values of k for which every r-regular graph with edge-connectivity λ has a k-factor.     

Spherical Designs and Generalized Sum-Free Sets in Abelian Groups

We extend the concepts of sum-freesets and Sidon-sets of combinatorial number theory with the aimto provide explicit constructions for spherical designs. We calla subset S of the (additive) abelian group G t-free if for all non-negative integers kand l with k+l t, the sum of k(not necessarily distinct) elements of S does notequal the sum of l (not necessarily distinct) elementsof S unless k=l and the two sums containthe same terms. Here we shall give asymptotic bounds for thesize of a largest t-free set in Z _n,and for t 3 discuss how t-freesets in Z _n can be used to constructspherical t-designs.