On E(s2)‐optimal and minimax‐optimal supersaturated designs with 20 rows and 76 columns

We derive a previously unknown lower bound of 41 for the frequency of of an E(s²)‐optimal and minimax‐optimal supersaturated design (SSD) with 20 rows and 76 columns. This is accomplished by an exhaustive computer search that uses the combinatorial properties of resolvable 2 − (20, 10, 36) designs and the parallel class intersection pattern method. We also classify all nonisomorphic E(s²)‐optimal 4‐circulant SSDs with 20 rows and .     

Minimal Obstructions for 1‐Immersions and Hardness of 1‐Planarity Testing

A graph is 1‐planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge (and any pair of crossing edges cross only once). A non‐1‐planar graph G is minimal if the graph is 1‐planar for every edge e of G. We construct two infinite families of minimal non‐1‐planar graphs and show that for every integer , there are at least nonisomorphic minimal non‐1‐planar graphs of order n. It is also proved that testing 1‐planarity is NP‐complete.     

Existence of multiple positive solutions for −Δu−μ(u/∣x∣2)=u2*−1+σf(x)

In this paper, we consider the semilinear elliptic problem where Ω??^N (N?3) is a bounded smooth domain such that 0∈Ω, σ>0 is a real parameter, and f(x) is some given function in L^∞(Ω) such that f(x)?0, f(x)?0 in Ω. Some existence results of multiple solutions have been obtained by implicit function theorem, monotone iteration method and Mountain Pass Lemma. Copyright © 2002 John Wiley & Sons, Ltd.     

Packing of graphic n‐tuples

An n‐tuple π (not necessarily monotone) is graphic if there is a simple graph G with vertex set {v₁, …, v_n} in which the degree of v_i is the ith entry of π. Graphic n‐tuples (d, …, d) and (d, …, d) pack if there are edge‐disjoint n‐vertex graphs G₁ and G₂ such that d(v_i) = d and d(v_i) = d for all i. We prove that graphic n‐tuples π₁ and π₂ pack if , where Δand δdenote the largest and smallest entries in π₁ + π₂ (strict inequality when δ = 1); also, the bound is sharp. Kundu and Lovász independently proved that a graphic n‐tuple π is realized by a graph with a k‐factor if the n‐tuple obtained by subtracting k from each entry of π is graphic; for even n we conjecture that in fact some realization has k edge‐disjoint 1‐factors. We prove the conjecture in the case where the largest entry of π is at most n/2 + 1 and also when k?3. © 2011 Wiley Periodicals, Inc. J Graph Theory     

The spectrum of 2‐idempotent 3‐quasigroups with conjugate invariant subgroups

A ternary quasigroup (or 3‐quasigroup) is a pair (N, q) where N is an n‐set and q(x, y, z) is a ternary operation on N with unique solvability. A 3‐quasigroup is called 2‐idempotent if it satisfies the generalized idempotent law: q(x, x, y) = q(x, y, x) = q(y, x, x)=y. A conjugation of a 3‐quasigroup, considered as an OA(3, 4, n), $({{N}},{\mathcal{B}})$, is a permutation of the coordinate positions applied to the 4‐tuples of ${\mathcal{B}}$. The subgroup of conjugations under which $({{N}},{\mathcal{B}})$ is invariant is called the conjugate invariant subgroup of $({{N}},{\mathcal{B}})$. In this article, we determined the existence of 2‐idempotent 3‐quasigroups of order n, n≡7 or 11 (mod 12) and n≥11, with conjugate invariant subgroup consisting of a single cycle of length three. This result completely determined the spectrum of 2‐idempotent 3‐quasigroups with conjugate invariant subgroups. As a corollary, we proved that an overlarge set of Mendelsohn triple system of order n exists if and only if n≡0, 1 (mod 3) and n≠6. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 292–304, 2010     

On ε‐biased generators in NC0

Cryan and Miltersen (Proceedings of the 26th Mathematical Foundations of Computer Science, 2001, pp. 272–284) recently considered the question of whether there can be a pseudorandom generator in NC⁰, that is, a pseudorandom generator that maps n‐bit strings to m‐bit strings such that every bit of the output depends on a constant number k of bits of the seed. They show that for k = 3, if m ≥ 4n + 1, there is a distinguisher; in fact, they show that in this case it is possible to break the generator with a linear test, that is, there is a subset of bits of the output whose XOR has a noticeable bias. They leave the question open for k ≥ 4. In fact, they ask whether every NC⁰ generator can be broken by a statistical test that simply XORs some bits of the input. Equivalently, is it the case that no NC⁰ generator can sample an ε‐biased space with negligible ε? We give a generator for k = 5 that maps n bits into cn bits, so that every bit of the output depends on 5 bits of the seed, and the XOR of every subset of the bits of the output has bias 2. For large values of k, we construct generators that map n bits to bits such that every XOR of outputs has bias . We also present a polynomial‐time distinguisher for k = 4,m ≥ 24n having constant distinguishing probability. For large values of k we show that a linear distinguisher with a constant distinguishing probability exists once m ≥ Ω(2^kn^?k/2?). Finally, we consider a variant of the problem where each of the output bits is a degree k polynomial in the inputs. We show there exists a degree k = 2 pseudorandom generator for which the XOR of every subset of the outputs has bias 2^?Ω(n) and which maps n bits to Ω(n²) bits. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

On 5‐Cycles and 6‐Cycles in Regular n‐Tournaments

Let T be a tournament of order n and be the number of cycles of length m in T. For and odd n, the maximum of is achieved for any regular tournament of order n (M. G. Kendall and B. Babington Smith, 1940), and in the case it is attained only for the unique regular locally transitive tournament RLT_n of order n (U. Colombo, 1964). A lower bound was also obtained for in the class of regular tournaments of order n (A. Kotzig, 1968). This bound is attained if and only if T is doubly regular (when ) or nearly doubly regular (when ) (B. Alspach and C. Tabib, 1982). In the present article, we show that for any regular tournament T of order n, the equality holds. This allows us to reduce the case to the case In turn, the pure spectral expression for obtained in the class implies that for a regular tournament T of order the inequality holds, with equality if and only if T is doubly regular or T is the unique regular tournament of order 7 that is neither doubly regular nor locally transitive. We also determine the value of c₆(RLT_n) and conjecture that this value coincides with the minimum number of 6‐cycles in the class for each odd      

Large ‐ or ‐Minors in 3‐Connected Graphs

There are numerous results bounding the circumference of certain 3‐connected graphs. There is no good bound on the size of the largest bond (cocircuit) of a 3‐connected graph, however. Oporowski, Oxley, and Thomas (J Combin Theory Ser B 57 (1993), 2, 239–257) proved the following result in 1993. For every positive integer k, there is an integer such that every 3‐connected graph with at least n vertices contains a ‐ or ‐minor. This result implies that the size of the largest bond in a 3‐connected graph grows with the order of the graph. Oporowski et al. obtained a huge function iteratively. In this article, we first improve the above authors' result and provide a significantly smaller and simpler function . We then use the result to obtain a lower bound for the largest bond of a 3‐connected graph by showing that any 3‐connected graph on n vertices has a bond of size at least . In addition, we show the following: Let G be a 3‐connected planar or cubic graph on n vertices. Then for any , G has a ‐minor with , and thus a bond of size at least .     

Vizing's 2‐Factor Conjecture Involving Large Maximum Degree

Let G be an n‐vertex simple graph, and let and denote the maximum degree and chromatic index of G, respectively. Vizing proved that or . Define G to be Δ‐critical if and for every proper subgraph H of G. In 1965, Vizing conjectured that if G is an n‐vertex Δ‐critical graph, then G has a 2‐factor. Luo and Zhao showed if G is an n‐vertex Δ‐critical graph with , then G has a hamiltonian cycle, and so G has a 2‐factor. In this article, we show that if G is an n‐vertex Δ‐critical graph with , then G has a 2‐factor.     

{2, 3}‐perfect m‐cycle systems are equationally defined for m = 5, 7, 8, 9, and 11 only

An m‐cycle system (S,C) of order n is said to be {2,3}‐perfect provided each pair of vertices is connected by a path of length 2 in an m‐cycle of C and a path of length 3 in an m‐cycle of C. The class of {2,3}‐perfect m‐cycle systems is said to be equationally defined provided, there exists a variety of quasigroups V with the property that a finite quasigroup (Q, , \, /) belongs to V if and only if its multiplicative (Q, ) part can be constructed from a {2,3}‐perfect m‐cycle system using the 2‐construction (a a = a for all a ∈ Q and if a ≠ b, a b = c and b a = d if and only if the m‐cycle (…, d, x, a, b, y, c, …) ∈ C). The object of this paper is to show that the class of {2,3}‐perfect m‐cycle systems cannot be equationally defined for all m ≥ 10, m ≠ 11. This combined with previous results shows that {2, 3}‐perfect m‐cycle systems are equationally defined for m = 5, 7, 8, 9, and 11 only. © 2004 Wiley Periodicals, Inc.     

Tiling 3‐Uniform Hypergraphs With

Let denote the hypergraph consisting of two triples on four points. For an integer n, let denote the smallest integer d so that every 3‐uniform hypergraph G of order n with minimum pair‐degree contains vertex‐disjoint copies of . Kühn and Osthus (J Combin Theory, Ser B 96(6) (2006), 767–821) proved that holds for large integers n. Here, we prove the exact counterpart, that for all sufficiently large integers n divisible by 4, A main ingredient in our proof is the recent “absorption technique” of Rödl, Ruciński, and Szemerédi (J. Combin. Theory Ser. A 116(3) (2009), 613–636).     

On Generalized Ramsey Numbers for 3‐Uniform Hypergraphs

The well‐known Ramsey number is the smallest integer n such that every ‐free graph of order n contains an independent set of size u. In other words, it contains a subset of u vertices with no K₂. Erd?s and Rogers introduced a more general problem replacing K₂ by  for . Extending the problem of determining Ramsey numbers they defined the numbers where the minimum is taken over all ‐free graphs G of order n. In this note, we study an analogous function for 3‐uniform hypergraphs. In particular, we show that there are constants c₁ and c₂ depending only on s such that      

The ζ(2) limit in the random assignment problem

The random assignment (or bipartite matching) problem asks about A_n=min_π ∑c(i, π(i)), where (c(i, j)) is a n×n matrix with i.i.d. entries, say with exponential(1) distribution, and the minimum is over permutations π. Mézard and Parisi (1987) used the replica method from statistical physics to argue nonrigorously that EA_n→ζ(2)=π²/6. Aldous (1992) identified the limit in terms of a matching problem on a limit infinite tree. Here we construct the optimal matching on the infinite tree. This yields a rigorous proof of the ζ(2) limit and of the conjectured limit distribution of edge‐costs and their rank‐orders in the optimal matching. It also yields the asymptotic essential uniqueness property: every almost‐optimal matching coincides with the optimal matching except on a small proportion of edges. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 381–418, 2001     

Simple 3‐designs of PSL(2, 2n) with block size 7

In this paper, we determine the number of the orbits of 7‐subsets of with a fixed orbit length under the action of PSL(2, 2ⁿ). As a consequence, we determine the distribution of λ for which there exists a simple 3‐(2ⁿ + 1, 7, λ) design with PSL(2, 2ⁿ) as an automorphism group. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 1–17, 2008     

On (4, 2)‐Choosable Graphs

A graph G is called ‐choosable if for any list assignment L that assigns to each vertex v a set of a permissible colors, there is a b‐tuple L‐coloring of G . An (a , 1)‐choosable graph is also called a‐choosable. In the pioneering article on list coloring of graphs by Erd?s et al.  2 , 2‐choosable graphs are characterized. Confirming a special case of a conjecture in  2 , Tuza and Voigt  3 proved that 2‐choosable graphs are ‐choosable for any positive integer m . On the other hand, Voigt 6 proved that if m is an odd integer, then these are the only ‐choosable graphs; however, when m is even, there are ‐choosable graphs that are not 2‐choosable. A graph is called 3‐choosable‐critical if it is not 2‐choosable, but all its proper subgraphs are 2‐choosable. Voigt conjectured that for every positive integer m , all bipartite 3‐choosable‐critical graphs are ‐choosable. In this article, we determine which 3‐choosable‐critical graphs are (4, 2)‐choosable, refuting Voigt's conjecture in the process. Nevertheless, a weaker version of the conjecture is true: we prove that there is an even integer k such that for any positive integer m , every bipartite 3‐choosable‐critical graph is ‐choosable. Moving beyond 3‐choosable‐critical graphs, we present an infinite family of non‐3‐choosable‐critical graphs that have been shown by computer analysis to be (4, 2)‐choosable. This shows that the family of all (4, 2)‐choosable graphs has rich structure.     

Uniqueness of weak solutions in critical space of the 3‐D time‐dependent Ginzburg‐Landau equations for superconductivity

We prove the uniqueness of weak solutions of the 3‐D time‐dependent Ginzburg‐Landau equations for super‐conductivity with initial data (ψ₀, A₀)∈ L² under the hypothesis that (ψ, A) ∈ L^s(0, T; L^r,∞) × (0, T; with Coulomb gauge for any (r, s) and satisfying + = 1, + = 1, ≥ , ≥ and 3 < r ≤ 6, 3 < ≤ ∞. Here L^r,∞ ≡ is the Lorentz space. As an application, we prove a uniqueness result with periodic boundary condition when ψ₀ ∈ , A₀ ∈ L³ (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

An asymptotic expansion for the semi‐infinite sum of Dirac‐δ functions

In this paper, we derive an asymptotic expansion for the semi‐infinite sum of Dirac‐δ functions centered at discrete equidistant points defined by the set . The method relies on the Laplace transform of the semi‐infinite sum of Dirac‐δ functions. The derived series distribution takes the form of the Euler‐Maclaurin summation when the distributions are defined for complex or real‐valued continuous functions over the interval . For n=1, the series expansion contributes with a term equal to δ(x)/2, which survives in the limit when a→0⁺. This term represents a correction term, which is in general omitted in calculations of the density of states of quantum confined systems by finite‐size effects.     

On the density of 2‐colorable 3‐graphs in which any four points span at most two edges

Let ex₂(n, K) be the maximum number of edges in a 2‐colorable K‐free 3‐graph (where K={123, 124, 134} ). The 2‐chromatic Turán density of K is $\pi_{2}({K}_{4}^-) =lim_{{n}\to \infty} {ex}_{2}({n}, {K}_{4}^-)/\left(_{3}^{n}\right)Let ex₂(n, K) be the maximum number of edges in a 2‐colorable K‐free 3‐graph (where K={123, 124, 134} ). The 2‐chromatic Turán density of K is $\pi_{2}({K}_{4}^-) =lim_{{n}\to \infty} {ex}_{2}({n}, {K}_{4}^-)/\left(_{3}^{n}\right)$. We improve the previously best known lower and upper bounds of 0.25682 and 3/10?ε, respectively, by showing that This implies the following new upper bound for the Turán density of K In order to establish these results we use a combination of the properties of computer‐generated extremal 3‐graphs for small n and an argument based on “super‐saturation”. Our computer results determine the exact values of ex(n, K) for n≤19 and ex₂(n, K) for n≤17, as well as the sets of extremal 3‐graphs for those n. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 105–114, 2010     

Graphs with Few 3‐Cliques and 3‐Anticliques are 3‐Universal

For given integers we ask whether every large graph with a sufficiently small number of k‐cliques and k‐anticliques must contain an induced copy of every l‐vertex graph. Here we prove this claim for with a sharp bound. A similar phenomenon is established as well for tournaments with .     

Minimum K2, 3‐Saturated Graphs

A graph is K_{2, 3}‐saturated if it has no subgraph isomorphic to K_{2, 3}, but does contain a K_{2, 3} after the addition of any new edge. We prove that the minimum number of edges in a K_{2, 3}‐saturated graph on vertices is sat.