Search

Let G be a K p -free graph. We say e is a K p -saturating edge of G if e ∉ E (G) and G + e contains a copy of K p. Denote by f p (n , m) the minimum number of K p -saturating edges that an n -vertex K p -free graph with m edges can have. Erdős and Tuza conjectured that f 4 (n , ⌊ n 2 / 4 ⌋ + 1) = (1 + o (1)) n 2 16. Balogh and Liu disproved this by showing f 4 (n , ⌊ n 2 / 4 ⌋ + 1) = (1 + o (1)) 2 n 2 33. They believed that a natural generalization of their construction for K p -free graph should also be optimal and made a conjecture that f p + 1 (n , ex (n , K p) + 1) = (2 (p − 2) 2 p (4 p 2 − 11 p + 8) + o (1)) n 2 for all integers p ≥ 3. The main result of this paper is to confirm the above conjecture of Balogh and Liu. [ABSTRACT FROM AUTHOR]

For a compact set A \subset \mathbb {R}^d and an integer k\ge 1, let us denote by \begin{equation*} A[k] = \left \{a_1+\cdots +a_k: a_1, \ldots, a_k\in A\right \}=\sum _{i=1}^k A \end{equation*} the Minkowski sum of k copies of A. A theorem of Shapley, Folkmann and Starr (1969) states that \frac {1}{k}A[k] converges to the convex hull of A in Hausdorff distance as k tends to infinity. Bobkov, Madiman and Wang [ Concentration, functional inequalities and isoperimetry , Amer. Math. Soc., Providence, RI, 2011] conjectured that the volume of \frac {1}{k}A[k] is nondecreasing in k, or in other words, in terms of the volume deficit between the convex hull of A and \frac {1}{k}A[k], this convergence is monotone. It was proved by Fradelizi, Madiman, Marsiglietti and Zvavitch [C. R. Math. Acad. Sci. Paris 354 (2016), pp. 185–189] that this conjecture holds true if d=1 but fails for any d \geq 12. In this paper we show that the conjecture is true for any star-shaped set A \subset \mathbb {R}^d for d=2 and d=3 and also for arbitrary dimensions d \ge 4 under the condition k \ge (d-1)(d-2). In addition, we investigate the conjecture for connected sets and present a counterexample to a generalization of the conjecture to the Minkowski sum of possibly distinct sets in \mathbb {R}^d, for any d \geq 7. [ABSTRACT FROM AUTHOR]

In 2020, Bennett, Carrillo, Machacek and Sagan gave a polynomial generalization of the Narayana numbers and conjectured that these polynomials have positive integer coefficients for 1 ≤ k ≤ n and for n ≥ 1. In 2020, Sagan and Tirrell used a powerful algebraic method to prove this conjecture (in fact, they extend and prove the conjecture for more than just the type A case). In this paper we give a combinatorial proof of a formula satisfied by the Lucas-Narayana polynomials described by Bennett et al. This gives a combinatorial proof that these polynomials have positive integer coefficients. A corollary of our main result establishes a parallel theorem for the FiboNarayana numbers N n , k , F , providing a combinatorial proof of the conjecture that these are positive integers for n ≥ 1. [ABSTRACT FROM AUTHOR]

Euler's identity equates the number of partitions of any non-negative integer n into odd parts and the number of partitions of n into distinct parts. Beck conjectured and Andrews proved the following companion to Euler's identity: the excess of the number of parts in all partitions of n into odd parts over the number of parts in all partitions of n into distinct parts equals the number of partitions of n with exactly one even part (possibly repeated). Beck's original conjecture was followed by generalizations and so-called "Beck-type" companions to other identities. In this paper, we establish a collection of Beck-type companion identities to the following result mentioned by Lehmer at the 1974 International Congress of Mathematicians: the excess of the number of partitions of n with an even number of even parts over the number of partitions of n with an odd number of even parts equals the number of partitions of n into distinct, odd parts. We also establish various generalizations of Lehmer's identity, and prove related Beck-type companion identities. We use both analytic and combinatorial methods in our proofs. [ABSTRACT FROM AUTHOR]

A matroid is uniform if and only if it has no minor isomorphic to U 1 , 1 ⊕ U 0 , 1 and is paving if and only if it has no minor isomorphic to U 2 , 2 ⊕ U 0 , 1. This paper considers, more generally, when a matroid M has no U k , k ⊕ U 0 , ℓ -minor for a fixed pair of positive integers (k , ℓ). Calling such a matroid (k , ℓ) -uniform , it is shown that this is equivalent to the condition that every rank- (r (M) − k) flat of M has nullity less than ℓ. Generalising a result of Rajpal, we prove that for any pair (k , ℓ) of positive integers and prime power q , only finitely many simple cosimple G F (q) -representable matroids are (k , ℓ) -uniform. Consequently, if Rota's Conjecture holds, then for every prime power q , there exists a pair (k q , ℓ q) of positive integers such that every excluded minor of G F (q) -representability is (k q , ℓ q) -uniform. We also determine all binary (2 , 2) -uniform matroids and show the maximally 3-connected members to be Z 5 ﹨ t , A G (4 , 2) , A G (4 , 2) ⁎ and a particular self-dual matroid P 10. Combined with results of Acketa and Rajpal, this completes the list of binary (k , ℓ) -uniform matroids for which k + ℓ ≤ 4. [ABSTRACT FROM AUTHOR]