Order of the smallest counterexample to Gallai’s conjecture

In 1966, Gallai conjectured that all the longest paths of a connected graph have a common vertex. Zamfirescu conjectured that the smallest counterexample to Gallai’s conjecture is a graph on 12 vertices. We prove that Gallai’s conjecture is true for every connected graph G with α′(G) ≤ 5, which implies that Zamfirescu’s conjecture is true.     

On <Emphasis Type="Italic">k</Emphasis>- critical 2<Emphasis Type="Italic">k</Emphasis>- connected graphs

A graph G is called an (n,k)-graph if κ(G-S)=n-|S| for any S ? V(G) with |S| ≤ k, where ?(G) denotes the connectivity of G. Mader conjectured that for k ≥ 3 the graph K_2k+2?(1-factor) is the unique (2k, k)-graph. Kriesell has settled two special cases for k = 3,4. We prove the conjecture for the general case k ≥ 5.     

Note on a conjecture for the sum of signless Laplacian eigenvalues

For a simple graph G on n vertices and an integer k with 1 ? k ? n, denote by \(\mathcal{S}^+_k\) (G) the sum of k largest signless Laplacian eigenvalues of G. It was conjectured that \(\mathcal{S}^+_k(G)\leqslant{e}(G)+(^{k+1}_{\;\;2})\) (G) ? e(G) + (k+1 2), where e(G) is the number of edges of G. This conjecture has been proved to be true for all graphs when k ∈ {1, 2, n ? 1, n}, and for trees, unicyclic graphs, bicyclic graphs and regular graphs (for all k). In this note, this conjecture is proved to be true for all graphs when k = n ? 2, and for some new classes of graphs.     

On the principal ideal theorem and spectral synthesis on discrete Abelian groups

For positive integers n, m, and h, we let \({\rho\hat (\mathbb{Z}_n, m, h)}\) denote the minimum size of the h-fold restricted sumset among all m-subsets of the cyclic group of order n. The value of \({\rho\hat (\mathbb{Z}_n, m, h)}\) was conjectured for prime values of n and h = 2 by Erd?s and Heilbronn in the 1960s; Dias da Silva and Hamidoune proved the conjecture in 1994 and generalized it for an arbitrary h, but little is known about the case when n is composite. Here we exhibit an explicit upper bound for all n, m, and h; our bound is tight for all known cases (including all n, m, and h with \({n \leqq 40}\)). We also provide counterexamples for conjectures made by Plagne and by Hamidoune, Lladó, and Serra.     

A variation of a conjecture due to Erdös and Sós

Erdoes and Soes conjectured in 1963 that every graph G on n vertices with edge number e（G） 〉 1/2（k - 1）n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n 〉 9/ 2k^2 ＋ 37/2＋ 14 and every graph G on n vertices with e（G） 〉 1/2 （k- 1）n, we prove that there exists a graph G＇ on n vertices having the same degree sequence as G and containing every tree T with k edges as a subgraph.     

Economical separability in free groups

Consider the rank n free group F _n with basis X. Bogopol’ski? conjectured in [1, Problem 15.35] that each element w ∈ F _n of length |w| ≥ 2 with respect to X can be separated by a subgroup H ≤ F _n of index at most C log |w| with some constant C. We prove this conjecture for all w outside the commutant of F _n , as well as the separability by a subgroup of index at most |w|/2 + 2 in general.     

A Munn type representation of abundant semigroups with a multiplicative ample transversal

In this note, we consider the Erd?s–Straus Diophantine equation

$$\begin{aligned} \frac{c}{n}=\frac{1}{x} + \frac{1}{y} + \frac{1}{z}, \end{aligned}$$

where n and c are positive integers with \(\gcd (n, c) = 1\). We provide a formula for the number f(n, c) of all positive integral solutions (x, y, z) of the equation. In 1948, Erd?s and Straus conjectured that \(f(n,4) \ge 1,\) for all integers \(n \ge 2\). Here, we solve the conjecture for a special case of n.

     

Periods and nonvanishing of central <Emphasis Type="Italic">L</Emphasis>-values for GL(2<Emphasis Type="Italic">n</Emphasis>)

Let π be a cuspidal automorphic representation of PGL(2n) over a number field F, and η the quadratic idèle class character attached to a quadratic extension E/F. Guo and Jacquet conjectured a relation between the nonvanishing of L(1/2, π)L(1/2, π ? η) for π of symplectic type and the nonvanishing of certain GL(n,E) periods. When n = 1, this specializes to a well-known result of Waldspurger. We prove this conjecture, and related global results, under some local hypotheses using a simple relative trace formula.We then apply these global results to obtain local results on distinguished supercuspidal representations, which partially establish a conjecture of Prasad and Takloo-Bighash.     

Neighbor sum distinguishing total chromatic number of <Emphasis Type="Italic">K</Emphasis><Subscript>4</Subscript>-minor free graph

A k-total coloring of a graph G is a mapping ?: V (G) ? E(G) → {1; 2,..., k} such that no two adjacent or incident elements in V (G) ? E(G) receive the same color. Let f(v) denote the sum of the color on the vertex v and the colors on all edges incident with v: We say that ? is a k-neighbor sum distinguishing total coloring of G if f(u) 6 ≠ f(v) for each edge uv ∈ E(G): Denote χ _Σ ^″ (G) the smallest value k in such a coloring of G: Pil?niak and Wo?niak conjectured that for any simple graph with maximum degree Δ(G), χ _Σ ^″ ≤ Δ(G)+3. In this paper, by using the famous Combinatorial Nullstellensatz, we prove that for K ₄-minor free graph G with Δ(G) > 5; χ _Σ ^″ = Δ(G) + 1 if G contains no two adjacent Δ-vertices, otherwise, χ _Σ ^″ (G) = Δ(G) + 2.     

Conditional connectivity of bubble sort graphs

A subset F ? V (G) is called an R ^k -vertex-cut of a graph G if G ? F is disconnected and each vertex of G ? F has at least k neighbors in G ? F. The R ^k -vertex-connectivity of G, denoted by κ ^k (G), is the cardinality of a minimum R ^k -vertex-cut of G. Let B _n be the bubble sort graph of dimension n. It is known that κ _k (B _n ) = 2 ^k (n ? k ? 1) for n ≥ 2k and k = 1, 2. In this paper, we prove it for k = 3 and conjecture that it is true for all k ∈ N. We also prove that the connectivity cannot be more than conjectured.     

On a Fitting length conjecture without the coprimeness condition

Let A be a finite nilpotent group acting fixed point freely by automorphisms on the finite solvable group G. It is conjectured that the Fitting length of G is bounded by the number of primes dividing the order of A, counted with multiplicities. The main result of this paper shows that the conjecture is true in the case where A is cyclic of order p ⁿ q, for prime numbers p and q coprime to 6 and G has abelian Sylow 2-subgroups.     

An Ore-Type Theorem on Hamiltonian Square Cycles

The kth power of a cycle C is the graph obtained from C by joining every pair of vertices with distance at most k on C. The second power of a cycle is called a square cycle. Pósa conjectured that every graph with minimum degree at least 2n/3 contains a hamiltonian square cycle. Later, Seymour proposed a more general conjecture that if G is a graph with minimum degree at least (kn)/(k + 1), then G contains the kth power of a hamiltonian cycle. Here we prove an Ore-type version of Pósa’s conjecture that if G is a graph in which deg(u) + deg(v) ≥ 4n/3 ? 1/3 for all non-adjacent vertices u and v, then for sufficiently large n, G contains a hamiltonian square cycle unless its minimum degree is exactly n/3 + 2 or n/3 + 5/3. A consequence of this result is an Ore-type analogue of a theorem of Aigner and Brandt.     

On the length of a finite group and of its 2-generator subgroups

The nonsoluble length λ(G) of a finite group G is defined as the minimum number of nonsoluble factors in a normal series of G each of whose quotients either is soluble or is a direct product of nonabelian simple groups. The generalized Fitting height of a finite group G is the least number h = h* (G) such that F* _h (G) = G, where F* ₁ (G) = F* (G) is the generalized Fitting subgroup, and F* _i+1(G) is the inverse image of F* (G/F*_i (G)). In the present paper we prove that if λ(J) ≤ k for every 2-generator subgroup J of G, then λ(G) ≤ k. It is conjectured that if h* (J) ≤ k for every 2-generator subgroup J, then h* (G) ≤ k. We prove that if h* (〈x, x^g 〉) ≤ k for allx, g ∈ G such that 〈x, x^g 〉 is soluble, then h* (G) is k-bounded.     

Markov type constants,flat tori and Wasserstein spaces

Let \(M_p(X,T)\) denote the Markov type p constant at time T of a metric space X, where \(p \ge 1\). We show that \(M_p(Y,T) \le M_p(X,T)\) in each of the following cases: (a) X and Y are geodesic spaces and Y is covered by X via a finite-sheeted locally isometric covering, (b) Y is the quotient of X by a finite group of isometries, (c) Y is the \(L^p\)-Wasserstein space over X. As an application of (a) we show that all compact flat manifolds have Markov type 2 with constant 1. In particular the circle with its intrinsic metric has Markov type 2 with constant 1. This answers the question raised by S.-I. Ohta and M. Pichot. Parts (b) and (c) imply new upper bounds for Markov type constants of the \(L^p\)-Wasserstein space over \({\mathbb {R}}^d\). These bounds were conjectured by A. Andoni, A. Naor and O. Neiman. They imply certain restrictions on bi-Lipschitz embeddability of snowflakes into such Wasserstein spaces.     

A cycle cover of a 2-edge-connected graph embedded with large face-width on an orientable surface

In 1985, Alon and Tarsi conjectured that the length of a shortest cycle cover of a bridgeless graph H is at most 7/5 |E(H|). The conjecture is still open. Let G be a 2-edge-connected graph embedded with face-width k on the non-spherical orientable surface S_g. We give an upper bound on the length of a cycle cover of G. In particular, if g = 1 and k ≥ 48, or g = 2 and k ≥ 427, or g ≥ 3 and k ≥ 288(4^g - 1), then the upper bound is 7/5 |E(G|), which means that Alon and Tarsi’s conjecture holds for such a graph.     

On the pronormality of subgroups of odd index in finite simple symplectic groups

A subgroup H of a group G is pronormal if the subgroups H and H ^g are conjugate in 〈H,H ^g 〉 for every g ∈ G. It was conjectured in [1] that a subgroup of a finite simple group having odd index is always pronormal. Recently the authors [2] verified this conjecture for all finite simple groups other than PSL _n (q), PSU _n (q), E ₆(q), ² E ₆(q), where in all cases q is odd and n is not a power of 2, and P Sp_2n (q), where q ≡ ±3 (mod 8). However in [3] the authors proved that when q ≡ ±3 (mod 8) and n ≡ 0 (mod 3), the simple symplectic group P Sp²ⁿ (q) has a nonpronormal subgroup of odd index, thereby refuted the conjecture on pronormality of subgroups of odd index in finite simple groups.The natural extension of this conjecture is the problem of classifying finite nonabelian simple groups in which every subgroup of odd index is pronormal. In this paper we continue to study this problem for the simple symplectic groups P Sp_2n (q) with q ≡ ±3 (mod 8) (if the last condition is not satisfied, then subgroups of odd index are pronormal). We prove that whenever n is not of the form 2 ^m or 2 ^m (2^2k +1), this group has a nonpronormal subgroup of odd index. If n = 2 ^m , then we show that all subgroups of P Sp_2n (q) of odd index are pronormal. The question of pronormality of subgroups of odd index in P Sp_2n (q) is still open when n = 2 ^m (2^2k + 1) and q ≡ ±3 (mod 8).     

Distributing pairs of vertices on Hamiltonian cycles

Let G be a graph of order n with minimum degree δ(G)≥n/2+1. Faudree and Li(2012) conjectured that for any pair of vertices x and y in G and any integer 2≤k≤n/2, there exists a Hamiltonian cycle C such that the distance between x and y on C is k. In this paper, we prove that this conjecture is true for graphs of sufficiently large order. The main tools of our proof are the regularity lemma of Szemer′edi and the blow-up lemma of Koml′os et al.(1997).     

On Frankl and Füredi’s conjecture for 3-uniform hypergraphs

Frankl and Füredi in [1] conjectured that the r-graph with m edges formed by taking the first m sets in the colex ordering of N^(r) has the largest Lagrangian of all r-graphs with m edges. Denote this r-graph by C _r,m and the Lagrangian of a hypergraph by λ(G). In this paper, we first show that if \(\leqslant m \leqslant \left( {\begin{array}{*{20}{c}}t \\ 3 \end{array}} \right)\), G is a left-compressed 3-graph with m edges and on vertex set [t], the triple with minimum colex ordering in G ^c is (t ? 2 ? i)(t ? 2)t, then λ(G) ≤ λ(C _3,m ). As an implication, the conjecture of Frankl and Füredi is true for \(\left( {\begin{array}{*{20}{c}}t \\ 3\end{array}} \right) - 6 \leqslant m \leqslant \left( {\begin{array}{*{20}{c}}t \\ 3\end{array}} \right)\).     

A family of non-isomorphism results

We calculate the local groups of germs associated with the higher dimensional R. Thompson groups nV. For a given \({n\in N\cup\left\{\omega\right\}}\) , these groups of germs are free abelian groups of rank r, for r ≤ n (there are some groups of germs associated with nV with rank precisely k for each index 1 ≤ k ≤ n). By Rubin’s theorem, any conjectured isomorphism between higher dimensional R. Thompson groups induces an isomorphism between associated groups of germs. Thus, if m ≠ n the groups mV and nV cannot be isomorphic. This answers a question of Brin.     

A note on Jeśmanowicz’ conjecture

Je?manowicz [9] conjectured that, for positive integers m and n with m > n, gcd(m,n) = 1 and \({m\not\equiv n\pmod{2}}\), the exponential Diophantine equation \({(m^2-n^2)^x+(2mn)^y=(m^2+n^2)^z}\) has only the positive integer solution (x, y, z) = (2, 2, 2). We prove the conjecture for \({2 \| mn}\) and m + n has a prime factor p with \({p\not\equiv1\pmod{16}}\).