On the second best constant in logarithmic Sobolev inequalities on complete Riemannian manifolds

We study the second best constant problem for logarithmic Sobolev inequalities on complete Riemannian manifolds and investigate its relationship with optimal heat kernel bounds and the existence of extremal functions.     

Infinite spectra in the first order theory of graphs

The psectrum Spec(A) of a sentenceA is, roughly, the set of those a for whichA has a threshold function at or nearp=n ^–a . Examples are given ofA with infinite spectra and with spectra of order type ⁱ for arbitraryi.     

Steiner Numbers in Graphs

Abstract

The Steiner distance d(S) of a set S of vertices in a connected graph G is the minimum size of a connected subgraph of G that contains S. The Steiner number s(G) of a connected graph G of order p is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = p—1. A smallest set S of vertices of a connected graph G of order p for which d(S) = p—1 is called a Steiner spanning set of G. It is shown that every connected graph has a unique Steiner spanning set. If G is a connected graph of order p and k is an integer with 0 ≤ k ≤ p—1, then the kth Steiner number sk(G) of G is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = k. The sequence s_o(G),s₁ (G),…,8_p-1(G) is called the Steiner sequence of G. Steiner sequences for trees are characterized.     

The critical Sobolev inequalities in Besov spaces and regularity criterion to some semi-linear evolution equations

We show the critical Sobolev inequalities in the Besov spaces with the logarithmic form such as Brezis-Gallouet-Wainger and Beale-Kato-Majda. As an application of those inequalities, the regularity problem under the critical condition to the Navier-Stokes equations, the Euler equations in and the gradient flow to the harmonic map to the sphere are discussed. Namely the Serrin-Ohyama type regularity criteria are improved in the terms of the Besov spaces. Received: 21 September 2000; in final form: 16 Feburary 2001 / Published online: 18 January 2002     

On the number ofC 5′S in a triangle-free graph

Research partially supported bv Hungarian National Foundation for Scientific Research Grant no. 1812.     

On the number of edge disjoint cliques in graphs of given size

In this paper, we prove that any graph ofn vertices andt _r–1(n)+m edges, wheret _r–1(n) is the Turán number, contains (1–o(1)m edge disjointK _r'sifm=o(n ²). Furthermore, we determine the maximumm such that every graph ofn vertices andt _r–1(n)+m edges containsm edge disjointK _r's ifn is sufficiently large.Research partially supported by Hungarian National Foundation for Scientific Research Grant no. 1812.     

Nonlocal Harnack inequalities

We state and prove a general Harnack inequality for minimizers of nonlocal, possibly degenerate, integro-differential operators, whose model is the fractional p-Laplacian.     

On the Turán number for the hexagon

A long-standing conjecture of Erd?s and Simonovits is that ex(n,C_2k), the maximum number of edges in an n-vertex graph without a 2k-gon is asymptotically as n tends to infinity. This was known almost 40 years ago in the case of quadrilaterals. In this paper, we construct a counterexample to the conjecture in the case of hexagons. For infinitely many n, we prove that

     

On the minimal number of edges in color-critical graphs

A graphG isk-critical if it has chromatic numberk, but every proper subgraph of it is (k?1)-colorable. This paper is devoted to investigating the following question: for givenk andn, what is the minimal number of edges in ak-critical graph onn vertices, with possibly some additional restrictions imposed? Our main result is that for everyk≥4 andn>k this number is at least $\left( {\frac{{k - 1}}{2} + \frac{{k - 3}}{{2(k^2 - 2k - 1)}}} \right)n$ , thus improving a result of Gallai from 1963. We discuss also the upper bounds on the minimal number of edges ink-critical graphs and provide some constructions of sparsek-critical graphs. A few applications of the results to Ramsey-type problems and problems about random graphs are described.     

The smallest eigenvalue of the signless Laplacian

Recently the signless Laplacian matrix of graphs has been intensively investigated. While there are many results about the largest eigenvalue of the signless Laplacian, the properties of its smallest eigenvalue are less well studied. The present paper surveys the known results and presents some new ones about the smallest eigenvalue of the signless Laplacian.     

On a conjecture about the Randi? index

A conjecture of Delorme, Favaron and Rautenbach [On the Randi? index, Discrete Math. 257 (2002) 29-38] about the Randi? index of a graph, in relation to its order and minimum degree, is refuted by the AutoGraphiX 2 system. Moreover, a modified conjecture is derived from presumably extremal graphs obtained with that system.     

On the Estrada and Laplacian Estrada indices of graphs

The Estrada index of a graph G is defined as , where λ₁,λ₂,…,λ_n are the eigenvalues of G. The Laplacian Estrada index of a graph G is defined as , where μ₁,μ₂,…,μ_n are the Laplacian eigenvalues of G. An edge grafting operation on a graph moves a pendent edge between two pendent paths. We study the change of Estrada index of graph under edge grafting operation between two pendent paths at two adjacent vertices. As the application, we give the result on the change of Laplacian Estrada index of bipartite graph under edge grafting operation between two pendent paths at the same vertex. We also determine the unique tree with minimum Laplacian Estrada index among the set of trees with given maximum degree, and the unique trees with maximum Laplacian Estrada indices among the set of trees with given diameter, number of pendent vertices, matching number, independence number and domination number, respectively.     

On the index of tricyclic graphs with perfect matchings

Let T(2k) be the set of all tricyclic graphs on 2k(k?2) vertices with perfect matchings. In this paper, we discuss some properties of the connected graphs with perfect matchings, and then determine graphs with the largest index in T(2k).     

Cycles in weighted graphs

A weighted graph is one in which each edgee is assigned a nonnegative numberw(e), called the weight ofe. The weightw(G) of a weighted graphG is the sum of the weights of its edges. In this paper, we prove, as conjectured in [2], that every 2-edge-connected weighted graph onn vertices contains a cycle of weight at least 2w(G)/(n–1). Furthermore, we completely characterize the 2-edge-connected weighted graphs onn vertices that contain no cycle of weight more than 2w(G)/(n–1). This generalizes, to weighted graphs, a classical result of Erds and Gallai [4].     

Trees in tournaments

Letf(n) be the smallest integer such that every tournament of orderf(n) contains every oriented tree of ordern. Sumner has just conjectures thatf(n)=2n–2, and F. K. Chung has shown thatf(n)(1+o(1))nlog₂ n. Here we show thatf(n)12n andf(n)(4+o(1))n.     

Compactness results in extremal graph theory

Let L be a given family of so called prohibited graphs. Let ex (n, L) denote the maximum number of edges a simple graph of ordern can have without containing subgraphs from L. A typical extremal graph problem is to determine ex (n, L), or at least, find good bounds on it. Results asserting that for a given L there exists a much smaller L*⫅L for which ex (n, L) ≈ ex (n, L*) will be calledcompactness results. The main purpose of this paper is to prove some compactness results for the case when L consists of cycles. One of our main tools will be finding lower bounds on the number of pathsP ^k+1 in a graph ofn vertices andE edges., witch is, in fact, a “super-saturated” version of a wellknown theorem of Erdős and Gallai. Dedicated to Tibor Gallai on his seventieth birthday     

On the Chromatic Number of Triangle-Free Graphs of Large Minimum Degree

We prove that, for each xed real number c > 1/3, the triangle-free graphs of minimum degree at least cn (where n is the number of vertices) have bounded chromatic number. This problem was raised by Erds and Simonovits in 1973 who pointed out that there is no such result for c < 1/3.     

Orthogonal vectors in then-dimensional cube and codes with missing distances

Fork a positive integer letm(4k) denote the maximum number of ±1-vectors of length 4k so that no two are orthogonal. Equivalently,m(4k) is the maximal number of codewords in a code of length 4k over an alphabet of size two, such that no two codewords have Hamming distance 2k. It is proved thatm(4k)=4 ifk is the power of an odd prime.     

Boundedness of optimal matrices in extremal multigraph and digraph problems

We consider multigraphs in which any two vertices are joined by at mostq edges, and study the Turán-type problem for a given family of forbidden multigraphs. In the caseq=2, answering a question of Brown, Erds and Simonovits, we obtain an explicit upper bound on the size of the matrix generating an asymptotical solution of the problem. In the caseq>2 we show that some analogous statements do not hold, and so disprove a conjecture of Brown, Erds and Simonovits.