COSAM » Departments » Mathematics & Statistics » Research » Seminars » Combinatorics

# Combinatorics

DMS Combinatorics Seminar
Mar 30, 2023 02:00 PM
328 Parker Hall/ZOOM

Speaker: Debsoumya Chakraborti, Institute for Basic Science (IBS), South Korea

Title: TBA

DMS Combinatorics Seminar
Mar 23, 2023 01:00 PM
328 Parker Hall/ZOOM

Speaker: Zilin Jiang, Arizona State University

Title: Forbidden subgraphs and spherical two-distance sets

DMS Combinatorics Seminar
Mar 21, 2023 02:00 PM
328 Parker Hall

Speaker: Chris Cox, Iowa State University

Title: Subgraph counts in planar graphs and maximum likelihood estimators of graphs

Abstract:(1) How many copies of a graph $$H$$ can exist within an $$n$$-vertex planar graph? Such questions can be traced back to the late 1970's when Hakimi and Schmeichel determined the maximum number of copies of $$C_3$$ and $$C_4$$ that a planar graph can hold. Furthermore, these problems have recently regained quite a bit of popularity!(2) For a graph $$H$$ on $$m$$ edges, which probability mass $$\mu$$ on the edges of some clique maximizes the probability that $$m$$ edges sampled independently from $$\mu$$ form a copy of $$H$$? While maximum likelihood estimation questions have a rich history (dating back to the 1920's), the above question appears to have never been asked...It turns out that there's a close relationship between problems (1) and (2) for graphs which display a certain subdivision structure. In this talk, we'll discuss this relationship illustrate how it can be used to show that a planar graph on $$n$$ vertices contains at most $$(n/3)^3$$ many copies of $$C_6$$.

DMS Combinatorics Seminar
Mar 16, 2023 02:00 PM
328 Parker Hall/ZOOM

Speaker: Songling Shan, Illinois State University/Auburn

Title: 2-factors in 3/2-tough plane triangulations

Abstract: In 1956, Tutte proved the celebrated theorem that every 4-connected planar graph is hamiltonian. This result implies that every more than $\frac{3}{2}$-tough planar graph on at least three vertices is hamiltonian, and so has a 2-factor.  Owens in 1999 constructed non-hamiltonian maximal planar graphs of toughness smaller than $\frac{3}{2}$. In fact, the graphs Owens constructed do not even contain a 2-factor. Thus the toughness of exactly  $\frac{3}{2}$  is the only case left in asking about the existence of 2-factors in tough planar graphs. This question was also asked by  Bauer, Broersma, and  Schmeichel in a survey. We close this gap by showing that every maximal  $\frac{3}{2}$-tough plane graph on at least three vertices has a 2-factor.

DMS Combinatorics Seminar
Mar 14, 2023 02:00 PM
328 Parker Hall/ZOOM

Speaker: Kathryn Nurse, Simon Fraser University

Title: Nowhere-zero flows in signed graphs

DMS Combinatorics Seminar
Mar 02, 2023 02:00 PM
328 Parker Hall/ZOOM

Speaker: Deepak Bal, Montclair State University (New Jersey)

Topic: Nordhaus-Gaddum for number of cliques

DMS Combinatorics Seminar
Feb 23, 2023 02:00 PM
328 Parker Hall

Speaker: Peter Johnson

Title: $G$-colorings of graphs $H$ on the same vertex set

DMS Combinatorics Seminar
Feb 16, 2023 02:00 PM
328 Parker Hall

Speaker: Peter Johnson, AU

Topic: On a Two-Person Game Proposed in the Graduate Student Research Seminar

Abstract: In the February 9 GSRS, the following type of 2-player game was proposed:  For an integer t > 2, and integers 0 < a(1) < … < a(t – 1), let S = {0, a(1), … , a(t – 1)}.  Two players, Roberto and Babette, will take turns coloring integers with red and blue, respectively, with no integer allowed to be colored twice, until one of them achieves the (monochromatic) coloring of a set of the form c + dS, in which c and d are integers and d is not 0.  (If d is required to be > 0, the game is slightly different.)  When this is achieved, the game is over and the player achieving the coloring has won.  In the Seminar it was claimed that when t = 3 the player to go first has a winning strategy, regardless of what S is (although the strategy will vary as S varies).

A number of questions arise, but in this talk I hope to raise questions that you may not have noticed right off, based on these games’ kinship with tic-tac-toe, and the obvious connection of certain modifications of these games (in which all the coloring is confined to a finite block of consecutive integers) to the famous 1927 theorem of B. L. van der Waerden about avoiding monochromatic k-term arithmetic  progressions in coloring blocks of consecutive integers.  (Note that every k-term arithmetic progression is a set of the form c + dS, S = {0, 1, 2, … , k – 1}, d > 0.)

DMS Combinatorics Seminar
Feb 09, 2023 02:00 PM
328 Parker Hall

Speaker: Jessica McDonald, AU

Topic: On flows (and group-connectivity) in signed graphs

DMS Combinatorics Seminar
Feb 02, 2023 02:00 PM
328 Parker Hall

Speaker: Joe Briggs

Title: Worst-Case Pyromania

DMS Combinatorics Seminar
Dec 01, 2022 02:00 PM
ZOOM

Speaker: Craig Larson (Virginia Commonwealth U)

Title: Independent Sets in Graphs & LP Theory

Abstract: Integer programming, together with linear programming relaxations of integer programs, were used beginning in the 60s as a tool for finding maximum independent sets in graphs and bounding the independence number.  Several attractive results appeared in the 70s and 80s---often in linear programming journals. Many related ideas reappeared later in a purely graph theoretic context and several essentially equivalent theorems were rediscovered and reproved. This talk will survey these ideas, connections and theorems.

Last Updated: 09/13/2022