## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, December 03, 2013, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Choongbum Lee (MIT)

## Two approaches to Sidorenko's conjecture

Sidorenko's conjecture states that the number of homomorphisms from a bipartite graph H to a graph G is at least the expected number of homomorphisms from H to the binomial random graph with the same expected edge density as G. In this talk, I will present two approaches to the conjecture. First, I will introduce the notion of tree-arrangeability, where a bipartite graph H with bipartition A \cup B is tree-arrangeable if neighborhoods of vertices in A have a certain tree-like structure, and show that Sidorenko's conjecture holds for all tree-arrangeable bipartite graphs. In particular, this implies that Sidorenko's conjecture holds if there are two vertices a1, a2 in A such that each vertex a in A satisfies N(a) \subseteq N(a1) or N(a) \subseteq N(a_2). Second, I will prove that if T is a tree and H is a bipartite graph satisfying Sidorenko's conjecture, then the Cartesian product of T and H also satisfies Sidorenko's conjecture. This result implies that, for all d \ge 2, the d-dimensional grid with arbitrary side lengths satisfies Sidorenko's conjecture.

Joint with Jeong Han Kim (KIAS) and Joonkyung Lee (Oxford)

Upcoming talks     |     All previous talks     |     Talks by speaker     | Upcoming talks in iCal format (beta version!)

Information for students and suggested topics for student talks
{"ft_lang_label":"__label__en","ft_lang_prob":0.8454162,"math_prob":0.79991215,"size":1806,"snap":"2023-40-2023-50","text_gpt3_token_len":507,"char_repetition_ratio":0.11931188,"word_repetition_ratio":0.0,"special_character_ratio":0.27851605,"punctuation_ratio":0.087878786,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9758485,"pos_list":[0,1,2,3,4],"im_url_duplicate_count":[null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-10-01T15:51:14Z\",\"WARC-Record-ID\":\"<urn:uuid:0c70d299-d7ca-4e5b-aaa8-dfe53127e01b>\",\"Content-Length\":\"14161\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:b3529c50-5085-462c-aeeb-67d1cc545830>\",\"WARC-Concurrent-To\":\"<urn:uuid:adaed012-7f5e-4c7f-8c33-052f5bd9b7cb>\",\"WARC-IP-Address\":\"129.132.114.93\",\"WARC-Target-URI\":\"https://ti.inf.ethz.ch/ew/mise/mittagssem.html?action=show&what=abstract&id=01c920acb8d4f5a28a6dc5b8713926d667507210\",\"WARC-Payload-Digest\":\"sha1:BLPZN2O4QXVMLDMXMOPXTJZ3GH4O4BOT\",\"WARC-Block-Digest\":\"sha1:SQX6PDXE2JG64I6D3JI7RBIXZ2LA5TBX\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-40/CC-MAIN-2023-40_segments_1695233510903.85_warc_CC-MAIN-20231001141548-20231001171548-00494.warc.gz\"}"}