A New Class of Graphs That Satisfies the Chen‐Chvátal Conjecture

A well‐known combinatorial theorem says that a set of n non‐collinear points in the plane determines at least n distinct lines. Chen and Chvátal conjectured that this theorem extends to metric spaces, with an appropriated definition of line. In this work, we prove a slightly stronger version of Chen and Chvátal conjecture for a family of graphs containing chordal graphs and distance‐hereditary graphs.     

1‐Factor and Cycle Covers of Cubic Graphs

Let G be a bridgeless cubic graph. Consider a list of k 1‐factors of G. Let be the set of edges contained in precisely i members of the k 1‐factors. Let be the smallest over all lists of k 1‐factors of G. Any list of three 1‐factors induces a core of a cubic graph. We use results on the structure of cores to prove sufficient conditions for Berge‐covers and for the existence of three 1‐factors with empty intersection. Furthermore, if , then is an upper bound for the girth of G. We also prove some new upper bounds for the length of shortest cycle covers of bridgeless cubic graphs. Cubic graphs with have a 4‐cycle cover of length and a 5‐cycle double cover. These graphs also satisfy two conjectures of Zhang 18 . We also give a negative answer to a problem stated in 18 .     

The Merrifield–Simmons Conjecture Holds for Bipartite Graphs

Let be a graph and the number of independent (vertex) sets of G. Then the Merrifield–Simmons conjecture states that the sign of the term only depends on the parity of the distance of the vertices in G. We prove that the conjecture holds for bipartite graphs by considering a generalization of the term, where vertex subsets instead of vertices are deleted.     

On the Beck‐Fiala conjecture for random set systems

Motivated by the Beck‐Fiala conjecture, we study discrepancy bounds for random sparse set systems. Concretely, these are set systems (X,Σ), where each element x ∈ X lies in t randomly selected sets of Σ, where t is an integer parameter. We provide new bounds in two regimes of parameters. We show that when |Σ| ≥ |X| the hereditary discrepancy of (X,Σ) is with high probability ; and when |X| ? |Σ|^t the hereditary discrepancy of (X,Σ) is with high probability O(1). The first bound combines the Lovász Local Lemma with a new argument based on partial matchings; the second follows from an analysis of the lattice spanned by sparse vectors.     

极大外平面图（r,k）——扇的4染色

定义了一类极大外平面图：(r,k）--扇。证明了当G是以r个顶点的圈Qr为标定界环的(r,k）一扇，G'是以Qr为标定界环的任意极大外平面图时，G和G'有公共四染色；同时对△(G)=r-3的极大外平在图也得到相同的结论。从而证明了四色定理的等价命题在给定条件下成立。     

Frames and the Feichtinger conjecture

We show that the conjectured generalization of the Bourgain-Tzafriri restricted-invertibility theorem is equivalent to the conjecture of Feichtinger, stating that every bounded frame can be written as a finite union of Riesz basic sequences. We prove that any bounded frame can at least be written as a finite union of linearly independent sequences. We further show that the two conjectures are implied by the paving conjecture. Finally, we show that Weyl-Heisenberg frames over rational lattices are finite unions of Riesz basic sequences.

     

A bilinear approach to the restriction and Kakeya conjectures

Bilinear restriction estimates have appeared in work of Bourgain, Klainerman, and Machedon. In this paper we develop the theory of these estimates (together with the analogues for Kakeya estimates). As a consequence we improve the spherical restriction theorem of Wolff from to , and also obtain a sharp spherical restriction theorem for .

     

The Arc‐Weighted Version of the Second Neighborhood Conjecture

Seymour conjectured that every oriented simple graph contains a vertex whose second neighborhood is at least as large as its first. Seymour's conjecture has been verified in several special cases, most notably for tournaments by Fisher  6 . One extension of the conjecture that has been used by several researchers is to consider vertex‐weighted digraphs. In this article we introduce a version of the conjecture for arc‐weighted digraphs. We prove the conjecture in the special case of arc‐weighted tournaments, strengthening Fisher's theorem. Our proof does not rely on Fisher's result, and thus can be seen as an alternate proof of said theorem.     

Analogue of the degree conjecture over function fields

Under a certain assumption, similar to Manin's conjecture, we prove an upper bound on the degree of modular parametrizations of elliptic curves by Drinfeld modular curves, which is the function field analogue of the conjectured bound over the rational numbers.

     

The asphericity of random 2‐dimensional complexes

We study random 2‐dimensional complexes in the Linial–Meshulam model and prove that for the probability parameter satisfying a random 2‐complex Y contains several pairwise disjoint tetrahedra such that the 2‐complex Z obtained by removing any face from each of these tetrahedra is aspherical. Moreover, we prove that the obtained complex Z satisfies the Whitehead conjecture, i.e. any subcomplex is aspherical. This implies that Y is homotopy equivalent to a wedge where Z is a 2‐dimensional aspherical simplicial complex. We also show that under the assumptions where c > 3 and , the complex Z is genuinely 2‐dimensional and in particular, it has sizable 2‐dimensional homology; it follows that in the indicated range of the probability parameter p the cohomological dimension of the fundamental group of a random 2‐complex equals 2. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 261–273, 2015     

The Structure of the Reduced Product of Preinjective Modules Over a Hereditary Right Pure Semisimple Ring

Abstract

For a monoid S , a (left) S -act is a nonempty set B together with a mapping S ×B→B sending (s, b) to sb such that S (tb)?=?lpar;st)b and 1b ?=?b for all S , t?∈?S and B ?∈?B. Right S -acts A can also be defined, and a tensor product A ??? _s B (a set)can be defined that has the customary universal property with respect to balanced maps from A?×?B into arbitrary sets. Over the past three decades, an extensive theory of flatness properties has been developed (involving free and projective acts, and flat acts of various sorts, defined in terms of when the tensor product functor has certain preservation properties). A recent and complete discussion of this area is contained in the monograph Monoids, Acts and Categories by M. Kilp et al. (New York: Walter de Gruyter, 2000). To date, there have been only a few attempts to generalize this material to ordered monoids acting on partially ordered sets ( S -posets). The present paper is devoted to such a generalization. A unique decomposition theorem for S -posets is given, based on strongly convex, indecomposable S -subposets, and a structure theorem for projective S -posets is given. A criterion for when two elements of the tensor product of S -posets given, which is then applied to investigate several flatness properties.     

A class of counterexamples to the Gel´fand-Kirillov conjecture

Let be a connected non-special semisimple algebraic group and let be a finite dimensional -representation such that has trivial generic stabilizer. Let . Then the semi-direct product is a counter-example to the Gel´fand-Kirillov conjecture.

     

An Algebraic Formulation of the Graph Reconstruction Conjecture

The graph reconstruction conjecture asserts that every finite simple graph on at least three vertices can be reconstructed up to isomorphism from its deck—the collection of its vertex‐deleted subgraphs. Kocay's Lemma is an important tool in graph reconstruction. Roughly speaking, given the deck of a graph G and any finite sequence of graphs, it gives a linear constraint that every reconstruction of G must satisfy. Let be the number of distinct (mutually nonisomorphic) graphs on n vertices, and let be the number of distinct decks that can be constructed from these graphs. Then the difference measures how many graphs cannot be reconstructed from their decks. In particular, the graph reconstruction conjecture is true for n‐vertex graphs if and only if . We give a framework based on Kocay's lemma to study this discrepancy. We prove that if M is a matrix of covering numbers of graphs by sequences of graphs, then . In particular, all n‐vertex graphs are reconstructible if one such matrix has rank . To complement this result, we prove that it is possible to choose a family of sequences of graphs such that the corresponding matrix M of covering numbers satisfies .     

Overfull conjecture for graphs with high minimum degree

Chetwynd and Hilton showed that any regular graph G of even order n which has relatively high degree has a 1‐factorization. This is equivalent to saying that under these conditions G has chromatic index equal to its maximum degree . Using this result, we show that any (not necessarily regular) graph G of even order n that has sufficiently high minimum degree has chromatic index equal to its maximum degree providing that G does not contain an “overfull” subgraph, that is, a subgraph which trivially forces the chromatic index to be more than the maximum degree. This result thus verifies the Overfull Conjecture for graphs of even order and sufficiently high minimum degree. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 73–80, 2004     

Nowhere‐zero 3‐flow and ‐connectedness in graphs with four edge‐disjoint spanning trees

Given a zero‐sum function with , an orientation D of G with in for every vertex is called a β‐orientation. A graph G is ‐connected if G admits a β‐orientation for every zero‐sum function β. Jaeger et al. conjectured that every 5‐edge‐connected graph is ‐connected. A graph is ‐extendable at vertex v if any preorientation at v can be extended to a β‐orientation of G for any zero‐sum function β. We observe that if every 5‐edge‐connected essentially 6‐edge‐connected graph is ‐extendable at any degree five vertex, then the above‐mentioned conjecture by Jaeger et al. holds as well. Furthermore, applying the partial flow extension method of Thomassen and of Lovász et al., we prove that every graph with at least four edge‐disjoint spanning trees is ‐connected. Consequently, every 5‐edge‐connected essentially 23‐edge‐connected graph is ‐extendable at any degree five vertex.     

Floer–Novikov cohomology and the flux conjecture

We study Floer–Novikov cohomology with local coefficients and prove the flux conjecture for general closed symplectic manifolds. Received: February 2005, Revised: May 2006, Accepted: May 2006 Partially supported by the Grant-in-Aid for Scientific Research No. 14003419, Japan Society for the Promotion of Sciences.     

Proof of a conjecture by Đoković on the Poincaré series of the invariants of a binary form

?okovi? (2006)  [3] gave an algorithm for the computation of the Poincaré series of the algebra of invariants of a binary form, where the correctness proof for the algorithm depended on an unproven conjecture. Here we prove this conjecture.     

Presentations of subgroups of the braid group generated by powers of band generators

According to the Tits conjecture proved by Crisp and Paris (2001) [4], the subgroups of the braid group generated by proper powers of the Artin elements σi are presented by the commutators of generators which are powers of commuting elements. Hence they are naturally presented as right-angled Artin groups.The case of subgroups generated by powers of the band generators aij is more involved. We show that the groups are right-angled Artin groups again, if all generators are proper powers with exponent at least 3. We also give a presentation in cases at the other extreme, when all generators occur with exponent 1 or 2. Such presentations are distinctively more complicated than those of right-angled Artin groups.     

Dade's Invariant Conjecture for the Symplectic Group Sp4(2 n ) and the Special Unitary Group SU4(22n ) in Defining Characteristic

In this article, we verify Dade's projective invariant conjecture for the symplectic group Sp₄(2 ⁿ ) and the special unitary group SU₄(2²ⁿ ) in the defining characteristic, that is, in characteristic 2. Furthermore, we show that the Isaacs–Malle–Navarro version of the McKay conjecture holds for Sp₄(2 ⁿ ) and SU₄(2²ⁿ ) in the defining characteristic, that is, Sp₄(2 ⁿ ) and SU₄(2²ⁿ ) are good for the prime 2 in the sense of Isaacs, Malle, and Navarro.