More results on perfect (3,3,6k + 4; 6k − 2)‐threshold schemes

A (2,3)‐packing on X is a pair (X, ), where is a set of 3‐subsets (called blocks) of X, such that any pair of distinct points from X occurs together in at most one block. Its leave is a graph (X,E) such that E consists of all the pairs which do not appear in any block of . In this article, we shall construct a set of 6k ? 2 disjoint (2,3)‐packings of order 6k + 4 with K_1,3 ∪ 3kK₂ or G₁ ∪ (3k ? 1)K₂ as their common leave for any integer k ≥ 1 with a few possible exceptions (G₁ is a special graph of order 6). Such a system can be used to construct perfect threshold schemes as noted by Schellenberg and Stinson ( 22 ). © 2006 Wiley Periodicals, Inc. J Combin Designs     

A Self‐Dual Polar Factorization for Vector Fields

We show that any nondegenerate vector field u in \begin{align*}L^{\infty}(\Omega, \mathbb{R}^N)\end{align*}, where Ω is a bounded domain in \begin{align*}\mathbb{R}^N\end{align*}, can be written as \begin{align*}u(x)= \nabla_1 H(S(x), x)\quad {\text for a.e.\ x \in \Omega}\end{align*}}, where S is a measure‐preserving point transformation on Ω such that \begin{align*}S^2=I\end{align*} a.e. (an involution), and \begin{align*}H: \mathbb{R}^N \times \mathbb{R}^N \to \mathbb{R}\end{align*} is a globally Lipschitz antisymmetric convex‐concave Hamiltonian. Moreover, u is a monotone map if and only if S can be taken to be the identity, which suggests that our result is a self‐dual version of Brenier's polar decomposition for the vector field as \begin{align*}u(x)=\nabla \phi (S(x))\end{align*}, where ? is convex and S is a measure‐preserving transformation. We also describe how our polar decomposition can be reformulated as a (self‐dual) mass transport problem. © 2012 Wiley Periodicals, Inc.     

On (ε,k)‐min‐wise independent permutations

A family of permutations of [n] = {1,2,…,n} is (ε,k)‐min‐wise independent if for every nonempty subset X of at most k elements of [n], and for any x ∈ X, the probability that in a random element π of , π(x) is the minimum element of π(X), deviates from 1/∣X∣ by at most ε/∣X∣. This notion can be defined for the uniform case, when the elements of are picked according to a uniform distribution, or for the more general, biased case, in which the elements of are chosen according to a given distribution D. It is known that this notion is a useful tool for indexing replicated documents on the web. We show that even in the more general, biased case, for all admissible k and ε and all large n, the size of must satisfy as well as This improves the best known previous estimates even for the uniform case. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

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     

Tauberian theorem for m‐spherical transforms on the Heisenberg group

In this paper we prove a Tauberian type theorem for the space L ( H _n ). This theorem gives sufficient conditions for a L ( H _n ) submodule J ? L ( H _n ) to make up all of L ( H _n ). As a consequence of this theorem, we are able to improve previous results on the Pompeiu problem with moments on the Heisenberg group for the space L^∞( H _n ). In connection with the Pompeiu problem, given the vanishing of integrals ∫ z ^m L _g f ( z , 0) dσ ( z ) = 0 for all g ∈ H _n and i = 1, 2 for appropriate radii r₁ and r₂, we now have the (improved) conclusion f ≡ 0, where = · · · and form the standard basis for T^(0,1)( H _n ). (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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     

Small degree out‐branchings

Using a suitable orientation, we give a short proof of a strengthening of a result of Czumaj and Strothmann 4 : Every 2‐edge‐connected graph G contains a spanning tree T with the property that for every vertex v. As an analogue of this result in the directed case, we prove that every 2‐arc‐strong digraph D has an out‐branching B such that . A corollary of this is that every k‐arc‐strong digraph D has an out‐branching B such that , where . We conjecture that in this case would be the right (and best possible) answer. If true, this would again imply a strengthening of a result from 4 concerning spanning trees with small degrees in k‐connected graphs when k ≥ 2. We prove that for acyclic digraphs the existence of an out‐branching satisfying prescribed bounds on the out‐degrees of each vertex can be checked in polynomial time. A corollary of this is that the existence of arc‐disjoint branchings , , where the first is an out‐branching rooted at s and the second an in‐branching rooted at t, can be checked in polynomial time for the class of acyclic digraphs © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 297–307, 2003     

Existence of 3‐chromatic Steiner quadruple systems

A Steiner quadruple system of order v (briefly SQS (v)) is a pair (X, ), where X is a v‐element set and is a set of 4‐element subsets of X (called blocks or quadruples), such that each 3‐element subset of X is contained in a unique block of . The chromatic number of an SQS(v)(X, ) is the smallest m for which there is a map such that for all , where . The system (X, ) is equitably m‐chromatic if there is a proper coloring with minimal m for which the numbers differ from each other by at most 1. Linek and Mendelsohn showed that an equitably 3‐chromatic SQS(v) exists for v ≡ 4, 8, 10 (mod 12), v ≥ 16. In this article we show that an equitably 3‐chromatic SQS(v) exists for v ≡ 2 (mod 12) with v > 2. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 469–477, 2007     

C‐perfect hypergraphs

Let ${\mathcal{H}}=({{X}},{\mathcal{E}})Let ${\mathcal{H}}=({{X}},{\mathcal{E}})$ be a hypergraph with vertex set X and edge set ${\mathcal{E}}$. A C‐coloring of ${\mathcal{H}}$ is a mapping ?:X→? such that |?(E)|<|E| holds for all edges ${{E}}\in{\mathcal{E}}$ (i.e. no edge is multicolored). We denote by $\bar{\chi}({\mathcal{H}})$ the maximum number |?(X)| of colors in a C‐coloring. Let further $\alpha({\mathcal{H}})$ denote the largest cardinality of a vertex set S?X that contains no ${{E}}\in{\mathcal{E}}$, and $\tau({\mathcal{H}})=|{{X}}|-\alpha({\mathcal{H}})$ the minimum cardinality of a vertex set meeting all $E \in {\mathcal{E}}$. The hypergraph ${\mathcal{H}}$ is called C‐perfect if $\bar{\chi}({\mathcal{H}}\prime)=\alpha({\mathcal{H}}\prime)$ holds for every induced subhypergraph ${\mathcal{H}}\prime\subseteq{\mathcal{H}}$. If ${\mathcal{H}}$ is not C‐perfect but all of its proper induced subhypergraphs are, then we say that it is minimally C‐imperfect. We prove that for all r, k∈? there exists a finite upper bound h(r, k) on the number of minimally C‐imperfect hypergraphs ${\mathcal{H}}$ with $\tau({\mathcal{H}})\le {{k}}$ and without edges of more than r vertices. We give a characterization of minimally C‐imperfect hypergraphs that have τ=2, which also characterizes implicitly the C‐perfect ones with τ=2. From this result we derive an infinite family of new constructions that are minimally C‐imperfect. A characterization of minimally C‐imperfect circular hypergraphs is presented, too. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 132–149, 2010     

A generalization of the Oberwolfach problem

Let n > 1 be an integer and let a₂,a₃,…,a_n be nonnegative integers such that . Then can be factored into ‐factors, ‐factors,…, ‐factors, plus a 1‐factor. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 151–161, 2002     

Eulerian subgraphs in 3‐edge‐connected graphs and Hamiltonian line graphs

In this paper, we show that if G is a 3‐edge‐connected graph with and , then either G has an Eulerian subgraph H such that , or G can be contracted to the Petersen graph in such a way that the preimage of each vertex of the Petersen graph contains at least one vertex in S. If G is a 3‐edge‐connected planar graph, then for any , G has an Eulerian subgraph H such that . As an application, we obtain a new result on Hamiltonian line graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 308–319, 2003     

Ryser's embedding problem for Hadamard matrices

What is the minimum order of a Hadamard matrix that contains an a by b submatrix of all 1's? Newman showed that where c^? denotes the smallest order greater than or equal to c for which a Hadamard matrix exists. It follows that if 4 divides both a and b, and if the Hadamard conjecture is true, then . We establish the improved bounds for min {a,b} ≥ 2. The Hadamard conjecture therefore implies that if 4 divides both 2ab and ?a/2? ?b/2?, then (a, b) = 2 · max {?a/2?b, ?b/2?a}. Our lower bound comes from a counting argument, while our upper bound follows from a sub‐multiplicative property of : Improvements in our upper bound occur when suitable conference matrices or Bush‐type Hadamard matrices exist. We conjecture that any (1,?1)‐matrix of size a by b occurs as a submatrix of some Hadamard matrix of order at most . © 2005 Wiley Periodicals, Inc. J Combin Designs     

Ore‐type degree conditions for a graph to be H‐linked

Given a fixed multigraph H with V(H) = {h₁,…, h_m}, we say that a graph G is H‐linked if for every choice of m vertices v₁, …, _vm in G, there exists a subdivision of H in G such that for every i, v_i is the branch vertex representing h_i. This generalizes the notion of k‐linked graphs (as well as some other notions). For a family of graphs, a graph G is ‐linked if G is H‐linked for every . In this article, we estimate the minimum integer r = r(n, k, d) such that each n‐vertex graph with is ‐linked, where is the family of simple graphs with k edges and minimum degree at least . © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 14–26, 2008     

Explicit sparse almost‐universal graphs for ${\bf {{\cal G}(n, {k \over n})}}$

For any integer n, let be a probability distribution on the family of graphs on n vertices (where every such graph has nonzero probability associated with it). A graph Γ is ‐almost‐universal if Γ satisifies the following: If G is chosen according to the probability distribution , then G is isomorphic to a subgraph of Γ with probability 1 ‐ . For any p ∈ [0,1], let (n,p) denote the probability distribution on the family of graphs on n vertices, where two vertices u and v form an edge with probability p, and the events {u and v form an edge}; u,v ∈ V (G) are mutually independent. For k ≥ 4 and n sufficiently large we construct a ‐almost‐universal‐graph on n vertices and with O(n)polylog(n) edges, where q = ? ? for such k ≤ 6, and where q = ? ? for k ≥ 7. The number of edges is close to the lower bound of Ω( ) for the number of edges in a universal graph for the family of graphs with n vertices and maximum degree k. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Vertex suppression in 3‐connected graphs

To suppress a vertex in a finite graph G means to delete it and add an edge from a to b if a, b are distinct nonadjacent vertices which formed the neighborhood of . Let be the graph obtained from by suppressing vertices of degree at most 2 as long as it is possible; this is proven to be well defined. Our main result states that every 3‐connected graph G has a vertex x such that is 3‐connected unless G is isomorphic to , , or to a wheel for some . This leads to a generator theorem for 3‐connected graphs in terms of series parallel extensions. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 41–54, 2008     

The quasi‐randomness of hypergraph cut properties

Let satisfy and suppose a k‐uniform hypergraph on n vertices satisfies the following property; in any partition of its vertices into k sets of sizes , the number of edges intersecting is (asymptotically) the number one would expect to find in a random k‐uniform hypergraph. Can we then infer that H is quasi‐random? We show that the answer is negative if and only if . This resolves an open problem raised in 1991 by Chung and Graham [J AMS 4 (1991), 151–196]. While hypergraphs satisfying the property corresponding to are not necessarily quasi‐random, we manage to find a characterization of the hypergraphs satisfying this property. Somewhat surprisingly, it turns out that (essentially) there is a unique non quasi‐random hypergraph satisfying this property. The proofs combine probabilistic and algebraic arguments with results from the theory of association schemes. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

Asymptotically self‐similar global solutions for a higher‐order semilinear parabolic equation

In this paper, we study the higher‐order semilinear parabolic equation where m, p>1 and $a\,\in\,\mathbb{R}$. For p>1+2m/N, we prove that the global existence of mild solutions for small initial data with respect to some norm. Some of those solutions are proved to be asymptotic self‐similar. Copyright © 2009 John Wiley & Sons, Ltd.     

Bush‐type Hadamard matrices and symmetric designs

Abstact: A symmetric 2‐(100, 45, 20) design is constructed that admits a tactical decomposition into 10 point and block classes of size 10 such that every point is in either 0 or 5 blocks from a given block class, and every block contains either 0 or 5 points from a given point class. This design yields a Bush‐type Hadamard matrix of order 100 that leads to two new infinite classes of symmetric designs with parameters and where m is an arbitrary positive integer. Similarly, a Bush‐type Hadamard matrix of order 36 is constructed and used for the construction of an infinite family of designs with parameters and a second infinite family of designs with parameters where m is any positive integer. © 2000 John Wiley & Sons, Inc. J Combin Designs 9: 72–78, 2001     

Inexpensive d‐dimensional matchings

Suppose that independent U(0, 1) weights are assigned to the ${d\choose 2}n^{2}$ edges of the complete d‐partite graph with n vertices in each of the d maximal independent sets. Then the expected weight of the minimum‐weight perfect d‐dimensional matching is at least $\frac{3}{16}n^{1-(2/d)}$. We describe a randomized algorithm that finds a perfect d‐dimensional matching whose expected weight is at most 5d³n^1?(2/d)+d¹⁵ for all d≥3 and n≥1. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 50–58, 2002     

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)