A new upper bound for the length of snakes

Ad-dimensional circuit code of spreads is a simple circuitC in the graph of thed-dimen sional unit cube with the property that for any verticesx andy ofC which differ in exactlyr co-ordinates,r<s, there exists a path fromx toy consisting ofr edges ofC. This property is useful for detecting and limiting errors. In this paper we give a new upper bound for the maximum length of ad-dimensional circuit code of spread 2.     

A new lower bound for Snake-in-the-Box Codes

In this paper we give a new lower bound on the length of Snake-in-the-Box Codes, i.e., induced cycles in thed-dmensional cube. The bound is a linear function of the number of vertices of the cube and improves the boundc·2 ^d /d, wherec is a constant, proved by Danzer and Klee.     

On the number of edge disjoint cliques in graphs of given size

In this paper, we prove that any graph ofn vertices andt _r–1(n)+m edges, wheret _r–1(n) is the Turán number, contains (1–o(1)m edge disjointK _r'sifm=o(n ²). Furthermore, we determine the maximumm such that every graph ofn vertices andt _r–1(n)+m edges containsm edge disjointK _r's ifn is sufficiently large.Research partially supported by Hungarian National Foundation for Scientific Research Grant no. 1812.     

Natural bounded concentrators

We give the first known direct construction for linear families of bounded concentrators. The construction is explicit and the results are simple natural bounded concentrators. Let be the field withq elements,g(x)∈F _q [x] of degree greater than or equal to 2, and . LetI _nputs=H/A,O _utputs=H/B, and draw an edge betweenaA andbB iffaA∩bB≠ϕ. We prove that for everyq≥5 this graph is an concentrator. Part of this research was done while the author was at the department of Computer Science, The University of British Columbia, Vancouver, B.C., Canada.     

Small maximally disjoint union-free families

A family F of k-subsets of an n-set X is disjoint union-free (DUF) if all disjoint pairs of elements of F have distinct unions; that is, if for every A,B,C,D∈F, A∩B=C∩D=∅ and A∪B=C∪D implies {A,B}={C,D}. DUF families of maximum size have been studied by Erdös and Füredi. Let F be DUF with the property that F∪{E} is not DUF for any k-subset E of X not already in F. Then F is maximally DUF. We introduce the problem of finding the minimum size of maximally DUF families and provide bounds on this quantity for k=3.     

Bounding the number of circuits of a graph

Letc(G) denote the number of circuits of a graphG. In this paper, we characterize those minor-closed classesG of graphs for which there is a polynomial functionp(.) such thatc(G)p(|E(G)|) for all graphsG inG.     

Bounding the number of bases of a matroid

Letb(M) andc(M), respectively, be the number of bases and circuits of a matroidM. For any given minor closed class? of matroids, the following two questions, are investigated in this paper. (1) When is there a polynomial functionp(x) such thatb(M)≤p(c(m)|E(M)|) for every matroidM in?? (2) When is there a polynomial functionp(x) such thatb(M)≤p(|E(M)|) for every matroidM in?? Let us denote byM _Mn the direct sum ofn copies ofU _1,2. We prove that the answer to the first question is affirmative if and only if someM _Mn is not in?. Furthermore, if all the members of? are representable over a fixed finite field, then we prove that the answer to the second question is affirmative if and only if, also, someM _Mn is not in?.     

Hypergraph families with bounded edge cover or transversal number

The transversal number, packing number, covering number and strong stability number of hypergraphs are denoted by τ, ν, ϱ and α, respectively. A hypergraph family t is called τ-bound (ϱ-bound) if there exists a “binding function”f(x) such that τ(H)≦f(v(H)) (ϱ(H)≦f(α(H))) for allH ∈ t. Methods are presented to show that various hypergraph families are τ-bound and/or ϱ-bound. The results can be applied to families of geometrical nature like subforests of trees, boxes, boxes of polyominoes or to families defined by hypergraph theoretic terms like the family where every subhypergraph has the Helly-property.     

Extremal energies of trees with a given domination number

The energy of a graph is defined as the sum of the absolute values of the eigenvalues of its adjacency matrix. Let T(n,γ) be the set of trees of order n and with domination number γ. In this paper, we characterize the tree from T(n,γ) with the minimal energy, and determine the tree from T(n,γ) where n=kγ with maximal energy for .     

Covering odd cycles

We estimate the number of vertices/edges necessary to cover all odd cycles in graphs of given order and odd girth.To the memory of Pál Erds     

Explicit constructions of graphs without short cycles and low density codes

We give an explicit construction of regular graphs of degree 2r withn vertices and girth ≧c logn/logr. We use Cayley graphs of factor groups of free subgroups of the modular group. An application to low density codes is given.     

Nonlinear diffusion with a bounded stationary level surface

We consider nonlinear diffusion of some substance in a container (not necessarily bounded) with bounded boundary of class C²$C^2$. Suppose that, initially, the container is empty and, at all times, the substance at its boundary is kept at density 1. We show that, if the container contains a proper C²$C^2$-subdomain on whose boundary the substance has constant density at each given time, then the boundary of the container must be a sphere. We also consider nonlinear diffusion in the whole RN${\mathbb{R}}^N$ of some substance whose density is initially a characteristic function of the complement of a domain with bounded C²$C^2$ boundary, and obtain similar results. These results are also extended to the heat flow in the sphere SN${\mathbb{S}}^N$ and the hyperbolic space HN${\mathbb{H}}^N$.     

On boundary-value problems for the laplacian in bounded and in unbounded domains with perforated boundaries

In this paper we consider boundary-value problems in domains with perforated boundaries. We use the classification of homogenized (limit) problems depending on the ratio of small parameters, which characterize the diameter of the holes and the distance between them. We study the analogue of the Helmholtz resonator for domains with a perforated boundary.     

Optimal tristance anticodes in certain graphs

For z₁,z₂,z₃∈Zⁿ, the tristance d₃(z₁,z₂,z₃) is a generalization of the L₁-distance on Zⁿ to a quantity that reflects the relative dispersion of three points rather than two. A tristance anticodeA_d of diameter d is a subset of Zⁿ with the property that d₃(z₁,z₂,z₃)?d for all z₁,z₂,z₃∈A_d. An anticode is optimal if it has the largest possible cardinality for its diameter d. We determine the cardinality and completely classify the optimal tristance anticodes in Z² for all diameters d?1. We then generalize this result to two related distance models: a different distance structure on Z² where d(z₁,z₂)=1 if z₁,z₂ are adjacent either horizontally, vertically, or diagonally, and the distance structure obtained when Z² is replaced by the hexagonal lattice A₂. We also investigate optimal tristance anticodes in Z³ and optimal quadristance anticodes in Z², and provide bounds on their cardinality. We conclude with a brief discussion of the applications of our results to multi-dimensional interleaving schemes and to connectivity loci in the game of Go.     

Hypergraphs in which all disjoint pairs have distinct unions

Let ℓ be a set-system ofr-element subsets on ann-element set,r≧3. It is proved that if |ℓ|>3.5 then ℓ contains four distinct membersA, B, C, D such thatA∪B=C∪D andA∩B=C∩D=0.     

On the full automorphism group of a graph

While it is easy to characterize the graphs on which a given transitive permutation groupG acts, it is very difficult to characterize the graphsX with Aut (X)=G. We prove here that for the certain transitive permutation groups a simple necessary condition is also sufficient. As a corollary we find that, whenG is ap-group with no homomorphism ontoZ _p wrZ _p , almost all Cayley graphs ofG have automorphism group isomorphic toG.     

The Cardinality of Sets of <Emphasis Type="Italic">k</Emphasis>-Independent Vectors over Finite Fields

A set of vectors is k-independent if all its subsets with no more than k elements are linearly independent. We obtain a result concerning the maximal possible cardinality Ind _q (n, k) of a k-independent set of vectors in the n-dimensional vector space F _q ⁿ over the finite field F _q of order q. Namely, we give a necessary and sufficient condition for Ind _q (n, k) = n + 1. We conclude with some pertinent remarks re applications of our results to codes, graphs and hypercubes. Supported, in part by grants EP/C000285, NSF-DMS-0439734 and NSF-DMS-0555839. S. B. Damelin thanks the Institute for Mathematics and Applications for their hospitality.     

Asymmetric potentials and motor effect: a homogenization approach

We provide a mathematical analysis for the appearance of motor effects, i.e., the concentration (as Dirac masses) at one side of the domain, for the solution of a Fokker–Planck system with two components, one with an asymmetric potential and diffusion and one with pure diffusion. The system has been proposed as a model for motor proteins moving along molecular filaments. Its components describe the densities of different conformations of proteins.     

Maximum degree and fractional matchings in uniform hypergraphs

Let ℋ be a family ofr-subsets of a finite setX. SetD(ℋ)= |{E:x∈E∈ℋ}|, (maximum degree). We say that ℋ is intersecting if for anyH,H′ ∈ ℋ we haveH ∩H′ ≠ 0. In this case, obviously,D(ℋ)≧|ℋ|/r. According to a well-known conjectureD(ℋ)≧|ℋ|/(r−1+1/r). We prove a slightly stronger result. Let ℋ be anr-uniform, intersecting hypergraph. Then either it is a projective plane of orderr−1, consequentlyD(ℋ)=|ℋ|/(r−1+1/r), orD(ℋ)≧|ℋ|/(r−1). This is a corollary to a more general theorem on not necessarily intersecting hypergraphs.     

A nowhere-zero point in linear mappings

We state the following conjecture and prove it for the case whereq is a proper prime power:Let A be a nonsingular n by n matrix over the finite field GF_qq4, then there exists a vector x in (GF_q)ⁿ such that both x and Ax have no zero component.Research supported in part by Allon Fellowship and by a Bat Sheva de Rothschild grant.