A note on triangle‐free quasi‐symmetric designs

Triangle‐free quasi‐symmetric 2‐ (v, k, λ) designs with intersection numbers x, y; 0<x<y<kand λ>1, are investigated. It is proved that λ?2y ? x ? 3. As a consequence it is seen that for fixed λ, there are finitely many triangle‐free quasi‐symmetric designs. It is also proved that: k?y(y ? x) + x. Copyright © 2011 Wiley Periodicals, Inc. J Combin Designs 19:422‐426, 2011     

Quasi‐symmetric designs with fixed difference of block intersection numbers

The following results for proper quasi‐symmetric designs with non‐zero intersection numbers x,y and λ > 1 are proved.

• (1) Let D be a quasi‐symmetric design with z = y ? x and v ≥ 2k. If x ≥ 1 + z + z³ then λ < x + 1 + z + z³.
• (2) Let D be a quasi‐symmetric design with intersection numbers x, y and y ? x = 1. Then D is a design with parameters v = (1 + m) (2 + m)/2, b = (2 + m) (3 + m)/2, r = m + 3, k = m + 1, λ = 2, x = 1, y = 2 and m = 2,3,… or complement of one of these design or D is a design with parameters v = 5, b = 10, r = 6, k = 3, λ = 3, and x = 1, y = 2.
• (3) Let D be a triangle free quasi‐symmetric design with z = y ? x and v ≥ 2k, then x ≤ z + z².
• (4) For fixed z ≥ 1 there exist finitely many triangle free quasi‐symmetric designs non‐zero intersection numbers x, y = x + z.
• (5) There do not exist triangle free quasi‐symmetric designs with non‐zero intersection numbers x, y = x + 2.

© 2006 Wiley Periodicals, Inc. J Combin Designs 15: 49–60, 2007     

Self‐Dual Codes and the Nonexistence of a Quasi‐Symmetric 2‐(37,9,8) Design with Intersection Numbers 1 and 3

We prove that a certain binary linear code associated with the incidence matrix of a quasi‐symmetric 2‐(37, 9, 8) design with intersection numbers 1 and 3 must be contained in an extremal doubly even self‐dual code of length 40. Using the classification of extremal doubly even self‐dual codes of length 40, we show that a quasi‐symmetric 2‐(37, 9, 8) design with intersection numbers 1 and 3 does not exist.     

Homomorphisms of 2‐Edge‐Colored Triangle‐Free Planar Graphs

In this article, we introduce and study the properties of some target graphs for 2‐edge‐colored homomorphism. Using these properties, we obtain in particular that the 2‐edge‐colored chromatic number of the class of triangle‐free planar graphs is at most 50. We also show that it is at least 12.     

Quasi‐random graphs with given degree sequences

It is now known that many properties of the objects in certain combinatorial structures are equivalent, in the sense that any object possessing any of the properties must of necessity possess them all. These properties, termed quasirandom, have been described for a variety of structures such as graphs, hypergraphs, tournaments, Boolean functions, and subsets of Z _n, and most recently, sparse graphs. In this article, we extend these ideas to the more complex case of graphs which have a given degree sequence. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

A Recursive Construction for New Symmetric Designs

We introduce a recursive construction of regular Handamard matrices with row sum 2h for h=±3ⁿ. Whenever q=(2h – 1)² is a prime power, we construct, for every positive integer m, a symmetric designs with parameters (4h²(q^m+1 – 1)/(q – 1), (2h² – h)q^m, (h² – h)q^m).     

The Existence of a Bush-Type Hadamard Matrix of Order 324 and Two New Infinite Classes of Symmetric Designs

A symmetric 2-(324, 153, 72) design is constructed that admits a tactical decomposition into 18 point and block classes of size 18 such that every point is in either 0 or 9 blocks from a given block class, and every block contains either 0 or 9 points from a given point class. This design is self-dual and yields a symmetric Hadamard matrix of order 324 of Bush type, being the first known example of a symmetric Bush-type Hadamard matrix of order 4n ² for n > 1 odd. Equivalently, the design yields a strongly regular graph with parameters v=324, k=153, ==72 that admits a spread of cocliques of size 18. The Bush-type Hadamard matrix of order 324 leads to two new infinite classes of symmetric designs with parameters

There are exactly five biplanes with k = 11

A biplane is a 2‐(k(k ? 1)/2 + 1,k,2) symmetric design. Only sixteen nontrivial biplanes are known: there are exactly nine biplanes with k < 11, at least five biplanes with k = 11, and at least two biplanes with k = 13. It is here shown by exhaustive computer search that the list of five known biplanes with k = 11 is complete. This result further implies that there exists no 3‐(57, 12, 2) design, no 112₁₁ symmetric configuration, and no (324, 57, 0, 12) strongly regular graph. The five biplanes have 16 residual designs, which by the Hall–Connor theorem constitute a complete classification of the 2‐(45, 9, 2) designs. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 117–127, 2008     

Non Existence of Triangle Free Quasi-symmetric Designs

The following two results are proved. Let D be a triangle free quasi-symmetric design with k=2y−x and x≥ 1 then D is a trivial design with v=5 and k=3. There do no exist triangle free quasi-symmetric designs with x≥ 1 and λ=y or λ=y−1.Communicated by: P. Wild     

New families of non‐embeddable quasi‐derived designs

The main result in this article is a method of constructing a non‐embeddable quasi‐derived design from a quasi‐derived design and an α‐resolvable design. This method is a generalization of techniques used by van Lint and Tonchev in 14 , 15 and Kageyama and Miao in 8 . As applications, we construct several new families of non‐embeddable quasi‐derived designs. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 263–275, 2008     

Quasi‐Random Oriented Graphs

We show that a number of conditions on oriented graphs, all of which are satisfied with high probability by randomly oriented graphs, are equivalent. These equivalences are similar to those given by Chung, Graham, and Wilson [5] in the case of unoriented graphs, and by Chung and Graham [3] in the case of tournaments. Indeed, our main theorem extends to the case of a general underlying graph G, the main result of [3] which corresponds to the case that G is complete. One interesting aspect of these results is that exactly two of the four orientations of a four cycle can be used for a quasi‐randomness condition, i.e., if the number of appearances they make in D is close to the expected number in a random orientation of the same underlying graph, then the same is true for every small oriented graph H.     

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     

Symmetric ‐Designs and ‐Difference Sets

In this paper, we introduce a method to construct ‐designs, which are also known as partial geometric designs, by using subsets of certain finite groups. We introduce the concept of ‐difference sets and investigate the existence and nonexistence of these structures. We also provide some nonexistence results on ‐designs based on the fact that ‐designs yield directed strongly regular graphs.     

Symmetric and Skew‐Symmetric ‐Matrices with Large Determinants

We show that the existence of ‐matrices having largest possible determinant is equivalent to the existence of certain tournament matrices. In particular, we prove a recent conjecture of Armario. We also show that large submatrices of conference matrices are determined by their spectrum.     

Flag‐Transitive 2‐ Symmetric Designs with Sporadic Socle

Let be a nontrivial 2‐ symmetric design admitting a flag‐transitive, point‐primitive automorphism group G of almost simple type with sporadic socle. We prove that there are up to isomorphism six designs, and must be one of the following: a 2‐(144, 66, 30) design with or , a 2‐(176, 50, 14) design with , a 2‐(176, 126, 90) design with or , or a 2‐(14,080, 12,636, 11,340) design with .     

3‐Coloring Triangle‐Free Planar Graphs with a Precolored 8‐Cycle

Let G be a planar triangle‐free graph and let C be a cycle in G of length at most 8. We characterize all situations where a 3‐coloring of C does not extend to a proper 3‐coloring of the whole graph.     

Infinite families of non‐embeddable quasi‐residual Menon designs

A Menon design of order h² is a symmetric (4h²,2h²‐h,h²‐h)‐design. Quasi‐residual and quasi‐derived designs of a Menon design have parameters 2‐(2h² + h,h²,h²‐h) and 2‐(2h²‐h,h²‐h,h²‐h‐1), respectively. In this article, regular Hadamard matrices are used to construct non‐embeddable quasi‐residual and quasi‐derived Menon designs. As applications, we construct the first two new infinite families of non‐embeddable quasi‐residual and quasi‐derived Menon designs. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 53–62, 2009     

Quasi‐carousel tournaments

A tournament is called locally transitive if the outneighborhood and the inneighborhood of every vertex are transitive. Equivalently, a tournament is locally transitive if it avoids the tournaments W₄ and L₄, which are the only tournaments up to isomorphism on four vertices containing a unique 3‐cycle. On the other hand, a sequence of tournaments  with  is called almost balanced if all but  vertices of  have outdegree . In the same spirit of quasi‐random properties, we present several characterizations of tournament sequences that are both almost balanced and asymptotically locally transitive in the sense that the density of W₄ and L₄ in  goes to zero as n goes to infinity.     

New families of strongly regular graphs

We apply symmetric balanced generalized weighing matrices with zero diagonal to construct four parametrically new infinite families of strongly regular graphs. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 208–217, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10038