On generalized Kneser hypergraph colorings

In 2002, the second author presented a lower bound for the chromatic numbers of hypergraphs , “generalized r-uniform Kneser hypergraphs with intersection multiplicities s.” It generalized previous lower bounds by K?í? (1992/2000) for the case s=(1,…,1) without intersection multiplicities, and by Sarkaria (1990) for . Here we discuss subtleties and difficulties that arise for intersection multiplicities si>1:

(1)

In the presence of intersection multiplicities, there are two different versions of a “Kneser hypergraph,” depending on whether one admits hypergraph edges that are multisets rather than sets. We show that the chromatic numbers are substantially different for the two concepts of hypergraphs. The lower bounds of Sarkaria (1990) and Ziegler (2002) apply only to the multiset version.

(2)

The reductions to the case of prime r in the proofs by Sarkaria and by Ziegler work only if the intersection multiplicities are strictly smaller than the largest prime factor of r. Currently we have no valid proof for the lower bound result in the other cases.

We also show that all uniform hypergraphs without multiset edges can be represented as generalized Kneser hypergraphs.     

Colouring triangle-free intersection graphs of boxes on the plane

We prove that intersection graphs of boxes on the plane with girth 6 and 8 are 3- and 2-degenerate, respectively. This implies that these graphs are 4- and 3-list-colourable, respectively.     

Sphericity, cubicity, and edge clique covers of graphs

The sphericity sph(G) of a graph G is the minimum dimension d for which G is the intersection graph of a family of congruent spheres in R^d. The edge clique cover number θ(G) is the minimum cardinality of a set of cliques (complete subgraphs) that covers all edges of G. We prove that if G has at least one edge, then sph(G)?θ(G). Our upper bound remains valid for intersection graphs defined by balls in the L_p-norm for 1?p?∞.     

Periodicity of hyperplane arrangements with integral coefficients modulo positive integers

We study central hyperplane arrangements with integral coefficients modulo positive integers q. We prove that the cardinality of the complement of the hyperplanes is a quasi-polynomial in two ways, first via the theory of elementary divisors and then via the theory of the Ehrhart quasi-polynomials. This result is useful for determining the characteristic polynomial of the corresponding real arrangement. With the former approach, we also prove that intersection lattices modulo q are periodic except for a finite number of q’s. This work was supported by the MEXT and the JSPS.     

A superclass of Edge-Path-Tree graphs with few cliques

Edge-Path-Tree (EPT) graphs are intersection graphs of EPT matrices that is matrices whose columns are incidence vectors of edge-sets of paths in a given tree. EPT graphs have polynomially many cliques [M.C. Golumbic, R.E. Jamison, The edge intersection graphs of paths in a tree, Journal of Combinational Theory Series B 38 (1985) 8–22; C.L. Monma, V.K. Wey, Intersection graphs of paths in a tree, Journal of Combinational Theory Series B 41 (1986) 141–181]. Therefore, the problem of finding a clique of maximum weight in these graphs is solvable in strongly polynomial time. We extend this result to a proper superclass of EPT graphs.     

靶场光电经纬仪多台交会测量的融合处理及其仿真分析

基于两台经纬仪交会测量原理,分析了两台经纬仪交会测量误差;提出了四台经纬仪两两交会测量结果的加权融合处理方法,该方法充分利用了所有测站的测量信息,而且融合测量值误差小于任两台经纬仪的交会误差;最后进行了仿真分析.从仿真结果可以看出,利用该方法可以大大提高空中目标的辨识精度.另外,本方法同样适用于三台或三台以上经纬仪的交会测量问题.     

The Schubert Triangle Geometry on an Algebraic Surface

For a smooth complex projective surface, and for two families of curves with traditional singularities in it, we enumerate the pairs of curves in each family having two points of contact among them, thus generalizing the double contact formulae known or conjectured by Zeuthen and Schubert in the case of the complex projective plane. The technique we use to this purpose is a particular notion of triangle which can be defined in any smooth surface, thus potentially generalizing to arbitrary surfaces the Schubert technique of triangles.     

Intersection graphs of ideals of rings

In this paper, we consider the intersection graph G(R) of nontrivial left ideals of a ring R. We characterize the rings R for which the graph G(R) is connected and obtain several necessary and sufficient conditions on a ring R such that G(R) is complete. For a commutative ring R with identity, we show that G(R) is complete if and only if G(R[x]) is also so. In particular, we determine the values of n for which is connected, complete, bipartite, planar or has a cycle. Next, we characterize finite graphs which arise as the intersection graphs of and determine the set of all non-isomorphic graphs of for a given number of vertices. We also determine the values of n for which the graph of is Eulerian and Hamiltonian.     

Weil–Petersson volumes and cone surfaces

The moduli spaces of hyperbolic surfaces of genus g with n geodesic boundary components are naturally symplectic manifolds. Mirzakhani proved that their volumes are polynomials in the lengths of the boundaries by computing the volumes recursively. In this paper, we give new recursion relations between the volume polynomials.      

A generalization of Talbot's theorem about King Arthur and his Knights of the Round Table

Let G be a graph consisting of powers of disjoint cycles and let A be an intersecting family of independent r-sets of vertices. Provided that G satisfies a further condition related to the clique numbers of the powers of the cycles, then |A| will be as large as possible if it consists of all independent r-sets containing one vertex from a specified cycle. Here r can take any value, 1?r?α(G), where α(G) is the independence number of G. This generalizes a theorem of Talbot dealing with the case when G consists of a cycle of order n raised to the power k. Talbot showed that .