Displaying 101 – 120 of 225

Showing per page

Non-degenerate Hilbert cubes in random sets

Csaba Sándor (2007)

Journal de Théorie des Nombres de Bordeaux

A slight modification of the proof of Szemerédi’s cube lemma gives that if a set S [ 1 , n ] satisfies | S | n 2 , then S must contain a non-degenerate Hilbert cube of dimension log 2 log 2 n - 3 . In this paper we prove that in a random set S determined by Pr { s S } = 1 2 for 1 s n , the maximal dimension of non-degenerate Hilbert cubes is a.e. nearly log 2 log 2 n + log 2 log 2 log 2 n and determine the threshold function for a non-degenerate k -cube.

Nonempty intersection of longest paths in a graph with a small matching number

Fuyuan Chen (2015)

Czechoslovak Mathematical Journal

A maximum matching of a graph G is a matching of G with the largest number of edges. The matching number of a graph G , denoted by α ' ( G ) , is the number of edges in a maximum matching of G . In 1966, Gallai conjectured that all the longest paths of a connected graph have a common vertex. Although this conjecture has been disproved, finding some nice classes of graphs that support this conjecture is still very meaningful and interesting. In this short note, we prove that Gallai’s conjecture is true for...

Currently displaying 101 – 120 of 225