# An extremal problem on degree sequences of graphs

Nathan Linial*, Eyal Rozenman

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

## Abstract

Let G = (In, E) be the graph of the n-dimensional cube. Namely In = {0, 1}n and [x, y] ε E whenever ||x - y||I = 1. For A ⊆ In and x ε A define hA(x) = #{y ε In / A{[x, y] ε E}, i.e., the number of vertices adjacent to x outside of A. Talagrand, following Margulis, proves that for every set A ⊆ In of size 2n-1 we have 1/2nxεA √hA(x) ≥ K for a universal constant K independent of n. We prove a related lower bound for graphs: Let G = (V, E) be a graph with |E| ≥ (k/2). Then ∑xεV(G) √d(x) ≥ k√k - 1, where d(x) is the degree of x. Equality occurs for the clique on k vertices.

Original language American English 573-582 10 Graphs and Combinatorics 18 3 https://doi.org/10.1007/s003730200041 Published - 2002

## Fingerprint

Dive into the research topics of 'An extremal problem on degree sequences of graphs'. Together they form a unique fingerprint.
{"ft_lang_label":"__label__en","ft_lang_prob":0.78867584,"math_prob":0.73115784,"size":1576,"snap":"2023-40-2023-50","text_gpt3_token_len":608,"char_repetition_ratio":0.085877866,"word_repetition_ratio":0.7706422,"special_character_ratio":0.39086294,"punctuation_ratio":0.13227513,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9734617,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-08T09:48:33Z\",\"WARC-Record-ID\":\"<urn:uuid:26b09c2c-917b-44fc-b72e-3bb45aed79a8>\",\"Content-Length\":\"44261\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:3523a4eb-d99f-4a93-aaad-9e35d1fc2b6a>\",\"WARC-Concurrent-To\":\"<urn:uuid:7bb15c1b-ccc9-473b-9a6c-10aa139c6ad1>\",\"WARC-IP-Address\":\"54.74.68.52\",\"WARC-Target-URI\":\"https://cris.huji.ac.il/en/publications/an-extremal-problem-on-degree-sequences-of-graphs\",\"WARC-Payload-Digest\":\"sha1:4N2AJNJ44HY5XV2BYE6NHYIIP7MD55W7\",\"WARC-Block-Digest\":\"sha1:HZOBWLSJRMC4SFPOD4XOGURFFACOESVZ\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679100739.50_warc_CC-MAIN-20231208081124-20231208111124-00847.warc.gz\"}"}