A | B | C | D | E | F | |
---|---|---|---|---|---|---|

1 | Presented by | Paper | Abstract for the seminar | URL | Area/Rough description | |

2 | ||||||

3 | 3/4/2015 | Nikola Djokic | On the Density of Transitive Tournaments | http://honza.ucw.cz/limsem/abst01.pdf | http://arxiv.org/abs/1501.04074 | Direct 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/2015 | Aurel Adler | On the Caccetta-Haggkvist conjecture with forbidden subgraphs | http://honza.ucw.cz/limsem/abst02.pdf | http://arxiv.org/abs/1107.2247 | This 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/2015 | Salimova Diyora | TurÃ¡n densities of hypercubes | http://honza.ucw.cz/limsem/abst03.pdf | http://arxiv.org/abs/1201.3587 | A 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/2015 | EMPTY SLOT | N/A | this cell is intentionally left blank | http://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/2015 | Sven Buchmann | Limits : Chapters 7,8,9 | http://honza.ucw.cz/limsem/abst04.pdf | http://honza.ucw.cz/limsem/book-chap7_11.pdf | 3 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/2015 | Adrian Binding | Limits : Chapters 10,11 | http://honza.ucw.cz/limsem/abst05.pdf | http://honza.ucw.cz/limsem/book-chap7_11.pdf | The 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/2015 | Christian Wieser | A solution to 2/3 conjecture | http://honza.ucw.cz/limsem/abst06.pdf | http://arxiv.org/abs/1306.6202 | No 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/2015 | Pascal Su | Quasirandom permutations are characterized by 4-point densities | http://honza.ucw.cz/limsem/abst07.pdf | http://arxiv.org/abs/1205.3074 | An 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/2015 | Robin Leroy | Undecidability of linear inequalities in graph homomorphism densities | http://honza.ucw.cz/limsem/abst08.pdf | http://honza.ucw.cz/limsem/undec.pdf | Most 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/2015 | Lukas Brun | On the logarithimic calculus and Sidorenko's conjecture | http://honza.ucw.cz/limsem/abst09.pdf | http://arxiv.org/abs/1107.1153 | Flag 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...