Packing 4-Cycles in Eulerian and Bipartite Eulerian Tournaments with an Application to Distances in Interchange Graphs

We prove that every Eulerian orientation of K_m,n contains arc-disjoint directed 4-cycles, improving earlier lower bounds. Combined with a probabilistic argument, this result is used to prove that every regular tournament with n vertices contains arc-disjoint directed 4-cycles. The result is also used to provide an upper bound for the distance between two antipodal vertices in interchange graphs.Received February 6, 2004     

The Maximum Size Of Graphs With A Unique<Emphasis Type="Italic">k</Emphasis>- Factor

For suitable positive integers n and k let m(n, k) denote the maximum number of edges in a graph of order n which has a unique k-factor. In 1964, Hetyei and in 1984, Hendry proved for even n and , respectively. Recently, Johann confirmed the following conjectures of Hendry: for and kn even and for n = 2kq, where q is a positive integer. In this paper we prove for and kn even, and we determine m(n, 3).     

On a Problem Concerning k-Subdomination Numbers of Graphs

One of numerical invariants concerning domination in graphs is the k-subdomination number of a graph G. A conjecture concerning it was expressed by J.H. Hattingh, namely that for any connected graph G with n vertices and any k with the inequality holds. This paper presents a simple counterexample which disproves this conjecture. This counterexample is the graph of the three-dimensional cube and k = 5.     

Sequential Dynamical Systems Over Words

In this paper we study sequential dynamical systems (SDS) over words. An SDS is a triple consisting of: (a) a graph Y with vertex set {v₁, ..., v_n}, (b) a family of Y-local functions , where K is a finite field and (c) a word w, i.e., a family (w₁, ..., w_k), where w_i is a Y-vertex. A map is called Y-local if and only if it fixes all variables and depends exclusively on the variables , for . An SDS induces an SDS- map, , obtained by the map-composition of the functions according to w. We show that an SDS induces in addition the graph G(w,Y) having vertex set {1, ..., k} where r, s are adjacent if and only if w_s, w_r are adjacent in Y. G(w, Y) is acted upon by S_k via and Fix(w) is the group of G(w, Y) graph automorphisms which fix w. We analyze G(w, Y)-automorphisms via an exact sequence involving the normalizer of Fix(w) in Aut(G(w, Y)), Fix(w) and Aut(Y). Furthermore we introduce an equivalence relation over words and prove a bijection between word equivalence classes and certain orbits of acyclic orientations of G(w, Y). Received September 12, 2004     

A Sharp Bound for the Number of Sets that Pairwise Intersect at <Emphasis Type="Italic">k</Emphasis> Positive Values

In this paper we prove that if is a set of k positive integers and {A ₁, ..., A _m } is a family of subsets of an n-element set satisfying , for all 1 i < j m, then . The case k = 1 was proven 50 years ago by Majumdar.     

The Structure of Disjoint Iteration Groups on the Circle

The aim of the paper is to investigate the structure of disjoint iteration groups on the unit circle that is, families of homeomorphisms such that and each F ^veither is the identity mapping or has no fixed point ((V, +) is an arbitrary 2-divisible nontrivial (i.e., card V> 1) abelian group).     

An Upper Bound for the Cardinality of an <Emphasis Type="Italic">s</Emphasis>-Distance Set in Euclidean Space

In this paper we show that if X is an s-distance set in ^m and X is on p concentric spheres then Moreover if X is antipodal, then .     

Random k-Sat: A Tight Threshold For Moderately Growing k

We consider a random instance I of k-SAT with n variables and m clauses, where k=k(n) satisfies k—log₂ n. Let m ₀=2 ^k nln2 and let =(n)>0 be such that n. We prove that

Addendum To Schrijver's Work On Minimum Permanents

Let denote the set of n×n binary matrices which have each row and column sum equal to k. For 2≤k≤n→∞ we show that is asymptotically equal to (k−1)^k−1k^2−k. This confirms Conjecture 23 in Minc's catalogue of open problems. * Written while the author was employed by the Department of Computer Science at the Australian National University.     

Approximate <Emphasis Type="Italic">C</Emphasis>*-ternary ring homomorphisms

In this paper, we establish the generalized Hyers–Ulam–Rassias stability of C*-ternary ring homomorphisms associated to the Trif functional equation

（Z2）^k-Actions with Fixed Point Set of Constant Codimension 2^k＋ 2

Let J.^r ,k denote the ideal in MO. of cobordism classes containing a representative that admits (Z2)^k-actions with a fixed point set of constant codimension r. In this paper we determine J,k^2k 2 and Ja,3^2^3 1.     

Matching Polynomials And Duality

Let G be a simple graph on n vertices. An r-matching in G is a set of r independent edges. The number of r-matchings in G will be denoted by p(G, r). We set p(G, 0) = 1 and define the matching polynomial of G by and the signless matching polynomial of G by .It is classical that the matching polynomials of a graph G determine the matching polynomials of its complement . We make this statement more explicit by proving new duality theorems by the generating function method for set functions. In particular, we show that the matching functions and are, up to a sign, real Fourier transforms of each other.Moreover, we generalize Foatas combinatorial proof of the Mehler formula for Hermite polynomials to matching polynomials. This provides a new short proof of the classical fact that all zeros of µ(G, x) are real. The same statement is also proved for a common generalization of the matching polynomial and the rook polynomial.     

Profile of Blow-up Solution to Hyperbolic System with Nonlocal Term

This paper is concerned with a nonlocal hyperbolic system as follows utt = △u ＋ （∫Ωvdx ）^p for x∈R^N,t〉0 ,utt = △u ＋ （∫Ωvdx ）^q for x∈R^N,t〉0 ,u（x,0）=u0（x）,ut（x,0）=u01（x） for x∈R^N,u（x,0）=u0（x）,ut（x,0）=u01（x） for x∈R^N, where 1≤ N ≤3, p ≥1, q ≥ 1 and pq 〉 1. Here the initial values are compactly supported and Ω belong to R^N is a bounded open region. The blow-up curve, blow-up rate and profile of the solution are discussed.     

On A Hypergraph Turán Problem Of Frankl

Let be the 2k-uniform hypergraph obtained by letting P₁, . . .,P_r be pairwise disjoint sets of size k and taking as edges all sets P_i∪P_j with i ≠ j. This can be thought of as the ‘k-expansion’ of the complete graph K_r: each vertex has been replaced with a set of size k. An example of a hypergraph with vertex set V that does not contain can be obtained by partitioning V = V1 ∪V₂ and taking as edges all sets of size 2k that intersect each of V₁ and V₂ in an odd number of elements. Let denote a hypergraph on n vertices obtained by this construction that has as many edges as possible. For n sufficiently large we prove a conjecture of Frankl, which states that any hypergraph on n vertices that contains no has at most as many edges as . Sidorenko has given an upper bound of for the Tur′an density of for any r, and a construction establishing a matching lower bound when r is of the form 2^p+1. In this paper we also show that when r=2^p+1, any -free hypergraph of density looks approximately like Sidorenko’s construction. On the other hand, when r is not of this form, we show that corresponding constructions do not exist and improve the upper bound on the Turán density of to , where c(r) is a constant depending only on r. The backbone of our arguments is a strategy of first proving approximate structure theorems, and then showing that any imperfections in the structure must lead to a suboptimal configuration. The tools for its realisation draw on extremal graph theory, linear algebra, the Kruskal–Katona theorem and properties of Krawtchouck polynomials. * Research supported in part by NSF grants DMS-0355497, DMS-0106589, and by an Alfred P. Sloan fellowship.     

The Number Of Orientations Having No Fixed Tournament

Let T be a fixed tournament on k vertices. Let D(n,T ) denote the maximum number of orientations of an n-vertex graph that have no copy of T. We prove that for all sufficiently (very) large n, where t_k−1(n) is the maximum possible number of edges of a graphon n vertices with no K_k, (determined by Turán’s Theorem). The proof is based on a directed version of Szemerédi’s regularity lemma together with some additional ideas and tools from Extremal Graph Theory, and provides an example of a precise result proved by applying this lemma. For the two possible tournaments with three vertices we obtain separate proofs that avoid the use of the regularity lemma and therefore show that in these cases already holds for (relatively) small values of n. * Research supported in part by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.     

Linear Codes and Character Sums

Let V be an rn-dimensional linear subspace of . Suppose the smallest Hamming weight of non-zero vectors in V is d. (In coding-theoretic terminology, V is a linear code of length n, rate r and distance d.) We settle two extremal problems on such spaces.First, we prove a (weak form) of a conjecture by Kalai and Linial and show that the fraction of vectors in V with weight d is exponentially small. Specifically, in the interesting case of a small r, this fraction does not exceed .We also answer a question of Ben-Or and show that if , then for every k, at most vectors of V have weight k.Our work draws on a simple connection between extremal properties of linear subspaces of and the distribution of values in short sums of -characters.* Supported in part by grants from the Israeli Academy of Sciences and the Binational Science Foundation Israel-USA. This work was done while the author was a student in the Hebrew University of Jerusalem, Israel.     

The number of partial orders of fixed width

We investigate the approximate number of n-element partial orders of width k, for each fixed k. We show that the number of width 2 partial orders with vertex set {1, 2, ..., n} is

On a periodic boundary value problem for cyclic feedback type linear functional differential systems

Nonimprovable effective sufficient conditions are established for the unique solvability of the periodic problem

Complete Minors In <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">s,s</Emphasis></Subscript>-Free Graphs

We prove that for a fixed integer s2 every K _s,s -free graph of average degree at least r contains a K _p minor where . A well-known conjecture on the existence of dense K _s,s -free graphs would imply that the value of the exponent is best possible. Our result implies Hadwigers conjecture for K _s,s -free graphs whose chromatic number is sufficiently large compared with s.