NDLI: Graph norms and Sidorenko’s conjecture

Content Provider	Springer Nature Link
Author	Hatami, Hamed
Copyright Year	2010
Abstract	Let H and G be two finite graphs. Define h $_{H}$(G) to be the number of homomorphisms from H to G. The function h $_{H}$(·) extends in a natural way to a function from the set of symmetric matrices to ℝ such that for A $_{G}$, the adjacency matrix of a graph G, we have h $_{H}$(A $_{G}$) = h $_{H}$(G). Let m be the number of edges of H. It is easy to see that when H is the cycle of length 2n, then h $_{H}$(·)$^{1/m }$ is the 2n-th Schatten-von Neumann norm. We investigate a question of Lovász that asks for a characterization of graphs H for which the function h $_{H}$(·)$^{1/m }$ is a norm.We prove that h $_{H}$(·)$^{1/m }$ is a norm if and only if a Hölder type inequality holds for H. We use this inequality to prove both positive and negative results, showing that h $_{H}$(·)$^{1/m }$ is a norm for certain classes of graphs, and giving some necessary conditions on the structure of H when h $_{H}$(·)$^{1/m }$ is a norm. As an application we use the inequality to verify a conjecture of Sidorenko for certain graphs including hypercubes. In fact, for such graphs we can prove statements that are much stronger than the assertion of Sidorenko’s conjecture.We also investigate the h $_{H}$(·)$^{1/m }$ norms from a Banach space theoretic point of view, determining their moduli of smoothness and convexity. This generalizes the previously known result for the 2n-th Schatten-von Neumann norms.
Starting Page	125
Ending Page	150
Page Count	26
File Format	PDF
ISSN	00212172
Journal	Israel Journal of Mathematics
Volume Number	175
Issue Number	1
e-ISSN	15658511
Language	English
Publisher	The Hebrew University Magnes Press
Publisher Date	2010-03-27
Publisher Place	Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Theoretical, Mathematical and Computational Physics Applications of Mathematics Analysis Group Theory and Generalizations Algebra Mathematics
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A proof of snevily’s conjecture

The Gaussian Moments Conjecture and the Jacobian Conjecture

Weak closure and Oliver’s p-group conjecture

On a conjecture by Kalai

Cocompactly cubulated graph manifolds

Simple loop conjecture for limit groups

Kummer’s conjecture for cubic Gauss sums

Clique complexes and graph powers

On the KŁR conjecture in random graphs

Graph norms and Sidorenko’s conjecture

Similar Documents

A proof of snevily’s conjecture

The Gaussian Moments Conjecture and the Jacobian Conjecture

Weak closure and Oliver’s p-group conjecture

On a conjecture by Kalai

Cocompactly cubulated graph manifolds

Simple loop conjecture for limit groups

Kummer’s conjecture for cubic Gauss sums

Clique complexes and graph powers

On the KŁR conjecture in random graphs

Graph norms and Sidorenko’s conjecture