Search

Ramsey’s theory (RAM) from combinatorics and network theory goes looking for regularities and repeated patterns inside structures equipped with nodes and edges. RAM represents the outcome of a dual methodological commitment: by one side a top-down approach evaluates the possible arrangement of specific subgraphs when the number of graph’s vertices is already known, by another side a bottom-up approach calculates the possible number of graph’s vertices when the arrangement of specific subgraphs is already known. Since natural neural networks are often represented in terms of graphs, we suggest to utilize RAM for the analytical and computational assessment of a peculiar structure supplied with neuronal vertices and axonal edges, i.e., the human brain connectome. We discuss how a RAM approach in neuroscientific issues might be able to locate and trace unexplored motifs shared between different cortical and subcortical subareas. Furthermore, we will describe how notable RAM outcomes, such as the Ramsey’s theorem and the Ramsey’s number, could contribute to uncover still unknown anatomical connexions endowed in neuronal networks and unexpected functional interactions among grey zones of the human brain.

Let [math] be integers. Define a bipartite graph between all [math] -element and all [math] -element subsets of an [math] -element set by drawing an edge if and only if the first one contains the second. The domination number of this graph is determined up to a factor of [math] . The short proof relies on some extremal results concerning hypergraphs.

Let G be a connected graph of order n with vertex set V(G). For positive integers a and b, a subset $$S\subseteq V(G)$$ is an (a, b)-dominating set if every vertex $$v\in S$$ is adjacent to at least a vertices inside S and every vertex $$v\in V{\setminus } S$$ is adjacent to at least b vertices inside S. The minimum cardinality of an (a, b)-dominating set for G is called the (a, b)-domination number of G and is denoted by $$\gamma _{a,b}(G)$$ . There are various results on upper bounds for $$\gamma _{a,b}(G)$$ when G is a regular graph or a and b are small numbers. In the first part of this paper, for a given graph G with the minimum degree of at least $$\max \{a,b\}$$ , we define a new graph $$G'$$ associated to G and show that the independence number of this graph is related to $$\gamma _{a,b}(G)$$ . In the next part, using Lovasz local lemma, we give a randomized approach to improve previous results on the upper bounds for $$\gamma _{a,b}(G)$$ in some special cases.

Confirming a conjecture of Vera T. S\'os in a very strong sense, we give a complete solution to Tur\'an's hypergraph problem for the Fano plane. That is we prove for $n\ge 8$ that among all $3$-uniform hypergraphs on $n$ vertices not containing the Fano plane there is indeed exactly one whose number of edges is maximal, namely the balanced, complete, bipartite hypergraph. Moreover, for $n=7$ there is exactly one other extremal configuration with the same number of edges: the hypergraph arising from a clique of order $7$ by removing all five edges containing a fixed pair of vertices. For sufficiently large values $n$ this was proved earlier by F\"uredi and Simonovits, and by Keevash and Sudakov, who utilised the stability method., Comment: revised according to referee reports

Let F be a graph that contains an edge whose deletion reduces its chromatic number. For such a graph F, a classical result of Simonovits from 1966 shows that every graph on n>n0(F) vertices with more than χ(F)−2χ(F)−1·n22 edges contains a copy of F. In this article we derive a similar theorem for multipartite graphs. For a graph H and an integer l≥v(H), let dl(H) be the minimum real number such that every l-partite graph whose edge density between any two parts is greater than dl(H) contains a copy of H. Our main contribution in this article is to show that dl(H)=χ(H)−2χ(H)−1 for all l≥l0(H) sufficiently large if and only if H admits a vertex-coloring with χ(H)−1 colors such that all color classes but one are independent sets, and the exceptional class induces just a matching. When H is a complete graph, this recovers a result of Pfender (Combinatorica 32 (2012), 483–495). We also consider several extensions of Pfender's result.

Turan’s theorem is a cornerstone of the extremal graph theory. In this paper, we determine the minimum number of edges of a connected graph without containing an independent vertex set of a given size and give a new proof of Turan’s theorem.

Clique counts reveal important properties about the structure of massive graphs, especially social networks. The simple setting of just 3-cliques (triangles) has received much attention from the research community. For larger cliques (even, say 6-cliques) the problem quickly becomes intractable because of combinatorial explosion. Most methods used for triangle counting do not scale for large cliques, and existing algorithms require massive parallelism to be feasible. We present a new randomized algorithm that provably approximates the number of k-cliques, for any constant k. The key insight is the use of (strengthenings of) the classic Turan's theorem: this claims that if the edge density of a graph is sufficiently high, the k-clique density must be non-trivial. We define a combinatorial structure called a Turan shadow, the construction of which leads to fast algorithms for clique counting. We design a practical heuristic, called TURAN-SHADOW, based on this theoretical algorithm, and test it on a large class of test graphs. In all cases, TURAN-SHADOW has less than 2% error, in a fraction of the time used by well-tuned exact algorithms. We do detailed comparisons with a range of other sampling algorithms, and find that TURAN-SHADOW is generally much faster and more accurate. For example, TURAN-SHADOW estimates all cliques numbers up to size 10 in social network with over a hundred million edges. This is done in less than three hours on a single commodity machine.

This paper is motivated by the question of how global and dense restriction sets in results from extremal combinatorics can be replaced by less global and sparser ones. The result we consider here as an example is Turan's theorem, which deals with graphs G=([n],E) such that no member of the restriction set consisting of all r-tuples on [n] induces a copy of K_r. Firstly, we examine what happens when this restriction set is replaced just by all r-tuples touching a given m-element set. That is, we determine the maximal number of edges in an n-vertex such that no K_r hits a given vertex set. Secondly, we consider sparse random restriction sets. An r-uniform hypergraph R on vertex set [n] is called Turannical (respectively epsilon-Turannical), if for any graph G on [n] with more edges than the Turan number ex(n,K_r) (respectively (1+\eps)ex(n,K_r), no hyperedge of R induces a copy of K_r in G. We determine the thresholds for random r-uniform hypergraphs to be Turannical and to epsilon-Turannical. Thirdly, we transfer this result to sparse random graphs, using techniques recently developed by Schacht [Extremal results for random discrete structures] to prove the Kohayakawa-Luczak-Rodl Conjecture on Turan's theorem in random graphs., Comment: 33 pages, minor improvements thanks to two referees

Much of extremal graph theory has concentrated either on finding very small subgraphs of a large graph (Turan-type results) or on finding spanning subgraphs (Dirac-type results). In this paper we are interested in finding intermediate-sized subgraphs. We investigate minimum degree conditions under which a graph G contains squared paths and squared cycles of arbitrary specified lengths. We determine precise thresholds, assuming that the order of G is large. This extends results of Fan and Kierstead [J. Combin. Theory Ser. B 63 (1995), 55--64] and of Komlos, Sarkozy, and Szemeredi [Random Structures Algorithms 9 (1996), 193--211] concerning the containment of a spanning squared path and a spanning squared cycle, respectively. Our results show that such minimum degree conditions constitute not merely an interpolation between the corresponding Turan-type and Dirac-type results, but exhibit other interesting phenomena., Comment: 44 pages, 2 figures; small errors corrected

In this note we complete an investigation started by Erdos in 1963 that aims to find the strongest possible conclusion from the hypothesis of Turan's theorem in extremal graph theory. Let K"r^+(s"1,...,s"r) be the complete r-partite graph with parts of sizes s"1>=2,s"2,...,s"r with an edge added to the first part. Letting t"r(n) be the number of edges of the r-partite Turan graph of order n, we prove that: For all r>=2 and all sufficiently small c>0, every graph of sufficiently large order n with t"r(n)+1 edges contains a K"r^+(@[email protected]?,...,@[email protected]?,@?n^1^-^[email protected]?). We also give a corresponding stability theorem and two supporting results of wider scope.

Fix l ⩾ r ⩾ 2 . Let H l + 1 ( r ) be the r -uniform hypergraph obtained from the complete graph K l + 1 by enlarging each edge with a set of r - 2 new vertices. Thus H l + 1 ( r ) has ( r - 2 ) l + 1 2 + l + 1 vertices and l + 1 2 edges. We prove that the maximum number of edges in an n -vertex r -uniform hypergraph containing no copy of H l + 1 ( r ) is ( l ) r l r n r + o ( n r ) as n → ∞ . This is the first infinite family of irreducible r -uniform hypergraphs for each odd r > 2 whose Turan density is determined. Along the way, we give three proofs of a hypergraph generalization of Turan's theorem. We also prove a stability theorem for hypergraphs, analogous to the Simonovits stability theorem for complete graphs.

Brualdi and Mellendorf raised the following problem as a modification of Turan's theorem. Let t and n be positive integers with n>=t>=2. Determine the maximum number of edges of a graph of order n that contains neither K"t nor K"t","t as a subgraph. They solved it for n=2t (see R.A. Brualdi, S. Mellendorf, Two extremal problems in graph theory, The Electron. J. Combin. 1 (1994) #R2). We consider the following similar modification of Turan's theorem. Let t and n be positive integers with n>=t>=2. Determine the maximum number of edges of a graph of order n that contains neither K"t nor K"t","t","t as a subgraph. We solve it for n=3t.

We prove the analogue of Turan's Theorem in random graphs with edge probability p(n) > n-1/(k-1.5). With probability 1 - o(1), one needs to delete approximately 1/k-1-fraction of the edges in a random graph in order to destroy all cliques of size k.

Given a graph G with n vertices and stability number α(G), Turan's Theorem gives a lower bound on the number of edges in G. Furthermore, Turan has proved that the lower bound is only attained if G is the union of α(G) disjoint balanced cliques. We prove a similar result for the 2-stability number α2(G) of G, which is defined as the largest number of vertices in a 2-colorable subgraph of G. Given a graph G with n vertices and 2-stability number α2(G), we give a lower bound on the number of edges in G and characterize the graphs for which this bound is attained. These graphs are the union of isolated vertices and disjoint balanced cliques. We then derive lower bounds on the 2-stability number, and finally discuss the extension of Turan's Theorem to the q-stability number, for q>2.

We say ( n , e ) → ( m , f ), an ( m, f ) subgraph is forced, if every n -vertex graph of size e has an m -vertex spanned subgraph with f edges. For example, as Turan proved, ( n , e )→( k ,( k 2 )) for e > t k − 1 ( n ) and (n,e) ↛( k 2 )) , otherwise. We give a number of constructions showing that forced pairs are rare. Using tools of extremal graph theory we also show infinitely many positive cases. Several problems remain open.

Extending results of Bollobas and Thomason (1981,J. Combin. Theory Ser. B31, 111?114) and Bondy (1983,J. Combin. Theory Ser. B34, 109?111), we characterize graphs of ordernand size at leasttr(n) that do not have a vertexxof maximal degreedxwhose neighbours span at leasttr?1(dx)+1 edges. Furthermore, we show that, for every graphGof ordernand size at leasttr(n), the degree-greedy algorithm used by Bondy (1983,J. Combin. Theory Ser. B34, 109?111) and Bollobas and Thomason (1985,Ann. Discr. Math.28, 47?97) constructs a complete graphKr+1, unlessGis the Turan graphTr(n).

For 00, there exists a real constantC=C(l, η), such that almost every random graphG n, p withp=p(n)≥Cn −1+1/2l satisfiesG n,p→1/2+η C 2l+1. In particular, for any fixedl≥1 and η>0, this result implies the existence of very sparse graphsG withG →1/2+η C 2l+1.

We give the Turán number ex (n, 2P5) for all positive integers n, improving one of the results of Bushaw and Kettle [Turán numbers of multiple paths and equibipartite forests, Combininatorics, Probability and Computing, 20 (2011) 837-853]. In particular we prove that ex (n, 2P5) = 3n−5 for n ≥ 18.

Two years ago, Conlon and Gowers, and Schacht proved general theorems that allow one to transfer a large class of extremal combinatorial results from the deterministic to the probabilistic setting. Even though the two papers solve the same set of long-standing open problems in probabilistic combinatorics, the methods used in them vary significantly and therefore yield results that are not comparable in certain aspects. The theorem of Schacht can be applied in a more general setting and yields stronger probability estimates, whereas the one of Conlon and Gowers also implies random versions of some structural statements such as the famous stability theorem of Erdos and Simonovits. In this paper, we bridge the gap between these two transference theorems. Building on the approach of Schacht, we prove a general theorem that allows one to transfer deterministic stability results to the probabilistic setting that is somewhat more general and stronger than the one obtained by Conlon and Gowers. We then use this theorem to derive several new results, among them a random version of the Erdos-Simonovits stability theorem for arbitrary graphs. The main new idea, a refined approach to multiple exposure when considering subsets of binomial random sets, may be of independent interest., Comment: 19 pages; slightly simplified proof of the main theorem; fixed a few typos

Every graph with n vertices and m edges has an independent set containing at least $n^2 / (2m + n)$ vertices. This paper presents a parallel algorithm that finds an independent set of this size and...

Szemeredi’s regularity lemma asserts that every graph can be decomposed into relatively few random-like subgraphs. This random-like behavior enables one to find and enumerate subgraphs of a given isomorphism type, yielding the so-called counting lemma for graphs. The combined application of these two lemmas is known as the regularity method for graphs and has proved useful in graph theory, combinatorial geometry, combinatorial number theory and theoretical computer science.

Diploma Thesis, ETH Zürich

Let Bn be an aperiodic Brandt semigroup M0[G;n, n;P ] where G is the trivial group, n ∈ N and P = (aij)n×n with aij = 1G if i = j and aij = 0 otherwise. The maximum size of an independent set in Bn is known to be bn2/4c+n, where bn2/4c denotes the largest integer not greater than n2/4. We reprove this result using Turan’s famous graph theorem. Moreover, we give a characterization of all independent sets in Bn with size bn2/4c+ n.

(1999). A Short Proof of Turan's Theorem. The American Mathematical Monthly: Vol. 106, No. 3, pp. 257-258.

The generalization of the Gilbert-Varshamov bound due to Gu and Fuja (1993) is a direct consequence of Turan's theorem on the existence of a clique in a graph with many edges. Turan's theorem allows a slight improvement of Gu and Fuja's result. This improved generalized Gilbert-Varshamov bound is in fact equivalent to Turan's theorem.

0. Notation n=n(G)=number of vertices of the graph G e=e(G)=number of edges of G h=h(G)=number of triangles in G deg (P)=valency (degree) of the vertex P deg,(P)= triangle-valency of P=number of triangles in G adjacent to P t=t(G)=n f deg(P) = 2eln = average valency in G (we will tacitly assume t' 1) T= T(G) =maximum valency in G a=a(G)=maximum size of independent set of vertices (independence or stability number) Kp=shorthana' -for p-clique log x=max {1, In x} to,cl,c2,... are absolute constants when speaking of union, difference or partition of graphs, we work with the vertex-sets

We prove the following extension of Turan's theorem, conjectured by Erdos. Let t r(n) be the number of edges in the r -partite Turan graph T r (n) of order n , and suppose G is a graph of order n with at least t r (n) edges. Then either G=T r (n) or else there is a vertex x such that the subgraph spanned by the neighbours of x contains at least t r−1 (d) +1 edges, where d is the degree of x . Furthermore d>c r n , where c r is a constant.

The abstracts (in two languages) can be found in the pdf file of the article. Original author name(s) and title in Russian and Lithuanian: А. А. Юдин. Новое доказательство теоремы Эрдёша—Турана A. Judinas. Erdiošo—Turano teoremos naujas įrodymas

Maximum of a square-free quadratic form on a simplex. The following question was suggested by a problem of J. E. MacDonald Jr. (1):Given a graph G with vertices 1, 2, . . . , n. Let S be the simplex in En given by xi ≥ 0, Σxi = 1. What is