二分图中度条件和k-因子的存在性

本文主要研究了二分图中任意一对距离为２的顶点的度数与ｋ－因子关系,给出了二分图有ｋ因子的若干充分条件,并说明这些条件是最好的可能,从而证明了Ｎｉｓｈｉｍｕｒａ提出的问题对二分图成立。     

Graphical Frobenius representations

A Frobenius group is a transitive permutation group that is not regular and such that only the identity fixes more than one point. A graphical Frobenius representation (GFR) of a Frobenius group G is a graph whose automorphism group, as a group of permutations of the vertex set, is isomorphic to G. The problem of classifying which Frobenius groups admit a GFR is a natural extension of the classification of groups that have a graphical regular representation (GRR), which occupied many authors from 1958 through 1982. In this paper, we review for graph theorists some standard and deep results about finite Frobenius groups, determine classes of finite Frobenius groups and individual groups that do and do not admit GFRs, and classify those Frobenius groups of order at most 300 having a GFR. Because a Frobenius group, as opposed to a regular permutation group, has a highly restricted structure, the GFR problem emerges as algebraically more complex than the GRR problem. This paper concludes with some further questions and a strong conjecture.     

Locally-finite connected-homogeneous digraphs

A digraph is connected-homogeneous if any isomorphism between finite connected induced subdigraphs extends to an automorphism of the digraph. We consider locally-finite connected-homogeneous digraphs with more than one end. In the case that the digraph embeds a triangle we give a complete classification, obtaining a family of tree-like graphs constructed by gluing together directed triangles. In the triangle-free case we show that these digraphs are highly arc-transitive. We give a classification in the two-ended case, showing that all examples arise from a simple construction given by gluing along a directed line copies of some fixed finite directed complete bipartite graph. When the digraph has infinitely many ends we show that the descendants of a vertex form a tree, and the reachability graph (which is one of the basic building blocks of the digraph) is one of: an even cycle, a complete bipartite graph, the complement of a perfect matching, or an infinite semiregular tree. We give examples showing that each of these possibilities is realised as the reachability graph of some connected-homogeneous digraph, and in the process we obtain a new family of highly arc-transitive digraphs without property Z.     

4p阶二面体群的弱3-CI性

决定了4p(p是奇素数)阶二面体群的连通3度Cayley图的完全分类,并证明4p阶二面体群不是弱3-CI群,从而否定了C.H.Li关于"所有有限群都是弱3-CI群"的猜想     

Pseudocomplementation in (Normal) Subgroup Lattices

The goal of this article is to study finite groups admitting a pseudocomplemented subgroup lattice (PK-groups) or a pseudocomplemented normal subgroup lattice (PKN-groups). In particular, we obtain a complete classification of finite PK-groups and of finite nilpotent PKN-groups. We also study groups with a Stone normal subgroup lattice, and we classify finite groups for which every subgroup has a Stone normal subgroup lattice. Finally, we obtain a complete classification of finite groups for which every subgroup is monolithic.     

On bipartite zero-divisor graphs

A (finite or infinite) complete bipartite graph together with some end vertices all adjacent to a common vertex is called a complete bipartite graph with a horn. For any bipartite graph G, we show that G is the graph of a commutative semigroup with 0 if and only if it is one of the following graphs: star graph, two-star graph, complete bipartite graph, complete bipartite graph with a horn. We also prove that a zero-divisor graph is bipartite if and only if it contains no triangles. In addition, we give all corresponding zero-divisor semigroups of a class of complete bipartite graphs with a horn and determine which complete r-partite graphs with a horn have a corresponding semigroup for r≥3.     

An Approximate Version of Sidorenko’s Conjecture

A beautiful conjecture of Erdős-Simonovits and Sidorenko states that, if H is a bipartite graph, then the random graph with edge density p has in expectation asymptotically the minimum number of copies of H over all graphs of the same order and edge density. This conjecture also has an equivalent analytic form and has connections to a broad range of topics, such as matrix theory, Markov chains, graph limits, and quasirandomness. Here we prove the conjecture if H has a vertex complete to the other part, and deduce an approximate version of the conjecture for all H. Furthermore, for a large class of bipartite graphs, we prove a stronger stability result which answers a question of Chung, Graham, and Wilson on quasirandomness for these graphs.     

The graph formulation of the union-closed sets conjecture

The union-closed sets conjecture asserts that in a finite non-trivial union-closed family of sets there has to be an element that belongs to at least half the sets. We show that this is equivalent to the conjecture that in a finite non-trivial graph there are two adjacent vertices each belonging to at most half of the maximal stable sets. In this graph formulation other special cases become natural. The conjecture is trivially true for non-bipartite graphs and we show that it holds also for the classes of chordal bipartite graphs, subcubic bipartite graphs, bipartite series-parallel graphs and bipartitioned circular interval graphs. We derive that the union-closed sets conjecture holds for all union-closed families being the union-closure of sets of size at most three.     

Locally Transitive Graphs Admitting a Group with Cyclic Sylow Subgroups

All graphs are finite simple undirected and of no isolated vertices in this paper. Using the theory of coset graphs and permutation groups, it is completed that a classification of locally transitive graphs admitting a non-Abelian group with cyclic Sylow subgroups. They are either the union of the family of arc-transitive graphs, or the union of the family of bipartite edge-transitive graphs.     

The union-closed sets conjecture almost holds for almost all random bipartite graphs

Frankl’s union-closed sets conjecture states that in every finite union-closed family of sets, not all empty, there is an element in the ground set contained in at least half of the sets. The conjecture has an equivalent formulation in terms of graphs: In every bipartite graph with least one edge, both colour classes contain a vertex belonging to at most half of the maximal stable sets.We prove that, for every fixed edge-probability, almost every random bipartite graph almost satisfies Frankl’s conjecture.     

A new result on difference sets with -1 as multiplier

In this paper we study finite abelian groups admitting a difference set with multiplier -1. In these groups we have that each integer, which is relatively prime to the group order, is a multiplier (see [1] and Section 1 of this paper).About the arithmetical structure, there is an interesting result of Jungnickel [3] on primes dividing the order n of the corresponding design. Here we prove (see Theorem 2.1) that each odd prime divisor of the order v of the group divides n. The proof of Theorem 2.1 rests on character computations and is motivated by [5].     

Non-realizability and ending laminations: Proof of the density conjecture

We give a complete proof of the Bers?CSullivan?CThurston density conjecture. In the light of the ending lamination theorem, it suffices to prove that any collection of possible ending invariants is realized by some algebraic limit of geometrically finite hyperbolic manifolds. The ending invariants are either Riemann surfaces or filling laminations supporting Masur domain measured laminations and satisfying some mild additional conditions. With any set of ending invariants we associate a sequence of geometrically finite hyperbolic manifolds and prove that this sequence has a convergent subsequence. We derive the necessary compactness theorem combining the Rips machine with non-existence results for certain small actions on real trees of free products of surface groups and free groups. We prove then that the obtained algebraic limit has the desired conformal boundaries and the property that none of the filling laminations is realized by a pleated surface. In order to be able to apply the ending lamination theorem, we have to prove that this algebraic limit has the desired topological type and that these non-realized laminations are ending laminations. That this is the case is the main novel technical result of this paper. Loosely speaking, we show that a filling Masur domain lamination which is not realized is an ending lamination.     

All Two-Weight Irreducible Cyclic Codes?

The aim of this paper is the classification of two-weight irreducible cyclic codes. Using Fourier transforms and Gauss sums, we obtain necessary and sufficient numerical conditions for an irreducible cyclic code to have at most two weights. This gives a unified explanation for all two-weight irreducible cyclic codes and allows a conjecturally complete classification. Aside from the two known infinite families of two-weight irreducible cyclic codes, a computer search reveals 11 sporadic examples. We conjecture that these are already all two-weight irreducible cyclic codes and give a partial proof of our conjecture conditionally on GRH.     

Error-correcting codes from permutation groups

We replace the usual setting for error-correcting codes (i.e. vector spaces over finite fields) with that of permutation groups. We give an algorithm which uses a combinatorial structure which we call an uncovering-by-bases, related to covering designs, and construct some examples of these. We also analyse the complexity of the algorithm.We then formulate a conjecture about uncoverings-by-bases, for which we give some supporting evidence and prove for some special cases. In particular, we consider the case of the symmetric group in its action on 2-subsets, where we make use of the theory of graph decompositions. Finally, we discuss the implications this conjecture has for the complexity of the decoding algorithm.     

Chirality and principal graph obstructions

Determining which bipartite graphs can be principal graphs of subfactors is an important and difficult question in subfactor theory. Using only planar algebra techniques, we prove a triple point obstruction which generalizes all known initial triple point obstructions to possible principal graphs. We also prove a similar quadruple point obstruction with the same technique. Using our obstructions, we eliminate some infinite families of possible principal graphs with initial triple and quadruple points which were a major hurdle in extending subfactor classification results above index 5.     

Matching theory and Barnette's conjecture

Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian.A graph, other than the path of length three, is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette's Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity.As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. (1985) [14]. These allow us to check whether a graph we generated is a brace.     

Random hypersurfaces and embedding curves in surfaces over finite fields

We use Poonen's closed point sieve to prove two independent results. First, we show that the obvious obstruction to embedding a curve in an unspecified smooth surface is the only obstruction over a perfect field, by proving the finite field analogue of a Bertini-type result of Altman and Kleiman. Second, we prove a conjecture of Vakil and Wood on the asymptotic probability of hypersurface sections having a prescribed number of singularities.     

Fibred coarse embeddings,a-T-menability and the coarse analogue of the Novikov conjecture

The connection between the coarse geometry of metric spaces and analytic properties of topological groupoids is well known. One of the main results of Skandalis, Tu and Yu is that a space admits a coarse embedding into Hilbert space if and only if a certain associated topological groupoid is a-T-menable. This groupoid characterisation then reduces the proof that the coarse Baum–Connes conjecture holds for a coarsely embeddable space to known results for a-T-menable groupoids. The property of admitting a fibred coarse embedding into Hilbert space was introduced by Chen, Wang and Yu to provide a property that is sufficient for the maximal analogue to the coarse Baum–Connes conjecture and in this paper we connect this property to the traditional coarse Baum–Connes conjecture using a restriction of the coarse groupoid and homological algebra. Additionally we use this results to give a characterisation of the a-T-menability for residually finite discrete groups.