Supersaturation For Ramsey-Turán Problems

For an l-graph , the Turán number is the maximum number of edges in an n-vertex l-graph containing no copy of . The limit is known to exist [8]. The Ramsey–Turán density is defined similarly to except that we restrict to only those with independence number o(n). A result of Erdős and Sós [3] states that as long as for every edge E of there is another edge E′of for which |E∩E′|≥2. Therefore a natural question is whether there exists for which . Another variant proposed in [3] requires the stronger condition that every set of vertices of of size at least εn (0<ε<1) has density bounded below by some threshold. By definition, for every . However, even is not known for very many l-graphs when l>2. We prove the existence of a phenomenon similar to supersaturation for Turán problems for hypergraphs. As a consequence, we construct, for each l≥3, infinitely many l-graphs for which . We also prove that the 3-graph with triples 12a, 12b, 12c, 13a, 13b, 13c, 23a, 23b, 23c, abc, satisfies . The existence of a hypergraph satisfying was conjectured by Erdős and Sós [3], proved by Frankl and R?dl [6], and later by Sidorenko [14]. Our short proof is based on different ideas and is simpler than these earlier proofs. * Research supported in part by the National Science Foundation under grants DMS-9970325 and DMS-0400812, and an Alfred P. Sloan Research Fellowship. † Research supported in part by the National Science Foundation under grants DMS-0071261 and DMS-0300529.     

Explicit Bounded-Degree Unique-Neighbor Concentrators

Here we solve an open problem considered by various researchers by presenting the first explicit constructions of an infinite family of bounded-degree ‘unique-neighbor’ concentrators Γ; i.e., there are strictly positive constants α and ε, such that all Γ = (X,Y,E(Γ)) ∈ satisfy the following properties. The output-set Y has cardinality times that of the input-set X, and for each subset S of X with no more than α|X| vertices, there are at least ε|S| vertices in Y that are adjacent in Γ to exactly one vertex in S. Also, the construction of is simple to specify, and each has fewer than edges. We then modify to obtain explicit unique-neighbor concentrators of maximum degree 3. * Supported by NSF grant CCR98210-58 and ARO grant DAAH04-96-1-0013.     

Discrepancy After Adding A Single Set

We show that the hereditary discrepancy of a hypergraph on n points increases by a factor of at most O(log n) when one adds a new edge to .     

Weighted Non-Trivial Multiply Intersecting Families

Let n and r be positive integers. Suppose that a family satisfies F₁∩···∩F_r ≠∅ for all F₁, . . .,F_r ∈ and . We prove that there exists ε=ε(r) >0 such that holds for 1/2≤w≤1/2+ε if r≥13.     

Proof Of A Conjecture Of Erdős On Triangles In Set-Systems

A triangle is a family of three sets A,B,C such that A∩B, B∩C, C∩A are each nonempty, and . Let be a family of r-element subsets of an n-element set, containing no triangle. Our main result implies that for r ≥ 3 and n ≥ 3r/2, we have This settles a longstanding conjecture of Erdős [7], by improving on earlier results of Bermond, Chvátal, Frankl, and Füredi. We also show that equality holds if and only if consists of all r-element subsets containing a fixed element. Analogous results are obtained for nonuniform families.     

Translation Generalized Quadrangles In Even Characteristic

In this paper, we first introduce new objects called “translation generalized ovals” and “translation generalized ovoids”, and make a thorough study of these objects. We then obtain numerous new characterizations of the of Tits and the classical generalized quadrangle in even characteristic, including the complete classification of 2-transitive generalized ovals for the even case. Next, we prove a new strong characterization theorem for the of Tits. As a corollary, we obtain a purely geometric proof of a theorem of Johnson on semifield flocks. * The second author is a Postdoctoral Fellow of the Fund for Scientific Research—Flanders (Belgium).     

Colorings Of Plane Graphs With No Rainbow Faces

We prove that each n-vertex plane graph with girth g≥4 admits a vertex coloring with at least ⌈n/2⌉+1 colors with no rainbow face, i.e., a face in which all vertices receive distinct colors. This proves a conjecture of Ramamurthi and West. Moreover, we prove for plane graph with girth g≥5 that there is a vertex coloring with at least if g is odd and if g is even. The bounds are tight for all pairs of n and g with g≥4 and n≥5g/2−3. * Supported in part by the Ministry of Science and Technology of Slovenia, Research Project Z1-3129 and by a postdoctoral fellowship of PIMS. ** Institute for Theoretical Computer Science is supported by Ministry of Education of CzechR epublic as project LN00A056.     

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.     

Some Remarks on the Simultaneous Chromatic Number

We present several partial results, variants, and consistency results concerning the following (as yet unsolved) conjecture. If X is a graph on the ground set V with then X has an edge coloring F with colors such that if V is decomposed into parts then there is one in which F assumes all values.Due to some unfortunate misunderstandings, this paper appeared much later than we expected.* Research partially supported by NSF grants DMS-9704477 and DMS-0072560. Research partially supported by Hungarian National Research Grant T 032455.     

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.     

Strongly connective degree sets II: perfect derived subgroups

When G is a finite nonabelian group, we associate the common-divisor graph with G by letting nontrivial degrees in cd(G) = {χ(1) | χ∈Irr(G)} be the vertices and making distinct vertices adjacent if they have a common nontrivial divisor. A set of vertices for this graph is said to be strongly connective for cd(G) if there is some prime which divides every member of , and every vertex outside of is adjacent to some member of . When G is nonsolvable, we provide sufficiency conditions for cd(G) to have a strongly connective subset. We also extend a previously known result about groups with nonabelian solvable quotients, and prove for arbitrary groups G that if the associated graph is connected and has a diameter bounded by 2, then indeed cd(G) has a strongly connective subset. The major focus is on when the derived subgroup G′ is perfect. Received: 23 July 2005     

Set Systems with few Disjoint Pairs

Let X = {1, . . . , n}, and let be a family of subsets of X. Given the size of , at least how many pairs of elements of must be disjoint? In this paper we give a lower bound for the number of disjoint pairs in . The bound we obtain is essentially best possible. In particular, we give a new proof of a result of Frankl and of Ahlswede, that if satisfies then contains at least as many disjoint pairs as X^(r).The situation is rather different if we restrict our attention to : then we are asking for the minimum number of edges spanned by a subset of the Kneser graph of given size. We make a conjecture on this lower bound, and disprove a related conjecture of Poljak and Tuza on the largest bipartite subgraph of the Kneser graph.* Research partially supported by NSF grant DMS-9971788     

Tolokonnikov’s Lemma for Real H ∞ and the Real Disc Algebra

We prove Tolokonnikov’s Lemma and the inner-outer factorization for the real Hardy space , the space of bounded holomorphic (possibly operator-valued) functions on the unit disc all of whose matrix-entries (with respect to fixed orthonormal bases) are functions having real Fourier coefficients, or equivalently, each matrix entry f satisfies for all z ∈ . Tolokonnikov’s Lemma for means that if f is left-invertible, then f can be completed to an isomorphism; that is, there exists an F, invertible in , such that F = [ f f _c ] for some f _c in . In control theory, Tolokonnikov’s Lemma implies that if a function has a right coprime factorization over , then it has a doubly coprime factorization in . We prove the lemma for the real disc algebra as well. In particular, and are Hermite rings. The work of the first author was supported by Magnus Ehrnrooth Foundation. Received: December 5, 2006. Revised: February 4, 2007.     

Exponential Stability of Traveling Pulse Solutions of a Singularly Perturbed System of Integral Differential Equations Arising From Excitatory Neuronal Networks

We establish the exponential stability of fast traveling pulse solutions to nonlinear singularly per-turbed systems of integral differential equations arising from neuronal networks.It has been proved that expo-nential stability of these orbits is equivalent to linear stability.Let (?) be the linear differential operator obtainedby linearizing the nonlinear system about its fast pulse,and let σ((?)) be the spectrum of (?).The linearizedstability criterion says that if max{Reλ:λ∈σ((?)),λ≠0}(?)-D,for some positive constant D,and λ=0 is asimple eigenvalue of (?)(ε),then the stability follows immediately (see [13] and [37]).Therefore,to establish theexponential stability of the fast pulse,it suffices to investigate the spectrum of the operator (?).It is relativelyeasy to find the continuous spectrum,but it is very difficult to find the isolated spectrum.The real part ofthe continuous spectrum has a uniformly negative upper bound,hence it causes no threat to the stability.Itremains to see if the isolated spectrum is safe.Eigenvalue functions (see [14] and [35,36]) have been a powerful tool to study the isolated spectrum of the as-sociated linear differential operators because the zeros of the eigenvalue functions coincide with the eigenvaluesof the operators.There have been some known methods to define eigenvalue functions for nonlinear systems ofreaction diffusion equations and for nonlinear dispersive wave equations.But for integral differential equations,we have to use different ideas to construct eigenvalue functions.We will use the method of variation of param-eters to construct the eigenvalue functions in the complex plane C.By analyzing the eigenvalue functions,wefind that there are no nonzero eigenvalues of (?) in {λ∈C:Reλ(?)-D} for the fast traveling pulse.Moreoverλ=0 is simple.This implies that the exponential stability of the fast orbits is true.     

The Reduced Minimum Modulus in <Emphasis>C</Emphasis><Superscript>*</Superscript>-Algebras

We define the reduced minimum modulus of a nonzero element a in a unital C ^*-algebra by . We prove that . Applying this result to and its closed two side ideal , we get that dist , and for any if RR = 0, where and is the quotient homomorphism and . These results generalize corresponding results in Hilbert spaces.     

More on Bounding Introspection in Modal Nonmonotonic Logics

Abstract By we denote the set of all propositional formulas. Let be the set of all clauses. Define . In Sec. 2 of this paper we prove that for normal modal logics , the notions of -expansions and -expansions coincide. In Sec. 3, we prove that if I consists of default clauses then the notions of -expansions for I and -expansions for I coincide. To this end, we first show, in Sec. 3, that the notion of -expansions for I is the same as that of -expansions for I. The project is supported by NSFC     

Fong characters and chains of normal subgroups

In this note, we show that if is a π-partial character of the π-separable group is a chain of normal subgroups of G, and H is a Hall π-subgroup of G, then has a Fong character α Irr(H) such that for every subgroup , every irreducible constituent of α _H∩N is Fong for N. We also show that if is quasi-primitive, then for every normal subgroup M of G the irreducible constituents of are Fong for M. Received: 21 July 2006 Revised: 17 January 2007     

On Shadows Of Intersecting Families

The shadow minimization problem for t-intersecting systems of finite sets is considered. Let be a family of k-subsets of . The -shadow of is the set of all (k-)-subsets contained in the members of . Let be a t-intersecting family (any two members have at least t elements in common) with . Given k,t,m the problem is to minimize (over all choices of ). In this paper we solve this problem when m is big enough.     

Bounded width problems and algebras

Let be finite relational structure of finite type, and let CSP denote the following decision problem: if is a given structure of the same type as , is there a homomorphism from to ? To each relational structure is associated naturally an algebra whose structure determines the complexity of the associated decision problem. We investigate those finite algebras arising from CSP’s of so-called bounded width, i.e., for which local consistency algorithms effectively decide the problem. We show that if a CSP has bounded width then the variety generated by the associated algebra omits the Hobby-McKenzie types 1 and 2. This provides a method to prove that certain CSP’s do not have bounded width. We give several applications, answering a question of Nešetřil and Zhu [26], by showing that various graph homomorphism problems do not have bounded width. Feder and Vardi [17] have shown that every CSP is polynomial-time equivalent to the retraction problem for a poset we call the Feder − Vardi poset of the structure. We show that, in the case where the structure has a single relation, if the retraction problem for the Feder-Vardi poset has bounded width then the CSP for the structure also has bounded width. This is used to exhibit a finite order-primal algebra whose variety admits type 2 but omits type 1 (provided P ≠ NP). Presented by M. Valeriote. Received January 8, 2005; accepted in final form April 3, 2006. The first author’s research is supported by a grant from NSERC and the Centre de Recherches Mathématiques. The second author’s research is supported by OTKA no. 034175 and 48809 and T 037877. Part of this research was conducted while the second author was visiting Concordia University in Montréal and also when the first author was visiting the Bolyai Institute in Szeged. The support of NSERC, OTKA and the Bolyai Institute is gratefully acknowledged.     

For Which Densities are Random Triangle-Free Graphs Almost Surely Bipartite?

Denote by the class of all triangle-free graphs on n vertices and m edges. Our main result is the following sharp threshold, which answers the question for which densities a typical triangle-free graph is bipartite. Fix > 0 and let . If n/2 m (1 – ) t ₃, then almost all graphs in are not bipartite, whereas if m (1 + )t ₃, then almost all of them are bipartite. For m (1 + )t ₃, this allows us to determine asymptotically the number of graphs in . We also obtain corresponding results for C -free graphs, for any cycle C of fixed odd length. Forschergruppe Algorithmen, Struktur, Zufall supported by Deutsche Forschungsgemeinschaft grant FOR 413/1-1