Quadruple systems with independent neighborhoods

A 4-graph is odd if its vertex set can be partitioned into two sets so that every edge intersects both parts in an odd number of points. Let

     

The independent neighborhoods process

A triangle T^(r) in an r-uniform hypergraph is a set of r+1 edges such that r of them share a common (r-1)-set of vertices and the last edge contains the remaining vertex from each of the first r edges. Our main result is that the random greedy triangle-free process on n points terminates in an r-uniform hypergraph with independence number O((n log n)^1/r). As a consequence, using recent results on independent sets in hypergraphs, the Ramsey number r(T^(r),K_s^(r)) has order of magnitude s^r/ log s. This answers questions posed in [4, 10] and generalizes the celebrated results of Ajtai–Komlós–Szemerédi [1] and Kim [9] to hypergraphs.     

Almost all triple systems with independent neighborhoods are semi-bipartite

The neighborhood of a pair of vertices u, v in a triple system is the set of vertices w such that uvw is an edge. A triple system H is semi-bipartite if its vertex set contains a vertex subset X such that every edge of H intersects X in exactly two points. It is easy to see that if H is semi-bipartite, then the neighborhood of every pair of vertices in H is an independent set. We show a partial converse of this statement by proving that almost all triple systems with vertex sets [n] and independent neighborhoods are semi-bipartite. Our result can be viewed as an extension of the Erd?s-Kleitman-Rothschild theorem to triple systems.The proof uses the Frankl-Rödl hypergraph regularity lemma, and stability theorems. Similar results have recently been proved for hypergraphs with various other local constraints.     

Maximal matchings in graphs with large neighborhoods of independent vertices

We obtain lower bounds on the size of a maximum matching in a graph satisfying the condition |N(X)| ≥ s for every independent set X of m vertices, thus generalizing results of Faudree, Gould, Jacobson, and Schelp for the case m = 2.     

Hypergraphs with Zero Chromatic Threshold

Let F be an r-uniform hypergraph. The chromatic threshold of the family of F-free, r-uniform hypergraphs is the infimum of all non-negative reals c such that the subfamily of F-free, r-uniform hypergraphs H with minimum degree at least \(c \left( {\begin{array}{c}|V(H)|\\ r-1\end{array}}\right) \) has bounded chromatic number. The study of chromatic thresholds of various graphs has a long history, beginning with the early work of Erd?s and Simonovits. One interesting problem, first proposed by ?uczak and Thomassé and then solved by Allen, Böttcher, Griffiths, Kohayakawa and Morris, is the characterization of graphs having zero chromatic threshold, in particular the fact that there are graphs with non-zero Turán density that have zero chromatic threshold. Here, we make progress on this problem for r-uniform hypergraphs, showing that a large class of hypergraphs have zero chromatic threshold in addition to exhibiting a family of constructions showing another large class of hypergraphs have non-zero chromatic threshold. Our construction is based on a particular product of the Bollobás–Erd?s graphs defined earlier by the authors.     

Hypergraphs with no special cycles

A special cycle in a hypergraph is a cyclex ₁ E ₁ x ₂ E ₂ x ₃ ...x _n E _n x ₁ ofn distinct verticesx _i andn distinct edgesE _j (n≧3) whereE _i ∩{x ₁,x ₂, ...,x _n }={x _i ,x _i+1} (x _n+1=x ₁). In the equivalent (0, 1)-matrix formulation, a special cycle corresponds to a square submatrix which is the incidence matrix of a cycle of size at least 3. Hypergraphs with no special cycles have been called totally balanced by Lovász. Simple hypergraphs with no special cycles onm vertices can be shown to have at most ( ₂ ^m )+m+1 edges where the empty edge is allowed. Such hypergraphs with the maximum number of edges have a fascinating structure and are called solutions. The main result of this paper is an algorithm that shows that a simple hypergraph on at mostm vertices with no special cycles can be completed (by adding edges) to a solution. Support provided by NSERC.     

Hypergraphs and hypergroups

We associate to every hypergraph a commutative quasi-hypergroupH _qG and find a necessary and sufficient condition on so thatH is associative. For certain, any finite included, we determine a sequence= ₀, ₁,, _n of hypergraphs such that ifH ₀ ,H ₁ ,H, H _n is the sequence of the associated quasi-hypergroups,H _n is a join space.Presented by I. Rosenberg.     

超图中的着色问题

本文是近三十年来有关超图中涉及的着色问题的综述。它包含了有关超图着色中的基本结果,临界可着色性,２－可着色性,非２－可着色性以及在超图中与顶点着色、边着色和其它着色相关的极值问题。     

Self-Complementary Non-Uniform Hypergraphs

Let V be a finite set. For a nonempty subset K of positive integers, a K-hypergraph on V is a hypergraph with vertex set V and edge set ${E=\bigcup_{k\in K}E_k}$ , where E _k is a nonempty set of k-subsets of V. We define the complement of a K-hypergraph (V, E) to be the K-hypergraph on V whose edge set consists of the subsets of V with cardinality in K which do not lie in E. A K-hypergraph is called self-complementary if it is isomorphic to its complement. The two extreme classes of self-complementary K-hypergraphs have been studied previously. When |K|?=?1 these are the self-complementary uniform hypergraphs, and when |K|?=?|V| ? 1, these are the so called ‘self-complementary hypergraphs’ studied by Zwonek. In this paper we determine necessary conditions on the order of self-complementary K-hypergraphs, and on the order of regular or vertex-transitive self-complementary K-hypergraphs, for various sets of positive integers K. We also present several constructions for K-hypergraphs to show that these necessary conditions are sufficient for certain sets K. In the language of design theory, the t-subset-regular self-complementary K-hypergraphs correspond to large sets of two isomorphic t-wise balanced designs, or t-partitions, in which the block sizes lie in the set K. Hence the results of this paper imply results in design theory.     

2-Colorings of Hypergraphs with Large Girth

Mathematical Notes - A hypergraph $$H=(V,E)$$ has property $$B_k$$ if there exists a 2-coloring of the set $$V$$ such that each edge contains at least $$k$$ vertices of each color. We let...     

Minimum cost b-matching problems with neighborhoods

Computational Optimization and Applications - Particle Swarm Optimization (PSO) is a population-based metaheuristic belonging to the class of Swarm Intelligence (SI) algorithms. Nowadays, its...     

Graphs with given neighborhoods of vertices

This article establishes criteria for existence of finite graphs L in which the neighborhoods of all vertices are isomorphic to a given graph M for the cases in which M is a simple arc and a simple cycle.Translated from Matematicheskie Zametki, Vol. 3, No. 2, pp. 211–216, February, 1968.