𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Turán problems for integer-weighted graphs

✍ Scribed by Zoltán Füredi; André Kündgen

Publisher
John Wiley and Sons
Year
2002
Tongue
English
Weight
238 KB
Volume
40
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A multigraph is (k,r)‐dense if every k‐set spans at most r edges. What is the maximum number of edges ex~ℕ~(n,k,r) in a (k,r)‐dense multigraph on n vertices? We determine the maximum possible weight of such graphs for almost all k and r (e.g., for all r>k^3^) by determining a constant m=m(k,r) and showing that ex~ℕ~(n,k,r)=m$\left ( n\atop 2\right )$+O(n), thus giving a generalization of Turán's theorem. We find exact answers in many cases, even when negative integer weights are also allowed. In fact, our main result is to determine the maximum weight of (k,r)‐dense n‐vertex multigraphs with arbitrary integer weights with an O(n) error term. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 195–225, 2002

📜 SIMILAR VOLUMES

A Turán–Kubilius Inequality for Integer
A Turán–Kubilius Inequality for Integer Matrices
✍ Gautami Bhowmik; Olivier Ramaré 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 254 KB

We prove a general Tura n Kubilius inequality and use it to derive that the number {(S) of divisors of an integer r\_r matrix S verifies {(S)=(Log |S|) Log 2+o(1) for all but o(X) matrices of determinant X. This is in sharp contrast with the average order which is Ä |S| ; r &1 (Log |S|) # r for ; r

On Turán Quadrature Formulas for the Che
On Turán Quadrature Formulas for the Chebyshev Weight
✍ Guang Shi Ying 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 107 KB

As we know, the Chebyshev weight w(x)=(1&x 2 ) &1Â2 has the property: For each fixed n, the solutions of the extremal problem dx for every even m are the same. This paper proves that the Chebyshev weight is the only weight having this property (up to a linear transformation).

Turán's theorem and k-connected graphs
Turán's theorem and k-connected graphs
✍ Nicolas Bougard; Gwenaël Joret 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB

## Abstract The minimum size of a __k__‐connected graph with given order and stability number is investigated. If no connectivity is required, the answer is given by Turán's Theorem. For connected graphs, the problem has been solved recently independently by Christophe et al., and by Gitler and Val

Explicit constructions of triple systems
Explicit constructions of triple systems for Ramsey–Turán problems
✍ Dhruv Mubayi; Vera T. Sós 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 68 KB

## Abstract We explicitly construct four infinite families of irreducible triple systems with Ramsey‐Turán density less than the Turán density. Two of our families generalize isolated examples of Sidorenko 14, and the first author and Rödl 12. Our constructions also yield two infinite families of i