Frustrated triangles

被引:4
作者
Kittipassorn, Teeradej [1 ]
Meszaros, Gabor [2 ]
机构
[1] Univ Memphis, Dept Math Sci, Memphis, TN 38152 USA
[2] Cent European Univ, Dept Math, H-1051 Budapest, Hungary
关键词
Frustrated triangle; Geometrical frustration;
D O I
10.1016/j.disc.2015.06.006
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A triple of vertices in a graph is a frustrated triangle if it induces an odd number of edges. We study the set F-n subset of [0, ((n)(3))] of possible number of frustrated triangles f (G) in a graph G on n vertices. We prove that about two thirds of the numbers in [0, n(3/2)] cannot appear in F-n, and we characterise the graphs G with 1(G) is an element of [0, n(3/2)]. More precisely, our main result is that, for each n >= 3, F-n, contains two interlacing sequences 0 = a(0) <= b(0) <= a(1) <= b(1) <= ... <= a(m) <= b(m) similar to n(3/2) such that F-n boolean AND (be, a(t+1)) = empty sit for all t, where the gaps are vertical bar b(t) - a(t+1)vertical bar = (n - 2) t(t + 1) and vertical bar a(t) - b(t)vertical bar = t(t - 1). Moreover,f(G) is an element of [a(t), b(t)] if and only if G can be obtained from a complete bipartite graph by flipping exactly t edges/nonedges. On the other hand, we show, for all n sufficiently large, that if m is an element of [f(n), ((n)(3)) - f(n)], then m is an element of F-n where f(n) is asymptotically best possible with f(n) similar to n(3/2) for n even and f(n) similar to root 2n(3/2) for n odd. Furthermore, we determine the graphs with the minimum number of frustrated triangles amongst those with n vertices and e <= n(2)/4 edges. (C) 2015 Elsevier B.V. All rights reserved.
引用
收藏
页码:2363 / 2373
页数:11
相关论文
共 16 条
[1]  
Balogh J., 2014, ARXIV14085296
[2]   Monochromatic triangles in three-coloured graphs [J].
Cummings, James ;
Kral, Daniel ;
Pfender, Florian ;
Sperfeld, Konrad ;
Treglown, Andrew ;
Young, Michael .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2013, 103 (04) :489-503
[3]  
Erdo P., 1962, Ill. J. Math., V6, P122
[4]  
Fay C.W., 2007, Statistical Mechanics of Vertex Cover
[5]  
Goodman A W., 1959, AM MATH MONTHLY, V66, P778
[6]   TRIANGLES IN A COMPLETE CHROMATIC GRAPH [J].
GOODMAN, AW .
JOURNAL OF THE AUSTRALIAN MATHEMATICAL SOCIETY SERIES A-PURE MATHEMATICS AND STATISTICS, 1985, 39 (AUG) :86-93
[7]   A Canonical Ramsey Theorem for Exactly m-Coloured Complete Subgraphs [J].
Kittipassorn, Teeradej ;
Narayanan, Bhargav P. .
COMBINATORICS PROBABILITY & COMPUTING, 2014, 23 (01) :102-115
[8]  
Lovasz L., 1983, STUDIES IN PURE MATH, P459
[9]  
Morgenstern A., 2014, J GRAPH THE IN PRESS
[10]  
Narayanan B. P., 2014, J GRAPH THE IN PRESS