r-一致超图Ramsey函数的渐近下界(英文)

本文利用Lovasz局部引理的Spencer形式和对称形式给出r-一致超图Ramsey函数的渐近下界.证明了:对于任意取定的正整数f0,使得当n→∞时,有R~((r))(m~l,n~(k-l))≥(c-o(1))(n~(r-1)/logn)~■.特别地,R~((r))_k(n)≥(1-o(1))n/e k~■(n→∞).对于任意取定的正整数s≥r+1和常数δ>0,α≥0,如果F表示阶为s的r-一致超图,■表示阶为t的r-一致超图,且■的边数满足m(■)≥(δ-o(1))t~r/(logt)α(t→∞),则存在c=c(s,δ,α)>0,使得R~((r))(F,■)≥(c-o(1))(t~(r-1)/(logt)~l+(r-l)α)~(m(F)-l/s-r).     

On the Chromaticity of Multi-Bridge Hypergraphs

A multi-bridge hypergraph is an h-uniform linear hypergraph consisting of some linear paths having common extremities. In this paper it is proved that the multisets of path lengths of two chromatically equivalent multi-bridge hypergraphs are equal provided the multiplicities of path lengths are bounded above by 2 ^h-1 − 2. Also, it is shown that h-uniform linear cycles of length m are not chromatically unique for every m, h ≥ 3.     

On Equitable Colorings of Hypergraphs

Mathematical Notes - A two-coloring is said to be equitable if, on the one hand, there are no monochromatic edges (the coloring is regular) and, on the other hand, the cardinalities of color...     

On Substructure Densities of Hypergraphs

A real number α ∈ [0, 1) is a jump for an integer r ≥ 2 if there exists c > 0 such that for any ∈ > 0 and any integer m ≥ r, there exists an integer n ₀ such that any r-uniform graph with n > n ₀ vertices and density ≥ α + ∈ contains a subgraph with m vertices and density ≥ α + c. It follows from a fundamental theorem of Erdös and Stone that every α ∈ [0, 1) is a jump for r = 2. Erdös also showed that every number in [0, r!/r ^r ) is a jump for r ≥ 3 and asked whether every number in [0, 1) is a jump for r ≥ 3 as well. Frankl and Rödl gave a negative answer by showing a sequence of non-jumps for every r ≥ 3. Recently, more non-jumps were found for some r ≥ 3. But there are still a lot of unknowns on determining which numbers are jumps for r ≥ 3. The set of all previous known non-jumps for r = 3 has only an accumulation point at 1. In this paper, we give a sequence of non-jumps having an accumulation point other than 1 for every r ≥ 3. It generalizes the main result in the paper ‘A note on the jumping constant conjecture of Erdös’ by Frankl, Peng, Rödl and Talbot published in the Journal of Combinatorial Theory Ser. B. 97 (2007), 204–216.     

On Jumping Densities of Hypergraphs

A number \({\alpha\in [0, 1)}\) is a jump for an integer r ≥ 2 if there exists a constant c > 0 such that for any family \({{\mathcal F}}\) of r-uniform graphs, if the Turán density of \({{\mathcal F}}\) is greater than α, then the Turán density of \({{\mathcal F}}\) is at least α + c. A fundamental result in extremal graph theory due to Erd?s and Stone implies that every number in [0, 1) is a jump for r = 2. Erd?s also showed that every number in [0, r!/r ^r ) is a jump for r ≥ 3. However, not every number in [0, 1) is a jump for r ≥ 3. In fact, Frankl and Rödl showed the existence of non-jumps for r ≥ 3. By a similar approach, more non-jumps were found for some r ≥ 3 recently. But there are still a lot of unknowns regarding jumps for hypergraphs. In this note, we show that if \({c\cdot{\frac{r!}{r^r}}}\) is a non-jump for r ≥ 3, then for every p ≥ r, \({c\cdot{\frac{p!}{p^p}}}\) is a non-jump for p.     

On the Chromaticity of Quasi Linear Hypergraphs

An h-hypergraph H is said to be quasi linear if every two edges of H intersect in 0 or r vertices (r ≥ 1 and h ≥ 2r + 1). The main result of this paper is the following: if G and H are chromatically equivalent h-hypergraphs, H is quasi linear and h ≥ 3r ? 1, then any two edges of G intersect in 0,1 or r vertices and the result cannot be strengthened. This extends the corresponding result of the first author for linear hypergraphs (case r = 1) [Tomescu in J Combin Theory B2 72: 229–235, 1988]     

On the Laplacian Spectrum and Walk-regular Hypergraphs

We use the generalization of the Laplacian matrix to hypergraphs to obtain several spectral-like results on hypergraphs. For instance, we obtain upper bounds on the eccentricity and the excess of any vertex of hypergraphs. We extend to the case of hypergraphs the concepts of walk regularity and spectral regularity, showing that all walk-regular hypergraphs are spectrally-regular. Finally, we obtain an upper bound on the mean distance of walk-regular hypergraphs that involves all the Laplacian spectrum.     

On the Laplacian Spectrum and Walk-regular Hypergraphs

We use the generalization of the Laplacian matrix to hypergraphs to obtain several spectral-like results on hypergraphs. For instance, we obtain upper bounds on the eccentricity and the excess of any vertex of hypergraphs. We extend to the case of hypergraphs the concepts of walk regularity and spectral regularity, showing that all walk-regular hypergraphs are spectrally-regular. Finally, we obtain an upper bound on the mean distance of walk-regular hypergraphs that involves all the Laplacian spectrum.     

On the Strong Chromatic Number of Random Hypergraphs

Doklady Mathematics - We study the probability threshold for the property of strong colorability with a given number of colors of a random $$k$$ -uniform hypergraph in the binomial model...     

3-一致超图的反馈数研究

超图H=(V,E)顶点集为V,边集为E.S(C)V是H的顶点子集,如果HS不含有圈,则称S是H的点反馈数,记tc(H)是H的最小点反馈数.本文证明了:(i)如果H是线性3-一致超图,边数为m,则tc(H)≤m/3;(ii)如果日是3-一致超图,边数为m,则Tc(H)≤m/2并且等式成立当且仅当日任何一个连通分支是孤立...     

On Graph-Lagrangians of Hypergraphs Containing Dense Subgraphs

Motzkin and Straus established a remarkable connection between the maximum clique and the Graph-Lagrangian of a graph in (Can. J. Math. 17:533–540, 1965). This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique number in graphs. It is useful in practice if similar results hold for hypergraphs. In this paper, we provide upper bounds on the Graph-Lagrangian of a hypergraph containing dense subgraphs when the number of edges of the hypergraph is in certain ranges. These results support a pair of conjectures introduced by Peng and Zhao (Graphs Comb. 29:681–694, 2013) and extend a result of Talbot (Comb. Probab. Comput. 11:199–216, 2002).     

On Acyclic Hypergraphs of Minimal Prime Models

We discuss the question of restoring the structural properties of theories from the hypergraphs of minimal prime models. We describe the spectrum and the main model-theoretic properties of acyclic complete theories with the property of extension of isomorphisms of families of minimal prime models.     

On the Number of Independent Sets in Simple Hypergraphs

Extremal problems on the number of j-independent sets in uniform simple hypergraphs are studied. Nearly optimal results on the maximum number of independent sets for the class of simple regular hypergraphs and on the minimum number of independent sets for the class of simple hypergraphs with given average degree of vertices are obtained.     

On Extremal Hypergraphs for Hamiltonian Cycles

We study sufficient conditions for Hamiltonian cycles in hypergraphs and obtain both Turán- and Dirac-type results. While the Turán-type result gives an exact threshold for the appearance of a Hamiltonian cycle in a hypergraph depending only on the extremal number of a certain path, the Dirac-type result yields just a sufficient condition relying solely on the minimum vertex degree.     

On the Laplacian Eigenvalues and Metric Parameters of Hypergraphs

The aim of this paper is to generalize some concepts and recent results of the algebraic graph theory in order to investigate and describe, by algebraic methods, the properties of some combinatorial structures. Here we introduce a version of "Laplacian matrix" of a hypergraph and we obtain several spectral-like results on its metric parameters, such as the diameter, mean distance, excess, bandwidth and cutsets.     

On the Number of Edges in Colour-Critical Graphs and Hypergraphs

A (hyper)graph G is called k-critical if it has chromatic number k, but every proper sub(hyper)graph of it is (k-1)-colourable. We prove that for sufficiently large k, every k-critical triangle-free graph on n vertices has at least (k-o(k))n edges. Furthermore, we show that every (k+1)-critical hypergraph on n vertices and without graph edges has at least (k-3/³?{k}) n(k-3/\sqrt[3]{k}) n edges. Both bounds differ from the best possible bounds by o(kn) even for graphs or hypergraphs of arbitrary girth.     

On Definability of Hypergraphs by Their Semigroups of Homomorphisms

. No Abstract.     

超图中的着色问题

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

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.