Sunflower Conjecture

[1] “1”

Load required packages and functions

# load packages
library(ggplot2)
library(ape)
library(dplyr)
library(magrittr)
library(tidyr)
library(cluster)
library(sp)
library(rgeos)
library(reshape2)


# #set working directory setwd('/Users/zach/Dropbox
# (ZachTeam)/THE_BOOK/Analyses/Sunflower_Conjecture') #load source functions
# source('./Source/thetaRand.R') source('./Source/makeNewSet.R')
# source('./Source/makeSpatialLines.R') source('./Source/findTriangles.R')
# source('./Source/sunflowerFunction.R')

Motivation

Alweiss et al. (2019) recent paper describes an improvement on the lower bound of the number of sets required for the Sunflower lemma as an extension of the original conjecture set forth by Erdös and Rado (1960). The conjecture aimed to find the minimum number of sets required to achieve ordered sunflower-shaped structures from randomly-generated points. Alweiss et al. (2019) were able to reduce the lower bound from w^w number of sets required to get at least one sunflower to log(w)^w number of sets. However, the exercise presented here is motivated by the potential to simplify the problem further, and determine a true lower bound (e.g., 3^w or 4^w number of sets). Seeking an alternative approach to Alweiss et al. (2019), whose methods included forming sets (from randomly generated points), creating sub-groupings of three points to form a “petal”, and then searching for 3-petaled sunflower structures using a pruning approach to reduce the overall search space for large sets. Another method to further simplify the problem may be to generate randomly-oriented lines of fixed lengths on a plane, and then search for r-3 sunflowers using a triangle similiarty index, computed by the degree of similarity between an equilateral triangle and the resulting convex hull of triangles formed from groupings of 3 sets (i.e., line segments).

Methods

The following includes functions (in program R) to generate n sets of randomly-oriented lines with a fixed radius on a cartesian coordinate plane. The functions then group sets by proximity (nearest-neighbor) analysis, compute the convex hull of each of the groups, determine which are triangles (3-sided polygons), and then compute an equilateral triangle-similarity index using the Side-Side-Side congruence theorem. Finally, nested for-loops are used to simulate scenarios varying the number of sets in order to determine the lower bound of sets required to generate triangles approximating equilateral triangles, which in this case would be considered structurally equivalent to an r-3 sunflower.

Overview of functions

thetaRand: Generate a random angle

thetaRand <- function() {
    angle = runif(n = 1, min = 0, max = 360)
    return(angle)
}

makeNewSet: Generate a new set of 2 points separated by a fixed distance (r) defined by 1) a randomly generated point and 2) a randomly generated angle (from thetaRand)

# make new set function
makeNewSet <- function(radiusIn, setNum) {
    
    # fixed distance (radius)
    r = radiusIn
    
    centerX = runif(n = 1, min = 0, max = 1)
    centerY = runif(n = 1, min = 0, max = 1)
    
    thetaRand = thetaRand()
    
    xA = centerX
    yA = centerY
    
    xB = xA + r * cos(thetaRand * pi/180)
    yB = yA + r * sin(thetaRand * pi/180)
    
    xCoords <- c(xA, xB)
    yCoords <- c(yA, yB)
    
    newSet.df <- data.frame(Set = paste("Set_", setNum, sep = ""), x = xCoords, 
        y = yCoords)
    return(newSet.df)
}

makeSpatialLines: Convert newly-generated set to spatialLine objects

# sub funtion to make spatialLine objects
makeSpatialLines <- function(dataIn, nSets) {
    
    newSet.df <- dataIn
    
    save.my.lines <- list()
    for (i in 1:nSets) {
        
        sub.data <- subset(newSet.df, Set == paste("Set_", i, sep = ""))
        
        newLine <- Line(sub.data[, -1])
        
        S1 <- Lines(list(newLine), ID = paste("Set_", i, sep = ""))
        
        Sl <- SpatialLines(list(S1))
        
        save.my.lines <- append(save.my.lines, Sl)
        
    }
    
    lines.combined <- do.call(rbind, save.my.lines)
    
    df <- data.frame(len = sapply(1:length(lines.combined), function(i) gLength(lines.combined[i, 
        ])))
    
    rownames(df) <- sapply(1:length(lines.combined), function(i) lines.combined@lines[[i]]@ID)
    
    ## SpatialLines to SpatialLinesDataFrame
    Sldf <- SpatialLinesDataFrame(lines.combined, data = df)
    
    return(Sldf)
}

findTriangles: Using the side-side-side comparison to determine degree of shape similarity to an equilateral triangle (S1==S2==S3), filter potential groupings within generated sets that contain r-3 sunflowers (i.e, groupings of three spatialLines whose convex hull perimeter approximates an equilateral triangle).

findTriangles <- function(dataIn) {
    
    new.data <- dataIn
    
    # get Super_Sets
    superSets <- unique(new.data$Super_Set)
    
    triangles.save <- list()
    for (i in 1:length(superSets)) {
        
        # print(as.character(i))
        sub.data <- subset(new.data, Super_Set == superSets[i])
        
        # get chull from sub.data
        temp_hull_Set <- sub.data %>% group_by(Super_Set) %>% slice(chull(X, 
            Y))
        
        # get number of edges
        sub.data$edgeCount <- length(temp_hull_Set$X)
        
        # create Triangle column
        sub.data$Triangle <- ifelse(sub.data$edgeCount == 3, "Yes", "No")
        
        if (unique(sub.data$Triangle) == "Yes") {
            # get triangle coords
            ch <- chull(sub.data$X, sub.data$Y)
            coords <- sub.data[c(ch), ]
            
            # compute distances between each point pairs
            point.pairs <- coords
            coordinates(point.pairs) <- ~X + Y
            class(point.pairs)
            
            point.pairs.dist <- gDistance(point.pairs, byid = TRUE)
            
            # convert 0 to NA
            point.pairs.dist[point.pairs.dist == 0] <- NA
            
            # triangle test (Side-Side-Side proof of similarity) proportion of mean to
            # each side
            edge.mean <- mean(point.pairs.dist, na.rm = TRUE)
            
            # get unique list of distances
            triangle.edge.df <- data.frame(Edge = c("edge1", "edge2", "edge3"), 
                Distance = na.omit(unique(c(point.pairs.dist))))
            
            # get ratio of Distance/Mean
            triangle.edge.df$Ratio <- edge.mean/triangle.edge.df$Distance
            triangle.edge.df$EquilateralSimilarity <- 1 - sum(abs(triangle.edge.df$Ratio - 
                1))
            
            # test triangle.edge.df$RatioPerfect triangle.edge.df$RatioPerfect<-2
            # triangle.edge.df$EquilateralSimilarityTest<-1-sum(abs(triangle.edge.df$RatioPerfect-1))
            
            # add result to sub.data
            sub.data$EquilateralSimilarity <- unique(triangle.edge.df$EquilateralSimilarity)
        } else {
            sub.data$EquilateralSimilarity <- -Inf
        }
        
        triangles.save <- rbind(triangles.save, sub.data)
    }
    
    # rank order by similarity index (to equilateral triangles)
    triangles.save <- triangles.save[order(triangles.save$EquilateralSimilarity, 
        decreasing = TRUE), ]
    triangles.save$Super_Set <- factor(triangles.save$Super_Set, levels = unique(triangles.save$Super_Set))
    
    return(triangles.save)
}

sunflowerFunction: Combines previously described functions to generate n new sets, convert to spatialLines, and search for r-3 sunflowers (via Triangle approximation). Results are plotted are saved.

sunflowerFunction <- function(radiusLength, const, nSets, nSim, nIter) {
    
    # make new random sets
    save.sets <- list()
    for (i in 1:nSets) {
        newSet = makeNewSet(radiusIn = radiusLength, setNum = i)
        save.sets <- rbind(save.sets, newSet)
    }
    
    # make spatialLines objects from new random sets
    newSpatialLines <- makeSpatialLines(dataIn = save.sets, nSets = nSets)
    
    # use fortify to plot with ggplot
    newLinesFortify <- fortify(newSpatialLines)
    names(newLinesFortify)[names(newLinesFortify) == "lat"] <- "Y"
    names(newLinesFortify)[names(newLinesFortify) == "long"] <- "X"
    
    # get distance between newSpatialLines
    m <- gDistance(newSpatialLines, byid = TRUE)
    
    ## Use distances to extract the ids of the line segments (goups of 3) closest
    ## to each point.
    groups3 <- apply(m, 2, function(X) rownames(m)[order(X)][1:3])
    
    # go through each set get list of all Sets
    newSetList <- colnames(groups3)
    
    save.groups <- list()
    for (i in 1:length(newSetList)) {
        
        new.set.group <- groups3[, c(newSetList[i])]
        
        # subset
        sub.groups <- subset(newLinesFortify, c(id == new.set.group[1] | id == 
            new.set.group[2] | id == new.set.group[3]))
        
        # compute distances among points
        new.sp <- sub.groups
        coordinates(new.sp) <- ~X + Y
        class(new.sp)
        
        distMat <- gDistance(new.sp, byid = TRUE)
        distMat[distMat < radiusLength + 0.01] <- NA
        
        # look at eigen vectors and values?
        
        # get matrix summary stats
        mat.mean <- mean(distMat[row(distMat) != col(distMat)], na.rm = TRUE)
        mat.min <- min(distMat[row(distMat) != col(distMat)], na.rm = TRUE)
        mat.max <- max(distMat[row(distMat) != col(distMat)], na.rm = TRUE)
        mat.sum <- sum(distMat[row(distMat) != col(distMat)], na.rm = TRUE)
        
        # create data.frame of group with summary stats
        new.df <- data.frame(Set_Group = paste(new.set.group, collapse = "+"), 
            mean = mat.mean, min = mat.min, max = mat.max, sum = mat.sum)
        
        # add Set_Group to sub.groups
        sub.groups$Set_Group <- unique(new.df$Set_Group)
        
        # now merge
        sub.merge <- merge(sub.groups, new.df, by = "Set_Group", all.x = TRUE)
        
        save.groups <- rbind(save.groups, sub.merge)
    }
    
    # rank order and take top numGroups/3
    groups.sort <- save.groups[order(save.groups$sum, decreasing = FALSE), ]
    
    hullList <- unique(groups.sort$Set_Group)
    
    hull.area.save <- list()
    for (i in 1:length(hullList)) {
        groups.sort.sub <- subset(groups.sort, Set_Group == hullList[i])
        hpts <- chull(x = groups.sort.sub$X, y = groups.sort.sub$Y)
        # hpts <- subset(groups.sort.sub, Set_Group==hullList[1])
        hpts <- cbind(hpts, hpts[1])
        xy.coords <- cbind(groups.sort.sub$X, groups.sort.sub$Y)
        chull.coords <- xy.coords[hpts, ]
        chull.poly <- Polygon(chull.coords, hole = F)
        chull.area <- chull.poly@area
        
        groups.sort.sub$Hull_area <- chull.area
        
        # add sum:area column
        groups.sort.sub$Mean_Area_ratio <- groups.sort.sub$mean/groups.sort.sub$Hull_area
        
        hull.area.save <- rbind(hull.area.save, groups.sort.sub)
    }
    
    # rank order and take top numGroups/3
    groups.sort.area <- hull.area.save[order(hull.area.save$Mean_Area_ratio, 
        decreasing = FALSE), ]
    
    Set_Group.order <- unique(groups.sort.area$Set_Group)
    
    groups.sort$Set_Group <- factor(groups.sort$Set_Group, levels = Set_Group.order)
    
    # remove duplicates
    noDups.1 <- groups.sort.area
    noDups.1$Set_Group <- NULL
    noDups.2 <- unique(noDups.1)
    
    # create new factor from mean
    noDups.2$Super_Set <- factor(noDups.2$mean)
    
    numUniqueSuperSets <- as.character(seq(1, length(levels(noDups.2$Super_Set))))
    
    # make new factor level names
    superSetList <- paste("Super_Set_", numUniqueSuperSets, sep = "")
    
    levels(noDups.2$Super_Set) <- superSetList
    
    # search for triangles that could be sunflower arrangements
    triangle.search <- findTriangles(dataIn = noDups.2)
    
    # get convex hulls
    hull_Set <- triangle.search %>% group_by(Super_Set) %>% slice(chull(X, Y))
    
    
    if (length(unique(triangle.search$EquilateralSimilarity)) > 1) {
        
        triangle.search$EquilateralSimilarity <- ifelse(triangle.search$EquilateralSimilarity == 
            -Inf, NA, triangle.search$EquilateralSimilarity)
        hull_Set$EquilateralSimilarity <- ifelse(hull_Set$EquilateralSimilarity == 
            -Inf, NA, hull_Set$EquilateralSimilarity)
        
        new.plot <- ggplot(triangle.search, aes(x = X, y = Y, group = group)) + 
            geom_point(aes(color = EquilateralSimilarity), size = 0.5) + geom_path(aes(color = EquilateralSimilarity), 
            alpha = 0.7) + geom_polygon(data = subset(hull_Set, Triangle == 
            "Yes"), aes(fill = EquilateralSimilarity, group = Super_Set), alpha = 0.5) + 
            # geom_polygon(data = subset(hull_Set, Triangle=='Yes'),
        # aes(fill=EquilateralSimilarity, group=Super_Set),alpha = 0.5)+
        theme(legend.position = "none") + scale_color_viridis_c(na.value = "gray40") + 
            scale_fill_viridis_c(na.value = "gray40") + xlim(0, 1) + ylim(0, 
            1) + expand_limits(x = 0.2, y = 0.2)
        # coord_fixed(ratio=1)
    } else {
        new.plot <- ggplot(triangle.search, aes(x = X, y = Y, group = id)) + 
            geom_point(color = "gray50", size = 0.5) + geom_path(color = "gray50", 
            alpha = 0.7) + geom_polygon(data = hull_Set, fill = "gray50", aes(group = Super_Set), 
            alpha = 0.5) + theme(legend.position = "none") + xlim(0, 1) + ylim(0, 
            1) + expand_limits(x = 0.2, y = 0.2)
        # coord_fixed(ratio=1)
    }
    
    print(new.plot)
    
    plotName <- paste("Sunflower_plot_All_", paste(const, nSets, nSim, nIter, 
        sep = "_"), ".png", sep = "")
    ggsave(new.plot, file = paste("/Users/zach/Dropbox (ZachTeam)/THE_BOOK/Analyses/Sunflower_Conjecture/Figures/", 
        plotName, sep = ""), width = 8, height = 7, dpi = 600)
    
    
    
    if (length(unique(triangle.search$EquilateralSimilarity)) > 1) {
        
        triangle.search$EquilateralSimilarity <- ifelse(triangle.search$EquilateralSimilarity == 
            -Inf, NA, triangle.search$EquilateralSimilarity)
        hull_Set$EquilateralSimilarity <- ifelse(hull_Set$EquilateralSimilarity == 
            -Inf, NA, hull_Set$EquilateralSimilarity)
        
        
        new.plot <- ggplot(triangle.search, aes(x = X, y = Y, group = group)) + 
            geom_point(aes(color = EquilateralSimilarity), size = 0.5) + geom_path(aes(color = EquilateralSimilarity), 
            alpha = 0.7) + geom_polygon(data = hull_Set, aes(fill = EquilateralSimilarity, 
            group = Super_Set), alpha = 0.5) + # geom_polygon(data = subset(hull_Set, Triangle=='Yes'),
        # aes(fill=EquilateralSimilarity, group=Super_Set),alpha = 0.5)+
        theme(legend.position = "none") + scale_color_viridis_c(na.value = "gray40") + 
            scale_fill_viridis_c(na.value = "gray40") + xlim(0, 1) + ylim(0, 
            1) + expand_limits(x = 0.1, y = 0.1)
        # coord_fixed(ratio=1)
    } else {
        new.plot <- ggplot(triangle.search, aes(x = X, y = Y, group = id)) + 
            geom_point(color = "gray50", size = 0.5) + geom_path(color = "gray50", 
            alpha = 0.7) + geom_polygon(data = hull_Set, fill = "gray50", aes(group = Super_Set), 
            alpha = 0.5) + theme(legend.position = "none") + xlim(0, 1) + ylim(0, 
            1) + expand_limits(x = 0.1, y = 0.1)
        # coord_fixed(ratio=1)
        
    }
    
    new.plot.facet <- new.plot + facet_wrap(Super_Set ~ ., scales = "free") + 
        theme(strip.background = element_blank(), strip.text.x = element_blank())
    
    # print(new.plot.facet)
    
    plotName <- paste("Sunflower_plot_facet", paste(const, nSets, nSim, nIter, 
        sep = "_"), "png", sep = ".")
    ggsave(new.plot.facet, file = paste("/Users/zach/Dropbox (ZachTeam)/THE_BOOK/Analyses/Sunflower_Conjecture/Figures/", 
        plotName, sep = ""), width = 14, height = 7, dpi = 600)
    
    # combine plot of all Sets with hulls of triangles only overlaid
    
    # return triangle.search
    return(triangle.search)
}

Demonstration of functions

thetaRand()

newTheta <- thetaRand()
print(newTheta)

[1] 110.6794

makeNewSet(radiusIn,setNum)

newSet <- makeNewSet(radiusIn = 0.05, setNum = 1)
kable(newSet)

Set	x	y
Set_1	0.7975776	0.1341498
Set_1	0.8359634	0.1021102

newSetPlot <- ggplot(newSet, aes(x = x, y = y)) + geom_point(color = "royalblue2") + 
    geom_path(color = "royalblue2", alpha = 0.7) + theme(legend.position = "none") + 
    xlim(0, 1) + ylim(0, 1) + expand_limits(x = 0.1, y = 0.1) + coord_fixed(ratio = 1)

newSetPlot

makeSpatialLines(radiusIn,setNum)

nSets = 100
radiusLength = 0.05

# make new random sets
save.sets <- list()
for (i in 1:nSets) {
    newSet = makeNewSet(radiusIn = radiusLength, setNum = i)
    save.sets <- rbind(save.sets, newSet)
}

# make spatialLines objects from new random sets
newSpatialLines <- makeSpatialLines(dataIn = save.sets, nSets)

# use fortify to plot with ggplot
newLinesFortify <- fortify(newSpatialLines)
names(newLinesFortify)[names(newLinesFortify) == "lat"] <- "Y"
names(newLinesFortify)[names(newLinesFortify) == "long"] <- "X"

newSpatialLinesPlot <- ggplot(newLinesFortify, aes(x = X, y = Y, group = group)) + 
    # geom_point(color='royalblue2',size=0.5)+
geom_path(color = "royalblue2", alpha = 0.4) + theme(legend.position = "none") + 
    xlim(0, 1) + ylim(0, 1) + expand_limits(x = 0.2, y = 0.2) + coord_fixed(ratio = 1)
newSpatialLinesPlot

findTriangles(dataIn)

nSets = 100
radiusLength = 0.05

# make new random sets
save.sets <- list()
for (i in 1:nSets) {
    newSet = makeNewSet(radiusIn = radiusLength, setNum = i)
    save.sets <- rbind(save.sets, newSet)
}

# make spatialLines objects from new random sets
newSpatialLines <- makeSpatialLines(dataIn = save.sets, nSets = nSets)

# use fortify to plot with ggplot
newLinesFortify <- fortify(newSpatialLines)
names(newLinesFortify)[names(newLinesFortify) == "lat"] <- "Y"
names(newLinesFortify)[names(newLinesFortify) == "long"] <- "X"

# get distance between newSpatialLines
m <- gDistance(newSpatialLines, byid = TRUE)

## Use distances to extract the ids of the line segments (goups of 3) closest
## to each point.
groups3 <- apply(m, 2, function(X) rownames(m)[order(X)][1:3])

# go through each set get list of all Sets
newSetList <- colnames(groups3)

save.groups <- list()
for (i in 1:length(newSetList)) {
    
    new.set.group <- groups3[, c(newSetList[i])]
    
    # subset
    sub.groups <- subset(newLinesFortify, c(id == new.set.group[1] | id == new.set.group[2] | 
        id == new.set.group[3]))
    
    # compute distances among points
    new.sp <- sub.groups
    coordinates(new.sp) <- ~X + Y
    class(new.sp)
    
    distMat <- gDistance(new.sp, byid = TRUE)
    distMat[distMat < radiusLength + 0.01] <- NA
    
    # look at eigen vectors and values?
    
    # get matrix summary stats
    mat.mean <- mean(distMat[row(distMat) != col(distMat)], na.rm = TRUE)
    mat.min <- min(distMat[row(distMat) != col(distMat)], na.rm = TRUE)
    mat.max <- max(distMat[row(distMat) != col(distMat)], na.rm = TRUE)
    mat.sum <- sum(distMat[row(distMat) != col(distMat)], na.rm = TRUE)
    
    # create data.frame of group with summary stats
    new.df <- data.frame(Set_Group = paste(new.set.group, collapse = "+"), mean = mat.mean, 
        min = mat.min, max = mat.max, sum = mat.sum)
    
    # add Set_Group to sub.groups
    sub.groups$Set_Group <- unique(new.df$Set_Group)
    
    # now merge
    sub.merge <- merge(sub.groups, new.df, by = "Set_Group", all.x = TRUE)
    
    save.groups <- rbind(save.groups, sub.merge)
}

# rank order and take top numGroups/3
groups.sort <- save.groups[order(save.groups$sum, decreasing = FALSE), ]

hullList <- unique(groups.sort$Set_Group)

hull.area.save <- list()
for (i in 1:length(hullList)) {
    groups.sort.sub <- subset(groups.sort, Set_Group == hullList[i])
    hpts <- chull(x = groups.sort.sub$X, y = groups.sort.sub$Y)
    # hpts <- subset(groups.sort.sub, Set_Group==hullList[1])
    hpts <- cbind(hpts, hpts[1])
    xy.coords <- cbind(groups.sort.sub$X, groups.sort.sub$Y)
    chull.coords <- xy.coords[hpts, ]
    chull.poly <- Polygon(chull.coords, hole = F)
    chull.area <- chull.poly@area
    
    groups.sort.sub$Hull_area <- chull.area
    
    # add sum:area column
    groups.sort.sub$Mean_Area_ratio <- groups.sort.sub$mean/groups.sort.sub$Hull_area
    
    hull.area.save <- rbind(hull.area.save, groups.sort.sub)
}

# rank order and take top numGroups/3
groups.sort.area <- hull.area.save[order(hull.area.save$Mean_Area_ratio, decreasing = FALSE), 
    ]

Set_Group.order <- unique(groups.sort.area$Set_Group)

groups.sort$Set_Group <- factor(groups.sort$Set_Group, levels = Set_Group.order)

# remove duplicates
noDups.1 <- groups.sort.area
noDups.1$Set_Group <- NULL
noDups.2 <- unique(noDups.1)

# create new factor from mean
noDups.2$Super_Set <- factor(noDups.2$mean)

numUniqueSuperSets <- as.character(seq(1, length(levels(noDups.2$Super_Set))))

# make new factor level names
superSetList <- paste("Super_Set_", numUniqueSuperSets, sep = "")

levels(noDups.2$Super_Set) <- superSetList

# search for triangles that could be sunflower arrangements
triangle.search <- findTriangles(dataIn = noDups.2)

# get convex hulls
hull_Set <- triangle.search %>% group_by(Super_Set) %>% slice(chull(X, Y))

if (length(unique(triangle.search$EquilateralSimilarity)) > 1) {
    
    triangle.search$EquilateralSimilarity <- ifelse(triangle.search$EquilateralSimilarity == 
        -Inf, NA, triangle.search$EquilateralSimilarity)
    hull_Set$EquilateralSimilarity <- ifelse(hull_Set$EquilateralSimilarity == 
        -Inf, NA, hull_Set$EquilateralSimilarity)
    
    new.plot <- ggplot(triangle.search, aes(x = X, y = Y, group = group)) + 
        # geom_point(aes(color=EquilateralSimilarity),size=0.5)+
    geom_path(aes(color = EquilateralSimilarity), alpha = 0.7) + geom_polygon(data = subset(hull_Set, 
        Triangle == "Yes"), aes(fill = EquilateralSimilarity, group = Super_Set), 
        alpha = 0.5) + # geom_polygon(data = subset(hull_Set, Triangle=='Yes'),
    # aes(fill=EquilateralSimilarity, group=Super_Set),alpha = 0.5)+
    theme(legend.position = "none") + # scale_color_viridis_c(na.value='gray40')+
    # scale_fill_viridis_c(na.value='gray40')+
    xlim(0, 1) + ylim(0, 1) + expand_limits(x = 0.1, y = 0.1) + coord_fixed(ratio = 1)
} else {
    new.plot <- ggplot(triangle.search, aes(x = X, y = Y, group = id)) + # geom_point(color='gray50',size=0.5)+
    geom_path(color = "gray50", alpha = 0.7) + geom_polygon(data = hull_Set, 
        fill = "gray50", aes(group = Super_Set), alpha = 0.5) + theme(legend.position = "none") + 
        xlim(0, 1) + ylim(0, 1) + expand_limits(x = 0.1, y = 0.1) + coord_fixed(ratio = 1)
}

new.plot

sunflowerFunction(dataIn)

# generate list of constants c^w number of times
constList <- c(3, 4)
numSetList <- c(3, 4, 5)
iter = 1

# test 3^w, 4^w
triangleSearchResults <- sunflowerFunction(radiusLength = 0.05, const = constList[1], 
    nSets = constList[1]^numSetList[1], nSim = 1, nIter = iter)

if (length(unique(triangle.search$EquilateralSimilarity)) > 1) {
    
    triangle.search$EquilateralSimilarity <- ifelse(triangle.search$EquilateralSimilarity == 
        -Inf, NA, triangle.search$EquilateralSimilarity)
    hull_Set$EquilateralSimilarity <- ifelse(hull_Set$EquilateralSimilarity == 
        -Inf, NA, hull_Set$EquilateralSimilarity)
    
    new.plot <- ggplot(triangle.search, aes(x = X, y = Y, group = group)) + 
        # geom_point(aes(color=EquilateralSimilarity),size=0.5)+
    geom_path(aes(color = EquilateralSimilarity), alpha = 0.7) + geom_polygon(data = subset(hull_Set, 
        Triangle == "Yes"), aes(fill = EquilateralSimilarity, group = Super_Set), 
        alpha = 0.5) + # geom_polygon(data = subset(hull_Set, Triangle=='Yes'),
    # aes(fill=EquilateralSimilarity, group=Super_Set),alpha = 0.5)+
    theme(legend.position = "none") + # scale_color_viridis_c(na.value='gray40')+
    # scale_fill_viridis_c(na.value='gray40')+
    xlim(0, 1) + ylim(0, 1) + expand_limits(x = 0.1, y = 0.1) + coord_fixed(ratio = 1)
} else {
    new.plot <- ggplot(triangle.search, aes(x = X, y = Y, group = id)) + # geom_point(color='gray50',size=0.5)+
    geom_path(color = "gray50", alpha = 0.7) + geom_polygon(data = hull_Set, 
        fill = "gray50", aes(group = Super_Set), alpha = 0.5) + theme(legend.position = "none") + 
        xlim(0, 1) + ylim(0, 1) + expand_limits(x = 0.1, y = 0.1) + coord_fixed(ratio = 1)
}

new.plot

Run simulations under various scenarios to find lower bound of number of sets required to get a 3-r sunflower

Nested for loops to simulate different constants (3,4,5) and numbers of sets (w^w; e.g., 3^3=27 sets)

# generate list of constants c^w number of times
constList <- c(3, 4)
numSetList <- c(3, 4, 5)

# Run simulate over n iterations and then plot distribution
save.results <- list()
for (j in 1:length(constList)) {
    
    const <- NULL
    const <- as.character(numSetList[j])
    
    sim.results <- list()
    for (h in 1:length(numSetList)) {
        
        
        nSets <- constList[j]^as.numeric(numSetList[h])
        # set number of simulations
        nSim = 100
        print(nSim)
        
        new.results <- list()
        for (i in 1:nSim) {
            print(i)
            sf1 = NULL
            sf1 = sunflowerFunction(radiusLength = 0.05, const = const, nSets = nSets, 
                nSim = nSim, nIter = i)
            
            # add column with number of iterations
            sf1$nSim <- as.character(nSim)
            
            # add number of sets
            sf1$Num_of_Sets <- as.character(nSets)
            
            # add const
            sf1$Constant <- const
            
            new.results <- rbind(new.results, sf1)
        }
        
        sim.results <- rbind(sim.results, new.results)
        
    }
    save.results <- rbind(save.results, sim.results)
}

# save results write.csv(save.results, file='/Users/zach/Dropbox
# (ZachTeam)/THE_BOOK/Analyses/Sunflower_Conjecture/Data/Sunflower_simulation_results_1-02-2019.csv',row.names=FALSE)

Simulation results

results.data <- read.csv("/Users/zach/Dropbox (ZachTeam)/THE_BOOK/Analyses/Sunflower_Conjecture/Data/Sunflower_simulation_results_1-03-2019.csv", 
    header = TRUE)

# add constant column into data
results.data$Constant <- ifelse(results.data$Num_of_Sets == "27", "3^w", ifelse(results.data$Num_of_Sets == 
    "81", "3^w", ifelse(results.data$Num_of_Sets == "243", "3^w", "4^w")))


# make variables factors
results.data$Constant <- as.factor(results.data$Constant)
results.data$nSim <- as.factor(results.data$nSim)
results.data$Num_of_Sets <- as.factor(as.character(results.data$Num_of_Sets))
results.data$Num_of_Sets <- factor(results.data$Num_of_Sets, levels = c("27", 
    "64", "81", "256", "243", "1024"))

# plot it
myColors <- c("gray50", "royalblue2")
triangleDensityPlot <- ggplot(results.data, aes(x = Triangle, fill = Triangle, 
    color = Triangle)) + geom_density(alpha = 0.3) + scale_fill_manual(values = myColors) + 
    scale_color_manual(values = myColors) + theme(legend.position = c(0.2, 0.075)) + 
    ylab("Density")
# triangleDensityPlot

trianglePlot.facet <- triangleDensityPlot + facet_grid(Num_of_Sets ~ Constant)

annotate_figure(trianglePlot.facet, right = text_grob("Number of Sets", rot = 270, 
    size = 14))

References

Alweiss, R., Lovett, S., Wu, K. and Zhang, J., 2019. Improved bounds for the sunflower lemma. arXiv preprint arXiv:1908.08483.

Erdös, P., and R. Rado. 1960. Intersection theorems for systems of sets. Journal of the London Mathematical Society, 35(1):85–90, 1960