Graph Limits seminar
 Share
The version of the browser you are using is no longer supported. Please upgrade to a supported browser.Dismiss

 
$
%
123
 
 
 
 
 
 
 
 
 
 
 
 
 
 
ABCDEF
1
Presented byPaper
Abstract for the seminar
URLArea/Rough description
2
3
3/4/2015Nikola DjokicOn the Density of Transitive Tournaments http://honza.ucw.cz/limsem/abst01.pdfhttp://arxiv.org/abs/1501.04074Direct application of flag algebras, the main result of the paper shows that the best in order to minimize the number of small transitive tournaments in a large tournament is to take a random tournament, and, furthermore, the random tournament is the only way how to obtain the minimum.
4
3/11/2015Aurel AdlerOn the Caccetta-Haggkvist conjecture with forbidden subgraphshttp://honza.ucw.cz/limsem/abst02.pdfhttp://arxiv.org/abs/1107.2247This time, flag algebras are used to show a weaker version of Caccetta-Haggkvist conjecture - a famous problem in oriented graphs. The conjecture asks what is the minimum outdegree in an oriented graph that guarantees a copy of oriented triangle.
5
3/18/2015Salimova DiyoraTurán densities of hypercubeshttp://honza.ucw.cz/limsem/abst03.pdfhttp://arxiv.org/abs/1201.3587A slightly different set-up of flag algebras, tailored to problems in hypercubes. Namely, what is the maximum number of edges in a C4-free / C6-free subgraph of n-dimensional hypercube?
6
3/25/2015EMPTY SLOTN/Athis cell is intentionally left blankhttp://www.lipsum.com/the first three people that will read this description before April 1st can email Jan to claim a free beer.
7
4/1/2015Sven BuchmannLimits : Chapters 7,8,9http://honza.ucw.cz/limsem/abst04.pdfhttp://honza.ucw.cz/limsem/book-chap7_11.pdf3 chapters from the book "Large networks and graph limits" that build a toolbox for constructing an analytic object - graphon - that represents the limit of a convergent sequence of graphs. NOTE: the book is in the ETH library. Also, a personal copy from Jan can be borrowed if it will not be available in the library.
8
The Easter break, yay! This time, hopefully at the correct place
9
4/15/2015Adrian BindingLimits : Chapters 10,11http://honza.ucw.cz/limsem/abst05.pdfhttp://honza.ucw.cz/limsem/book-chap7_11.pdfThe following 2 chapters from the book, use the tools developed in the previous chapters to construct a graphon for every convergent sequence of graphs. NOTE: the book is in the ETH library. Also, a personal copy from Jan can be borrowed if it will not be available in the library.
10
4/22/2015Christian WieserA solution to 2/3 conjecturehttp://honza.ucw.cz/limsem/abst06.pdfhttp://arxiv.org/abs/1306.6202No matter how the edges of a complete graph are colored using RED/GREEN/BLUE, there are always (at most) 3 vertices and one of the colors, say RED, so that at least 2n/3 vertices have a RED edge to at least one of these 3 vertices. The paper first translate this problem to flag algebras, and then use the semidefinite method for solving it.
11
4/29/2015
12
5/6/2015Pascal SuQuasirandom permutations are characterized by 4-point densitieshttp://honza.ucw.cz/limsem/abst07.pdfhttp://arxiv.org/abs/1205.3074An analogue of Chung-Graham-Wilson, but this time for permutations: if pi has density 1/24 for every subpermutation of size 4, then pi has density 1/k! for every subpermutation of size k.
13
5/13/2015
14
5/20/2015Robin Leroy
Undecidability of linear inequalities in graph homomorphism densities
http://honza.ucw.cz/limsem/abst08.pdfhttp://honza.ucw.cz/limsem/undec.pdfMost of the applications of flag alebras in extremal graph theory are concerned with proving that a certain density expression f is non-negative for every graph G. Moreover, many of these results were obtained in an algorithmic way. Can it be that actually the framework of flag algebras will solve every extremal graph theory problem (provided we give it enough time)? This paper gives a negative answer to this question, even in much stronger sense -- the general problem of deciding whether a given density expression is non-negative is undecideable.
15
5/27/2015Lukas BrunOn the logarithimic calculus and Sidorenko's conjecturehttp://honza.ucw.cz/limsem/abst09.pdfhttp://arxiv.org/abs/1107.1153Flag Algebras and semidefinite method provides a systematic way of applying Cauchy-Schwarz inequality for extremal graph theory problems. In this paper, the authors set-up a framework for systematic way of applying Jensen inequality instead of Cauchy-Schwarz, and use it to resolve some cases of so called Sidorenko's conjecture.
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
Loading...
 
 
 
spring term 2015
Feedback
 
 
Main menu